Algorithmus für die nte-Wurzel gesucht

[Chuck]

Probier' mal diese Rekursionsformel für ein beliebiges a und a_0 und dein n für
den Wurzelgrad:

a_k+1 = ( (n - 1) * a_k + a / (a_k)^(n - 1) ) / n

Nach paar Schritten ist a_k+1 ≈ nte Wurzel von a

[Mathematikker]

stefan2008 schrieb:

Das ist schon schlau gedacht. Aber die Logarithmus-Funktion aus der cmath kann ich nicht direkt verwenden, da ich die Zahlen in einzelne Ziffern zerlege. Aber Du hast mich auf eine tolle Idee gebracht. Ich muss eine eigene Logarithmus-Funktion für meinen Datentyp schreiben. Ich muss nur wissen, wie die Formel für den Logarithmus geht, dann wäre ich die Lösung ein Schritt näher.

Die Reihendarstellung des Logarithmus findest du hier: http://de.wikipedia.org/wiki/Logarithmus#Potenzreihe
Leider geht derzeit ja der Latex-Modus hier im Forum nicht mehr.

Aber die Methode von Chuck ist natürlich besser. Dachte mir schon, dass es eine Verallgemeinerung zu dem Heron-Verfahren gibt, aber kannte es bis eben nicht

[stefan2008]

Danke für eure Hilfe. Ich hoffe nur das ich mein CPU nicht übervordere, da die Genauigkeit bei meinem Datentypen bei 2000 Nachkommastellen liegt.

[.filmor]

Wenn du das Newtonverfahren benutzt (Chucks Vorschlag), dann verdoppelst du mit jeder Iteration die Anzahl der „korrekten“ Stellen, nach 11 Iterationen (log_2 2048 = 11 ≥ log_2 2000 > log_2 1024 = 10) bist du also bereits soweit, dass die Wurzel einer Zahl mit einer Stelle vor dem Komma in deinem Datentyp so genau ist wie es nur geht.

[Taurin]

stefan2008 schrieb:

Danke für eure Hilfe. Ich hoffe nur das ich mein CPU nicht übervordere, da die Genauigkeit bei meinem Datentypen bei 2000 Nachkommastellen liegt.

Ich hab mal kurz deine Seite überflogen. Big-Number-Klassen sind ja schon von vielen Leuten sehr ausführlich behandelt worden, ich bin alles andere als Experte dafür. Aber z.b. könntest du mal überlegen, statt Dezimalzahlen eine andere Zahlendarstellung zu wählen. Wie wäre es, statt zur Basis 10 zur Basis 256 (oder eine andere geeignete 2er-Potenz) zu rechnen? Dann ist ein Byte genau eine Ziffer und du sparst viel Speicher. Ausserdem lassen sich viele Operationen durch Bit-Verknüpfungen / -shifts ausdrücken.

Und ausserdem: Warum gerade 2000 Nachkommastellen? Warum nicht 100 oder eine Millionen?

[stefan2008]

Naja, mit 2000 verbinde ich das Jahr 2000; ein neuer Zeitabschnitt. Natürlich kann ich auch mehr Nachkommastellen benutzen. Aber wenn es mehr als 5000 Nachkommastellen sind, braucht die Prozedur mehr Zeit. Mein Ziel ist es, dass der Computer nicht Byteweise rechnet, sondern so wie wir es als Menschen es gewohnt sind.
Der Computer ist wie ein Kind, den man alles beibringen muss. Mein Klasse schreibt den Computer einige Regel vor.
1.) Regel sagt den Computer: Eine Zahl kann aus mehreren Ziffern bestehen und diese Ziffern können (bei der Dezimaldarstellung) nur die Zahl 0 bis 9 einnehmen.
2.) Regel besagt: Wenn eine Zahl größer als die (Schalt-)Zahl 9 ist, muss eine neue Ziffer vor der anderen stehen.
3.) Regel schreibt den Computer vor: Wenn Du ein Fehler findest, solltest Du es automatisch ausfilter, um den Benutzer Zeit und ärger ersparren.
usw...

Wenn ich nicht mit Zeichenketten gearbeitet hätte, würde er vielleicht schnell aber nicht sicher arbeiten. Mein Ziel ist es, ein Datentyp zu programmieren, dass im Gegensatz zu den Standarddatentypen, Regeln berücksichtigt und er den Programmiere Helfen soll, die Fehler schnell zu finden.

Rein theoretisch könnte man (zumindest beim Miniprogramm strbib), wie ein verrückter auf die Tasten hauen und trotzdem könnte mein Programm die Fehler abfangen (ohne try... catch!). Darauf bin ich sehr stolz!

Mittlerweile überlege ich mir, ob ich die Division durch Null erlauben soll und Sonderregelung aufstellen soll:

1.) Regel:
[endlose Zahl] = 999999999999999999...
Alle Ziffern mit der Schaltzahl 9 belegen, da 1 + 9 eine neue Ziffer voranstellt.

2.) Regel:
([beliebige Zahl] < [endlose Zahl]) : 0 = ([endlose Zahl] - [beliebige Zahl])

3.) Regel:
([beliebige Zahl] > [endlose Zahl]) : 0 = ([beliebige Zahl] - [endlose Zahl])

Da 0 bis [endlose Zahl] geht und von [endlose Zahl] zum (negative)[endlose Zahl] übergeht bis hinzu 0 - so meine Überlegung.

Beispiel:
0 : 0 = [endlose Zahl]
[endlose Zahl] * 0 = 0
1 : 0 = 999999999999....8

Alternative Regel:
[beliebige Zahl] : 0 = [beliebige Zahl] unit

unit = Einheit

Klingt zwar idiotisch aber, wenn man früher mit Imaginäre Zahlen experimentiert hat, könnte man bei der Division durch Null auch einen neuen Zahlentyp einführen finde ich.

[.filmor]

stefan2008 schrieb:

Naja, mit 2000 verbinde ich das Jahr 2000; ein neuer Zeitabschnitt. Natürlich kann ich auch mehr Nachkommastellen benutzen. Aber wenn es mehr als 5000 Nachkommastellen sind, braucht die Prozedur mehr Zeit.

Wenn technisch nichts dagegen spricht, dann lass die Genauigkeit vom Nutzer angeben.

stefan2008 schrieb:

Mein Ziel ist es, dass der Computer nicht Byteweise rechnet, sondern so wie wir es als Menschen es gewohnt sind.

Hast du schonmal daran gedacht, dass es vielleicht einen Grund hat, dass sich an manchen Stellen das Rechnen des Computers von dem eines Menschen unterscheidet?

stefan2008 schrieb:

3.) Regel schreibt den Computer vor: Wenn Du ein Fehler findest, solltest Du es automatisch ausfilter, um den Benutzer Zeit und ärger ersparren.

Das ist völlig kontraproduktiv. Du unterschlägst die Fehler nur, damit ersparst du mitnichten Zeit und Ärger.

stefan2008 schrieb:

Wenn ich nicht mit Zeichenketten gearbeitet hätte, würde er vielleicht schnell aber nicht sicher arbeiten.

Wie kommst du darauf? Was wäre denn anders, wenn du die Zeichenkette nicht als solche sondern als ein Array von Bytes ansiehst?

stefan2008 schrieb:

Mein Ziel ist es, ein Datentyp zu programmieren, dass im Gegensatz zu den Standarddatentypen, Regeln berücksichtigt und er den Programmiere Helfen soll, die Fehler schnell zu finden.

Indem du sie verschweigst?

Nebenbei, eine Division durch 0 ist /immer/ ein Fehler, ich sehe überhaupt keine Rechtfertigung für deine Vorschläge.
Sinnvolle Möglichkeiten sind z.B. einen speziellen Wert einführen (inf bzw. -inf), für 0/0 braucht's dann aber noch was anderes (NaN), oder eine Exception werfen.

stefan2008 schrieb:

Klingt zwar idiotisch aber, wenn man früher mit Imaginäre Zahlen experimentiert hat, könnte man bei der Division durch Null auch einen neuen Zahlentyp einführen finde ich.

Wie meinen?

[Chuck]

Grüße,

wie soll das mit dem Fehlerbeheben funktionieren? Woher will denn der Rechner
wissen was ein Fehler ist und was nicht?
Über diese Sache mit unendlich und co. haben sich schon andere Leute Gedanken
gemacht. Schau' mal, was du über surreelle Zahlen oder Nichtstandardanalysis
findest.

[Kritiker2000]

@stefan2008:
Kann mich nur anschließen.
Ein paar Kritikpunkte, die du dir wirklich zu Herzen nehmen solltest:

1. Wie schon gesagt, braucht deine Art der Zahlendarstellung unnötig viel Speicher und ist unnötig langsam. Computer rechnen nunmal bitweise und nicht mit Zeichen. Auf einem 64-Bit-Prozessor könntest du mit einem einzigen Befehl gleich 64 Stellen addieren (im Dualsystem, also ~20 Stellen im Dezimalsystem). So wie du es machst, kannst du nur eine einzige Stelle auf einmal addieren/subtrahieren. Mit der std::list kommt nochmal ein gewaltiger Speicher-Overhead dazu, um die doppelt verkettete Liste zu verwalten. Wenn überhaupt ein Container, dann einen std::vector benutzen! Am besten aber ein Array.
2. Fehler sollen nicht verschwiegen werden. Eine gute Bibliothek sollte m.M.n. Fehler auf jeden Fall mitteilen, sonst bleiben sie unentdeckt, und der Programmierer sucht an der falschen Stelle.
3. Du benutzt an vielen Stellen kein const-Schlüsselwort. Google mal nach "const correctness".
4. Parameter werden bei dir immer als Kopie übergeben - d.h. zum Beispiel bei einer Addition müssen beide Zahlen zuerst kopiert werden (inklusive der darin enthaltenen std::list). Das ist unnötig langsam. Übergabe per konstanter Referenz benutzt man da eigentlich.
5. Die Namensgebung: "Digit" heißt "Ziffer". Du willst damit aber eine Zahl darstellen, also ist der Name irreführend.
6. Deine Überladung des "!"-Operators ist irreführend, da man damit normalerweise die boolsche Negation in Verbindung bringt. Zudem steht dieser Operator vor der Zahl, während das Ausrufungszeichen bei der Fakultät hinter der Zahl steht.
7. Was sollen die Operatoren << und >> mit Kommazahlen tun? Mir fällt da nichts Sinnvolles ein. In der Beschreibung steht was von "bitweisem Verschieben". Wie soll das gehen, bzw. was soll da rauskommen?

[stefan2008]

Ich möchte try.. catch sovie exception vermeiden. Mein Datentyp soll nicht "versuchen" etwas zu rechen, sondern "soll es" rechnen. Wenn er ein Fehler bemerkt, filtert er diesen Fehler aus und gibt eine kleine Meldung aus ( Screenshots auf http://www.srbib.de/medien.html). Das mit den Nachkommastellen habe ich mir schon überlegt. Wenn man sich den Quelltext anschaut, sieht man, das ganz oben eine Konstante steht, die für die Nachkommastellenbegrenzung zuständig ist. Die kann man beliebig verändern. Ich habe es eigebaut, damit die Divison mit Fließkommazahlen überhaupt erst funktioniert. Hätte ich es weggelassen, so würde der Komma bei der Division nicht an der richtige Stelle stehn.
Das mit der Einführung einer neuen Zahl war eine Schnapsidee. Ich dachte, wenn sich Leute schon mit Wurzel ziehen von Negativen Zahlen Gedanken gemacht haben (sprich komplexe Zahlen), könnten sich andere Gedanken mit der Division durch null machen.

PS: Die Fehler werden markiert und sind sichtbar, auch wenn die Bibliothek diese automatisch filtert ( Screenshot http://www.srbib.de/screenshots/screenshot4.png)

[Kritiker2000]

@stefan2008:
Warum gehst du nicht auf meine 7 Punkte ein?

[Kritiker2000]

Mir ist nochwas aufgefallen:
8. Deine Operatoren ++ und -- erhöhen/verringern nicht(!), wie man erwarten müsste, um 1, sondern sie beziehen sich nur die letzte Nachkommastelle.

[stefan2008]

@Kritiker2000
Ich gebe zu, bei den meisten Dingen hast Du recht. Meine Bibliothek hat schon Verbesserungsbedarf. Aber auf der anderen Seite, gibt es Eigenschaftswerte zurück, das man von Standarddatentypen nicht erwaten kann. Zum Beispiel, kann man abfragen ob die Zahl gerade, ungerade oder Nachkommastellen enthält.

[stefan2008]

@Kritiker2000
Mit den ++ und -- Operatoren wollte ich die Zahl mit den kleinstmöglichen Zahl, je nach dem wo sich die kleinste Zahl befindet, addieren / subtrahieren.
Ich dachte es wäre besser so.

Ich habe viel Arbeit und Ideen reingesteckt. Soll ich jetzt alles vernichten?

[stefan2008]

Was würdest Du als Namen vorschlagen?

[Tippgeber]

Man soll die Operatorüberladung nicht misbrauchen und du tust das. Benutze die Operatoren so wie man sie gewohnt ist und nicht wie du es gerade für sinnvoll hälst. Das verwirrt andere nur.

Ist doch deine Klasse, wenn du sie nicht so ändern willst, wie die Mehrheit es sich wünscht, dann ist das doch deine Entscheidung.

Ich persönlich sehe den Sinn hinter deinen Ideen nicht. Wenn ich solch eine Klasse schreiben würde, dann hätte ich
a) keine Beschränkung der Vor-/Nachkommastellen (höchstens Schrittweiten die eine bessere Performance mit sich bringen)
b) möglichst gute Performance

Was hat ein Programmierer denn davon, dass der PC extrem ineffizient rechnet, so wie wir? Ich benutze den PC doch genau dafür, da er es besser kann wie ich.
Deshalb würde ich eine Basis wie 256 wählen und nicht die 10er Basis.
Als zugrunde liegende Datenstruktur würde ich mir überlegen ob ich Vorteile von einem std::bitset oder std::vector< bool > hätte, ansonsten ganz normal ein std::vector< uint8_t >, wobei uint8_t ein geeignetes typedef wäre auf einen 8Bit unsigned Typen.
Wenn es für die Performance keinen Unterschied macht würde ich statt 8Bit pro Byte allgemein 2^(Bits pro Byte) als Basis wählen.

Nur so ein paar Ideen. Mir ginge es eher um die programmiertechnische Herausforderung bei solch einer Klasse, da ich diese eh nie selber nutzen würde und auf was fertiges (besseres) zurückgreifen würde.

[stefan2008]

Ja, es stimmt. Wenn ich mit mehr als ein Operator rechne beansprucht es sehr viel Zeit. Ich bin nicht gerade ein guter Programmierer, da ich mir alles selbst beigebracht und nicht studiert habe.
Eine Frage habe ich aber noch. Ein Bool ist ja ein Bit groß. Stimmt es, dass der CPU den Bool-Wert trotzdem Byteweise durchführt? Ich frage nur, weil es mich interessiert, ob ein Bool genauso schnell wie ein Long Integer gelesen wird.

[Chuck]

Ein "bool" ist in C++ ein Byte groß. Brauch also genauso lange wie
ein "char", "short", "int" oder "long" in C++ um verarbeitet zu werden.

[Tippgeber]

Chuck schrieb:

Ein "bool" ist in C++ ein Byte groß. Brauch also genauso lange wie
ein "char", "short", "int" oder "long" in C++ um verarbeitet zu werden.

Die Größe eines Bools ist nicht so strikt festgelegt um dem Compiler Spielraum zur Optimierung zu geben, so kann er zum Beispiel mehrere Bools in ein einzelnes Byte packen, oder die Wortbreite der Architektur verwenden um die beste performance zu ermöglichen.

[Chuck]

Wäre aber genauso schnell, wie ein einzelnes "int" zuverarbeiten *Ausrede such*.