Angenommen ich habe die Zahl 3 Millionen ^5 oder ^6 oder ^7 ... Wie bekomme daraus die 3 Millionen zurück, also qasi wie berechnet man z.B. die 7. Wurzel aus 3.000.000^7 (klar, 3 Millionen kommen raus, aber wie kann ich das ausrechnen wenn ich es nicht vorher weiß)? Ich weiß, daß man das auch umschreiben kann x=Riesenzahl^(1/7), aber wie berechne ich das in Assembler auf einem µC, der bestenfalls 32 Bit Register und keinen wirklichen Befehl dafür hat?
Das einfachste ist, so wie der Mensch es machen würde: https://www.tinohempel.de/info/mathe/wurzel/wurzel.htm
log() .. div N .. 10^() respektive ln() .. div N .. exp()
> Das einfachste ist, so wie der Mensch es machen würde:
Dieses Verfahren scheint schwieriger zu werden wenn es NICHT die
Quadratwurzel sondern die x-te sein soll.
3000000^7=2,187e+45, dafür braucht man 151 Bits, also 19 Bytes. Du musst also eine MUL-Routine schreiben, die solche Zahlen schafft. Dafür brauchst Du 19*19=361 MULs und etliche ADDs. Für 32x32->64 habe ich es mal (vor 11 Jahren) hier realisiert: Beitrag "Rechnen mit AVR" Dann mit binärer Suche, sollte nicht so schwer sein. Beitrag "Rechnen mit extrem großen Zahlen"
Ben B. schrieb: > Ich weiß, daß man das auch umschreiben kann x=Riesenzahl^(1/7), > aber wie berechne ich das in Assembler auf einem µC, der bestenfalls 32 > Bit Register und keinen wirklichen Befehl dafür hat? Indem man eine Bibliothek für hohe Genauigkeit einsetzt. http://www.nongnu.org/hpalib/ Oder als Anwendung unter Linux den bc: http://www.pro-linux.de/artikel/2/909/der-basic-calculator-bc.html
Kann man sich nach etwas ueberlegen fuer BCD oder Binaer mit beliebig vielen Stellen selbst zusammenkloppen.
Sapperlot W. schrieb: > Kann man sich nach etwas ueberlegen fuer BCD oder Binaer mit beliebig > vielen Stellen selbst zusammenkloppen. Oder nach "Arbitrary-precision arithmetic" googeln. Da hat es auch in der deutschen WP einen Artikel -> https://de.wikipedia.org/wiki/Langzahlarithmetik IMHO der mit Abstand schlechteste Artikel der dt. WP, weil er nahezu nix erklärt, nur von Pontus nach Pilatus verlinkt.
"Riesige" Zahlen lassen sich mit den normalen Bibliotheken (C, C++) nicht bearbeiten. Aus diesem Grunde wird es wohl nichts helfen als auf Bibliotheken wie: http://www.nongnu.org/hpalib/ und ähnliche zurückzugreifen. Das "übliche" Format, das in Bibliotheken in Form von "Float" und Konsorten verwendet ist zwar relativ genau, aber nicht exakt. Allerdings sollte man bei der Umkehrrechnung großer Zahlen und Exponenten auf die "natürlichen" Grenzen bzw. Ungenauigkeiten achten.
Sapperlot W. schrieb: > Kann man sich nach etwas ueberlegen fuer BCD oder Binaer mit beliebig > vielen Stellen selbst zusammenkloppen. Skizziere bitte deine Überlegungen zum Ziehen der n Wurzel aus großen Zahlen (siehe Eingangsbeitrag).
Also den Hinweg würde ich einigermaßen problemlos schaffen. Wenn man bei nicht ganz so großen Zahlen bleibt, z.B. unter 2^128, kann z.B. der x86 im 64-bit-Modus direkt in diesen Bereich hinein multiplizieren und man könnte diese Multiplikation in einer Schleife ausführen um so die Potenz zu berechnen. Vielleicht nicht die schnellste Methode, würde aber funktionieren. Aber der Weg zurück macht mir Schwierigkeiten - durch die wiederholte Addition kann man die Schleife nicht einfach rückwärts ablaufen lassen, da man ja nicht weiß durch welchen Wert man teilen muß.
Obacht bei der HPALIB: Diese kennt (intern und extern) nur eine Art zu runden, nämlich Rundung in Richtung null.
Ben B. schrieb: > Wenn man bei nicht ganz so großen Zahlen bleibt, z.B. unter 2^128, kann > z.B. der x86 im 64-bit-Modus direkt in diesen Bereich hinein > multiplizieren und man könnte diese Multiplikation in einer Schleife > ausführen um so die Potenz zu berechnen. Wenn du zusätzlich noch eine Vergleichsroutine für 128 Bit hast, die ja leicht zu implementieren ist, eProfi schrieb: > Dann mit binärer Suche Das ist vielleicht nicht die effizienteste Methode, aber leicht zu implementieren.
Wie meinst Du das? Solange probieren bis man einmal drunter und einmal drüber geschossen hat? Wäre vom Prinzip her denkbar, aber das find ich wirklich ineffizient. Gibts da nichts besseres?
Wenn du eine Funktion hast (in deinem Fall die Potenzfunktion) kannst du die inverse Funktion (Wurzelziehen) durch sukzessive Approximation (bitweise Annäherung) erreichen. Das geht im Prinzip wie bei einem solchen Analog-Digital-Wandler, nur dass statt dem Vergleich des Analogwerts mit dem Zwischenwert ein Vergleich der Potenz des Zwischenwertes mit dem Radikand stattfindet.
Ben B. schrieb: > Wie meinst Du das? Solange probieren bis man einmal > drunter und einmal drüber geschossen hat? So ähnlich. > Wäre vom Prinzip her denkbar, aber das find ich > wirklich ineffizient. Gibts da nichts besseres? Selbstverständlich gibt es besseres. Zum Beispiel der Weg, der im dritten Beitrag skizziert wurde.
Possetitjel schrieb: > Selbstverständlich gibt es besseres. > Zum Beispiel der Weg, der im dritten Beitrag skizziert > wurde. Sapperlot W. schrieb: > log() .. div N .. 10^() respektive ln() .. div N .. exp() Der Weg über Logarithmus und Exponentialfunktion wäre vielleicht schneller auf einem Prozessor mit FPU. Auf einem µC vermutlich nicht. Vor allem aber ist der Weg nicht exakt, sondern nur eine Annäherung, während bei der sukzessiven Approximation auch immer eine exakte Wurzel herauskommt, wenn der Radikand die Potenz einer Ganzzahl ist.
Kannst Du diesen Weg bitte näher beschreiben, so daß man ihn ohne Doktor in Mathematik versteht?
Ben B. schrieb: > Wie meinst Du das? Solange probieren bis man einmal drunter und einmal > drüber geschossen hat? Ja. Pro Iteration, in der testweise die n-te Potenz des bisherigen Ergebnis berechnet werden muss, wird 1 Bit des Ergebnisses bestimmt. Um also die n-te Wurzel aus einer 128-Bit-Zahl zu berechnen, muss bis zu 64-mal die n-te Potenz einer 64-Bit-Zahl berechnet werden. Diese Methode wird oft zur Bestimmung der ganzzahligen Quadratwurzel verwendet, wobei eine Quadrierung natürlich deutlich schneller vonstatten geht als eine Potenzierung. Wenn die CPU keinen schnellen Multiplizierer hat, kann man die Quadrierung unter Verwendung des jeweils letzten Ergebnisses mit wenigen Additionen und Bitshifts realisieren, so dass das Verfahren immer noch ziemlich schnell ist, aber eben leider nur für Quadratwurzeln. Eine andere bereits vorgeschlagene Methode wäre, das ganze in Floating- Point unter Verwendung der Funktionen log und exp zu machen. In C wäre damit die n-te Wurzel aus x y = exp(log(x) / n); oder einfach y = pow(x, 1.0 / n); Dabei ist aber nicht garantiert, dass bei "aufgehender" Wurzel das Ergebnis auch tatsächlich exakt richtig ist. Ein minimaler Rundungsfehler schleicht sich fast immer ein. Da die Berechnung mit Floating-Point-Arithmetik eigentlich naheliegend ist, bin ich davon ausgegangen, dass du sie nicht als Option siehst. Darf man frage, wozu du diese Berechnung benötigst?
Yalu X. schrieb: > Um > also die n-te Wurzel aus einer 128-Bit-Zahl zu berechnen, muss bis zu > 64-mal die n-te Potenz einer 64-Bit-Zahl berechnet werden. Das gilt nur für n=2 also die Quadratwurzel. Bei n=4 wäre es nur noch bis zu 32-mal die 4. Potenz einer 32-Bit-Zahl. Man kann relativ schnell aus dem ersten gesetzten Bit des Radikanden berechnen, wie groß die Wurzel maximal in Bits sein kann. Erst da muss man mit der Rechnerei anfangen. Dadurch reduziert sich die Zahl der Aufrufe der Potenzfunktion drastisch, gerade bei höherem n.
:
Bearbeitet durch User
Jobst Q. schrieb: > Man kann relativ schnell aus dem ersten gesetzten Bit > des Radikanden berechnen, wie groß die Wurzel maximal > in Bits sein kann. Richtig. Anders ausgedrückt: Man bestimmt einen Schätzwert für den (binären) Logarithmus.
Jobst Q. schrieb: > Yalu X. schrieb: >> Um >> also die n-te Wurzel aus einer 128-Bit-Zahl zu berechnen, muss bis zu >> 64-mal die n-te Potenz einer 64-Bit-Zahl berechnet werden. > > Das gilt nur für n=2 also die Quadratwurzel. Bei n=4 wäre es nur noch > bis zu 32-mal die 4. Potenz einer 32-Bit-Zahl. Stimmt. Das war ein Denkfehler meinerseits. Damit wird die Methode mit zunehmendem n nicht aufwendiger, wie ich zunächst gedacht hatte, sondern genau das Gegenteil ist der Fall.
Fuer den Logarithmus : http://www.ibrtses.com/embedded/logarithms.html es ist viel einfacher als es scheint. Nun muss man nur noch mit beliebig grossen Zahlen, die N Byte lang sind arbeiten koennen.
Wenn ich mich recht erinnere, dann macht man sowas mit Ganzzahlarithmetik, um die Rundungsfehler nicht ins Unendliche laufen zu lassen. Dazu braucht man erst mal eine geeignete Klasse und nicht unerhebliche Kenntnisse aus der Zahlentheorie, um durch bekannte Abschätzungen den Rechenaufwand in Grenzen zu halten. Auch die zuletzt genannten Logarithmusgeschichten длинний зелёний тролль schrieb: > es ist viel einfacher als es scheint. Nun muss man nur noch mit beliebig > grossen Zahlen, die N Byte lang sind arbeiten koennen. kranken massiv an den Rundungsfehlern. Es gibt eben auf einem Rechner keine beliebig großen Zahlen! es sei denn, man rechnet eben mit Ganzen Zahlen und weiß, was mann tut. Denke einfach mal daran, dass du mit Gleitkommazahlen niemals auf "0" checken kannst. Gruß Rainer
Man kann zB mit Festkommazahlen arbeiten. Nehmen wir zB 32 byte vor dem Komma und 8 byte nach dem Komma. Ob man die Nachkommazahlen verwendet oder nicht ist unwesentrlich mehr Aufwand.
Yalu X. schrieb: > Ben B. schrieb: >> Wie meinst Du das? Solange probieren bis man einmal drunter und einmal >> drüber geschossen hat? > > Ja. Pro Iteration, in der testweise die n-te Potenz des bisherigen > Ergebnis berechnet werden muss, wird 1 Bit des Ergebnisses bestimmt. Um > also die n-te Wurzel aus einer 128-Bit-Zahl zu berechnen, muss bis zu > 64-mal die n-te Potenz einer 64-Bit-Zahl berechnet werden. Das geht besser. Jedem Abiturienten sollte das Newton-Verfahren zur iterativen Bestimmung der Quadratwurzel bekannt sein. Das Verfahren ist zwar erst ca. knapp 4000 Jahre bekannt [1], aber dennoch ;) Und in jedem einschlägigen Fachbuch (oder notfalls bei Wikipedia[2]) findet man die Erweiterung auf beliebige Wurzeln. Das Verfahren konvergiert für gutmütige Probleme (die n-te Wurzel zählt darunter) quadratisch, verdoppelt also mit jedem Schritt die Anzahl gültiger Stellen. [1] siehe [2] unter Quadratwurzel [2] https://de.wikipedia.org/wiki/Newton-Verfahren
Axel S. schrieb: > Jedem Abiturienten sollte das Newton-Verfahren zur iterativen > Bestimmung der Quadratwurzel bekannt sein. [...] > > Das Verfahren konvergiert für gutmütige Probleme (die n-te > Wurzel zählt darunter) quadratisch, [...] Jedem Abiturienten sollte klar sein, dass solche Konvergenz- aussagen nur für GUTE Startwerte gelten. Um die Größenordnung zu finden, ist das Verfahren ungeeignet. (Womit wir wieder beim Logarithmus wären.)
Possetitjel schrieb: > Axel S. schrieb: > >> Jedem Abiturienten sollte das Newton-Verfahren zur iterativen >> Bestimmung der Quadratwurzel bekannt sein. [...] >> >> Das Verfahren konvergiert für gutmütige Probleme (die n-te >> Wurzel zählt darunter) quadratisch, [...] > > Jedem Abiturienten sollte klar sein, dass solche Konvergenz- > aussagen nur für GUTE Startwerte gelten. Im Allgemeinfall ja. Spezifisch für die monotone(!) Wurzelfunktion ist der Startwert für die Konvergenz nicht ausschlaggebend. Darüber hinaus ist es trivial, einen guten Startwert für die n-te Wurzel zu finden: einfach den Radikand um n Bits nach rechts schieben. PS: Korrektur. Nicht um n Bits. Ausgehend davon, daß das k-te Bit das höchste gesetzte Bit ist, muß man die Anzahl der Bits (n-1)mal halbieren. Wenn bspw. das höchste gesetzte Bit das 100ste ist, muß man man für die 2. Wurzel um 50 Bit und für die 3. Wurzel um 75 Bit rechts schieben.
:
Bearbeitet durch User
Ben B. schrieb: > x=Riesenzahl^(1/7) Umformen: x^7 = Riesenzahl <=> x^7 - Riesenzahl = 0 bzw. mit R für Riesenzahl: x^7 - R = 0 und danach Newton: Axel S. schrieb: > Das geht besser. Jedem Abiturienten sollte das Newton-Verfahren zur > iterativen Bestimmung der Quadratwurzel bekannt sein. Das Verfahren ist > zwar erst ca. knapp 4000 Jahre bekannt [1], aber dennoch ;) Und in jedem > einschlägigen Fachbuch (oder notfalls bei Wikipedia[2]) findet man die > Erweiterung auf beliebige Wurzeln. > > Das Verfahren konvergiert für gutmütige Probleme (die n-te Wurzel zählt > darunter) quadratisch, verdoppelt also mit jedem Schritt die Anzahl > gültiger Stellen. > > [1] siehe [2] unter Quadratwurzel > [2] https://de.wikipedia.org/wiki/Newton-Verfahren Possetitjel schrieb: > Jedem Abiturienten sollte klar sein, dass solche Konvergenz- > aussagen nur für GUTE Startwerte gelten. > > Um die Größenordnung zu finden, ist das Verfahren ungeeignet. > (Womit wir wieder beim Logarithmus wären.) An diesem Einwand habe ich so meine Zweifel. Ja, Newton konvergiert nicht immer und überall für alle Funktionen, das sollte man sich merken aber bitte für welche Startwerte soll denn eine Funktion x^n - R = 0 divergieren? für x>0 ist die Funktion immer streng monoton steigend, d.h. es gibt keine lokalen Extrema. Außerdem gibt es für x>0 und R>0 genau eine einzige Nullstelle. Startet man mit einem positiven Wert, dann konvergiert das Newton-Verfahren ziemlich sicher gegen die positive Lösung.
Axel S. schrieb: > PS: Korrektur. Nicht um n Bits. Ausgehend davon, daß das k-te Bit das > höchste gesetzte Bit ist, muß man die Anzahl der Bits (n-1)mal > halbieren. Wenn bspw. das höchste gesetzte Bit das 100ste ist, muß man > man für die 2. Wurzel um 50 Bit und für die 3. Wurzel um 75 Bit rechts > schieben. <seufz> immer noch falsch. Wenn man eine Binärzahl, deren höchstes gesetztes Bit das k-te ist, zur n-ten Potenz erhebt, dann ist da höchstens das k*n-te Bit gesetzt. Für das Beispiel mit dem Radikant mit 100 Bit kann die 3. Wurzel maximal 33 Bit haben. Man muß also um 67 Bit nach rechts schieben. Sofern man nicht gleich mit 2^33 als Startwert rechnen will.
Axel S. schrieb: > Possetitjel schrieb: >> Axel S. schrieb: >> >>> Jedem Abiturienten sollte das Newton-Verfahren zur iterativen >>> Bestimmung der Quadratwurzel bekannt sein. [...] >>> >>> Das Verfahren konvergiert für gutmütige Probleme (die n-te >>> Wurzel zählt darunter) quadratisch, [...] >> >> Jedem Abiturienten sollte klar sein, dass solche Konvergenz- >> aussagen nur für GUTE Startwerte gelten. > > Im Allgemeinfall ja. Spezifisch für die monotone(!) Wurzelfunktion > ist der Startwert für die Konvergenz nicht ausschlaggebend. Ich frage mich -- allmählich wirklich verzweifelt --, was an meinen Aussagen so unverständlich ist. Der Startwert ist sehr wohl für die KONVERGENZGESCHWINDIGKEIT ausschlaggebend. Probiere es aus. Die reklamierte quadratische Konvergenz setzt erst ein, wenn der Näherungswert schon ziemlich gut ist. Für schlechte Näherungswerte wird Newton zur fortgesetzten Halbierung. > Darüber hinaus ist es trivial, einen guten Startwert für > die n-te Wurzel zu finden: einfach den Radikand um n Bits > nach rechts schieben. Ja -- jetzt zum dritten Mal: Damit sind wir wieder beim binären Logarithmus. Anzahl der Binärstellen zählen, durch die Ordnung der Wurzel teilen und eine Eins entsprechend oft nach links schieben. Das ist dann ein ziemlich guter Startwert.
Liebe Leute, auch die entscheidende Frage, ob Gauss oder Newton, bringt euch der Lösung nicht weiter. Was immer auch Din und 64-Bit-Float sagen, es ist Quatsch! Ihr müßt mit ganz anderen Algorithmen antreten. Aber das ist dem TO wahrscheinlich eh egal... Gruß Rainer
Und dem TO rate ich jetzt mal, besser in entsprechende Foren zu schaun, große Zahlen sind nix für den Compi...glaub es mir! Rainer
und ich kann es mir nicht verkneifen...3Mio ist keine große Zahl... Gruß Rainer
noch ein Beispiel...die Algorithmen, die Pi auf hundertausende Stellen ausrechen, rechnen nicht mit Iso...und 10 Bits nach links verschieben...ja ja... Gruß Rainer
Rainer V. schrieb In 4 direkt aufeinanderfolgenden Beiträgen nur Gefasel. Könntest du das vielleicht mal lassen? Wenn du unbedingt etwas von dir geschriebenes lesen willst, dann schreib halt ein Buch.
> und ich kann es mir nicht verkneifen...3Mio ist keine große Zahl... Aber 3Mio ^6 oder ^7 ist eine verdammt große Zahl. Wenn ich jetzt darlege wofür ich das "brauche" wirds sehr ausschweifend. Aber ich muß auch zugeben mich ärgert ein wenig, daß jeder "dumme Taschenrechner" das problemlos beherrscht und ich selber habe nicht mal eine richtig gute Idee. Das hätte ich gerne geändert. > Anzahl der Binärstellen zählen, durch die Ordnung der Wurzel teilen > und eine Eins entsprechend oft nach links schieben. > Das ist dann ein ziemlich guter Startwert. Erreiche ich dadurch eine sichere obere oder untere Grenze für den gesuchten Wert oder ist das nur ein Schuss ins Blaue, der sowohl über als auch unter dem gesuchten Ergebnis liegen kann?
>> Anzahl der Binärstellen zählen, durch die Ordnung der >> Wurzel teilen und eine Eins entsprechend oft nach links >> schieben. Das ist dann ein ziemlich guter Startwert. >Erreiche ich dadurch eine sichere obere oder untere >Grenze für den gesuchten Wert oder ist das nur ein >Schuss ins Blaue, der sowohl über als auch unter dem >gesuchten Ergebnis liegen kann? Na. Was denkst du denn ? Nachvollzogen ? 1 Million = 2^20 : = 20 binaer stellen 3 wurzel : 20 div 3 = 6..7 2^6 .. 2^7 : 64 .. 128 Kommt doch hin
Sapperlot W. schrieb: >>> Anzahl der Binärstellen zählen, durch die Ordnung der >>> Wurzel teilen und eine Eins entsprechend oft nach links >>> schieben. Das ist dann ein ziemlich guter Startwert. > >>Erreiche ich dadurch eine sichere obere oder untere >>Grenze für den gesuchten Wert oder ist das nur ein >>Schuss ins Blaue, der sowohl über als auch unter dem >>gesuchten Ergebnis liegen kann? > > Na. Was denkst du denn ? Nachvollzogen ? Offenbar nicht. Sehr ärgerlich. > 1 Million = 2^20 : = 20 binaer stellen > 3 wurzel : 20 div 3 = 6..7 > 2^6 .. 2^7 : 64 .. 128 > > Kommt doch hin Wenn man konsequent abrundet, liegt man meistens darunter und ist höchstens gleich.
Yalu X. schrieb: > Eine andere bereits vorgeschlagene Methode wäre, das ganze in Floating- > Point unter Verwendung der Funktionen log und exp zu machen. Hmm.. du kommst aus der Furche mit den C-Bibliotheken nicht raus. Ich würde dort anders herangehen - vorausgesetzt, ich hätte dazu ein passendes float-Format zum Rechnen: Zuerst: die Zahl normieren auf 1.0 bis 2^n der Wurzel. Das geht so, daß man von der angenommenen Gleitkommazahl die Mantisse und den Exponenten separiert und sich zunächst dem Exponenten zuwendet. Für die Quadratwurzel wird er in Richtung Null halbiert, für die 3. Wurzel wird er durch 3 geteilt, für die 4. Wurzel durch 4 geteilt usw. Es muß aber immer in Richtung Null gehen, weil ja z.B. 0.5*0.5-->0.25 wird. Soweit klar? OK. Die abgetrennte Mantisse ist nun im Bereich 1.0 bis 1.9999... Da es bei obigem Exponentengewurschtel einen Rest des Exponenten geben kann, muß dieser Rest mit der abgetrennten Mantisse verrechnet werden. Bei Quadratwurzel kann der Exponentenrest ja nur 1 werden, also ergibt sich daraus und mit der Verrechnung ein Mantissenbereich von 1.0 bis 3.9999... So. jetzt haben wir: a) den neuen Exponenten des künftigen Ergebnisses b) eine Zahl in einem überschaubaren Bereich, ohne daß wir mit der Mantisse irgend etwas rechnen mußten. Abschätzung des Bereiches: Er beginnt immer bei 1.0 und endet wie folgt: Exponentenrest = 0 --> Zahl 1.0 bis 1.9999___ Exponentenrest = 1 --> Zahl 2.0 bis 3.9999___ 3. Wurzel: Exponentenrest = 0 --> Zahl 1.0 bis 1.9999___ Exponentenrest = 1 --> Zahl 2.0 bis 3.9999___ Exponentenrest = 2 --> Zahl 4.0 bis 7.9999___ usw. Was hat man damit gekonnt? Nun, man hat zum Ziehen der entsprechenden Wurzel keine riesigen Zahlen mehr vor der Nase, sondern etwas, das unabhängig von der Größe der ursprünglichen Zahl ist, so daß man einen passenden Pseudo-Divisionsalgorithmus benutzen kann. Die altbekannte Quelle für sowas (Lampe,Jorke,Wengel) hatte sowas mit dem Z80 für die Quadratwurzel mal durchexerziert. Bin jetzt aber zu faul, das alles wieder herauszukramen. W.S.
W.S. schrieb: > Hmm.. du kommst aus der Furche mit den C-Bibliotheken nicht raus. Ich > würde dort anders herangehen - vorausgesetzt, ich hätte dazu ein > passendes float-Format zum Rechnen: > ... Und wozu das alles selber programmieren, wenn es das schon fertig, vollständig und getestet als optimierten Assemblercode für verschiedene CPUs (AVR, ARM, x86 u.v.m.) gibt?
Yalu X. schrieb: > W.S. schrieb: >> Hmm.. du kommst aus der Furche mit den C-Bibliotheken nicht raus. Ich >> würde dort anders herangehen - vorausgesetzt, ich hätte dazu ein >> passendes float-Format zum Rechnen: >> ... > > Und wozu das alles selber programmieren, wenn es das schon fertig, > vollständig und getestet als optimierten Assemblercode für verschiedene > CPUs (AVR, ARM, x86 u.v.m.) gibt? Wozu suchen? Herr Binom läßt grüßen...; Ebenso Herr Intervall...
Ich habe mir die verlinkte C-Library natürlich angeschaut, aber unglücklicherweise kann ich kein C. ;-((((((( Ich kann noch etwas Basic aus C64-Zeiten, Schul-Pascal... aber richtig gut nur Assembler und PHP. Es reicht leider nicht aus, um sich in professionell geschriebenem C-Code zurechtzufinden oder dort enthaltene Funktionen für eigene Verwendungen anzupassen.
Ben B. schrieb: > Ich habe mir die verlinkte C-Library natürlich angeschaut, > aber unglücklicherweise kann ich kein C. ;-((((((( > > Ich kann noch etwas Basic aus C64-Zeiten, Schul-Pascal... aber > richtig gut nur Assembler und PHP. Es reicht leider nicht aus, > um sich in professionell geschriebenem C-Code zurechtzufinden > oder dort enthaltene Funktionen für eigene Verwendungen > anzupassen. Ich möchte Dir nicht zu nahe treten, aber es liest sich für mich eher so, dass Du mit der Mathematik auf Kriegsfuß stehst. Wurzelziehen ist nicht so viel schwieriger als die vier Grundrechenarten; das bekommt man noch von Hand implementiert.
Ben B. schrieb: > Aber 3Mio ^6 oder ^7 ist eine verdammt große Zahl. 3e6^7 ≈ 2.2e45 Die meisten Taschenrechner rechnen bis knapp 1e100, 64-Bit-FP-Zahlen gehen bis knapp 1.8e308. So groß sind deine Zahlen also auch wieder nicht. > Aber ich muß auch zugeben mich ärgert ein wenig, daß jeder "dumme > Taschenrechner" das problemlos beherrscht und ich selber habe nicht mal > eine richtig gute Idee. Das hätte ich gerne geändert. Derr Taschenrechner rechnet mit FP und nutzt für die Potenzierung (auch mit gebrochenen Exponenten) intern u.a. die schon oben genannten exp- und log-Funktion. Die musst du aber nicht selber programmieren, weil das etliche Leute vor dir schon getan haben. > Erreiche ich dadurch eine sichere obere oder untere Grenze für den > gesuchten Wert oder ist das nur ein Schuss ins Blaue, der sowohl über > als auch unter dem gesuchten Ergebnis liegen kann? Zeigt dir dein Taschenrechner untere und obere Grenzen an? Wenn nicht, ist das auch kein Problem: Zeigt er bspw. 2.187000000e+45 an und geht man davon aus, dass die letzte angezeigte Ziffer unsicher ist, dann liegen die Schranken mit 2.187999999e+45 und 2.187000001e+45 angeben. In ähnlich kannst du das auch programmieren. Wenn du ganz sicher sein möchtest, betrachtest du die zweitletzte Ziffer ebenfalls als unsicher, so dass die Schranken bei 2.187999990e+45 und 2.187000010e+45 liegen. Ben B. schrieb: > Ich habe mir die verlinkte C-Library natürlich angeschaut, aber > unglücklicherweise kann ich kein C. ;-((((((( Dann suche halt Routinen in Assembler. Viele FP-Bibliotheken sind Open-Source. Brauchst du Hilfe bei der Bedienung von Google, oder wo liegt das Problem?
> Ich möchte Dir nicht zu nahe treten, aber es liest sich > für mich eher so, dass Du mit der Mathematik auf Kriegsfuß > stehst. > > Wurzelziehen ist nicht so viel schwieriger als die vier > Grundrechenarten; das bekommt man noch von Hand implementiert. Schön wenn's für Dich so einfach ist und Du die 93. Wurzel aus einer beliebigen 500-Bit-Zahl nach 20 Sekunden im Kopf berechnet hast. Allerdings frage ich mich dann was diese nutzlosen Kommentare sollen - wie ich schon schrieb, man kann nicht alles wissen. Wenn Du einen Vergleich haben willst, lass uns z.B. einen im Judo machen. Vielleicht geht's Dir dann ähnlich wie mir in der Zahlentheorie und auch schon ein paar Jahre aus der Schule raus - wonach ich eigenartigerweise nie wieder eine Wurzel schriftlich errechnen mußte. Danke für Dein Verständnis, wenn der Stoff dann nicht mehr so taufrisch ist. Es ist auch mal wieder typisch für dieses Forum, daß man jetzt schon von der Moderation als grenzdebil und unfähig zur Benutzung von Google hingestellt wird. Ihr löscht doch sonst auch jede kleinste dumme Bemerkung, aber ihr selber dürft das oder wie?! Ich hab bei Google gesucht, auch nach Assembler-Routinen. Ich hab auch gefunden - aber nichts, was mit Zahlen zurechtkommt, die nicht mehr in die Standardregister passen bzw. wo deswegen die FPU nicht mehr mit umgehen kann. Für µCs hab ich erst recht nichts in diesen Bereichen gefunden. Mag vielleicht daran liegen, daß wenige µCs n-te Wurzeln berechnen müssen, weiß ich nicht. Bis 32 Bit alles schön, da kann Google helfen. Aber 128 Bit oder mehr? Da verließen sie ihn. Naja wie dem auch sei - danke für die konstruktiven Beiträge. Aber bevor ich mir jetzt weitere beleidigende Bemerkungen bieten lassen soll gebe ich mich mit der Annährungsmethode zufrieden, auch wenns gefühlt eine der ineffizientesten ist. Und in einem Punkt habt ihr wahrscheinlich recht - das hätte ich irgendwann auch alleine hinbekommen.
Ich komischer Weise konnte der C64 schon mit sehr, sehr großen Zahlen umgehen.
Zu Doof schrieb: > Ich komischer Weise konnte der C64 schon mit sehr, sehr großen Zahlen > umgehen. Der Satz zeigt, dass du wirklich "Zu Doof" bist.
Wer Fehler findet darf und soll sie behalten. Sachlich! Was ist an meiner Aussage falsch? Als Gast kann ich Fehler nämlich nicht korrigieren...
Zu Doof schrieb: > Als Gast kann ich Fehler nämlich nicht korrigieren... Du hast einen Nick, der zu dir passt.
Ben B. schrieb: > Es ist auch mal wieder typisch für dieses Forum, daß man jetzt schon von > der Moderation als grenzdebil und unfähig zur Benutzung von Google > hingestellt wird. Ich wollte dich nicht als grenzdebil hinstellen, aber ich verstehe wirklich nicht (mehr), wo dein konkretes Problem liegen könnte. Anderen geht es wohl ähnlich, sonst wäre sicher schon längst eine für dich akzeptable Lösung gefunden worden. Ben B. schrieb: > Ich hab auch gefunden - aber nichts, was mit Zahlen zurechtkommt, die > nicht mehr in die Standardregister passen bzw. wo deswegen die FPU > nicht mehr mit umgehen kann. Die größten Zahlen, von denen du die n-te Wurzel berechnen möchtest, liegen deiner eigenen Aussage nach im Bereich von 3.000.000^7. Als Integerzahl dargestellt, werden dafür mindestens 151 Bits benötigt, das ist richtig. Als Floating-Point-Zahl reichen dafür 64 Bits locker. Wie ich oben geschrieben habe, lassen sich damit Zahlen bis fast 1.8e308 darstellen. Du kannst damit also bspw. sogar 3.000.000^47 ausrechnen, und das Ergebnis passt immer noch in ein 64-Bit-Register einer FPU. Da du bisher noch keinen Grund gegen die Floating-Point-Arithmetik genannt hast, gehe ich davon aus, dass sie prinzipiell eine Option für dich darstellt, dir aber ihre Implementierung Schwierigkeiten macht, die zugegebenermaßen nicht trivial ist. Als Tipp, um dieses Problem zu umgehen, verwies ich auf fertige Open-Source-Bibliotheken. Da diese meist in Assembler geschrieben sind, brauchst du keinerlei C-Kenntnisse, um sie anzuwenden, und Assembler beherrschst du ja nach eigener Aussage. Der nächste Schritt wäre also, im Netz nach so einer FP-Bibliothek zu suchen. Wenn ich dich richtig verstehe, hast du bisher nur nach Big- Integer-Bibliotheken gesucht. Ich kann mir vorstellen, dass die meisten (evtl. sogar alle) keine Routine zur Berechnung der n-ten Wurzel enthalten, und dass du deswegen bei der Suche erfolglos warst. Vielleicht hast du auch schon nach einer FP-Bibliothek gesucht und keine gefunden. Solche Bibliotheken sind oft nicht isoliert, sondern bspw. als Bestandteil der Laufzeitbibliothek von höheren Programmiersprachen verfügbar. Da du mit höheren Programmiersprachen nichts am Hut hast, dachte ich, du bei der Suche evtl. Hilfe gebrauchen könntest. Das ist aber offensichtlich nicht der Fall, sonst wäre deine Reaktion anders ausgefallen. Woran hängt es also? Das weiß im Moment niemand außer dir. Vielleicht solltest du einfach noch einmal in dich gehen und überlegen, welche Informationen du noch herausrücken möchtest, damit wir dein Problem besser verstehen.
Ben B. schrieb: > Aber bevor ich mir jetzt weitere beleidigende Bemerkungen > bieten lassen soll [...] Ich weiss nicht, welches Problem Du hast; ich wollte Dir dennoch rückmelden, dass ich DEIN Verhalten als beleidigend empfinde. Vor Dir wurde in den Grundzügen alles Wissen ausgebreitet, das man fürs Wurzelziehen benötigt, und es gab keine positive Reaktion von Dir. Also hatte ich den Verdacht, dass es nicht an der programmier- technischen Seite, sondern an der Mathematik hängt. Auf meine entsprechende Frage hin werde ich beschimpft. Was soll das?
...wobei ich anmerken möchte, dass die meisten mir bekannten Taschenrechner (z.B. von TI) intern mit BCD arbeiten, um Rundungsungenauigkeiten zu vermeiden. Ob das für neuere Billigrechner auch gilt, weiß ich aber nicht.
Also nur um das nochmal darzulegen. Die 3Mio^7 waren nur ein Beispiel, wie man auf eine verdammt große Zahl kommt. Es hätten auch 5Mio^9 oder meiner wegen die Anzahl Sandkörner am Strand vom El Arenal sein können. Oder die Anzahl Atome im Universum, falls tatsächlich jemand die Sandkörner zählen können möchte und feststellt so viele sind's gar nicht. Einfach nur eine riesengroße Zahl. Die Strategie zum Wurzel ziehen aus sowas sollte gleich sein. Was mir wirklich schleierhaft ist, wenn ich eine so große Zahl in 64 bit quetsche, wieviel Genauigkeit bleibt dann übrig? In 64 Bit passen nunmal nicht mehr als 64 Bit rein, und manche Zahlenwerte lassen sich sowieso nicht genau binär darstellen. Es ist auch nicht unbedingt trivial, ein fremdes Assemblerprogramm auf seine eigenen Bedürfnisse anzupassen. Es gibt da heute viele verschiedene Assembler, die meistens Unterschiede in der Syntax aufweisen, wodurch einer lange nicht jedes Programm assemblieren kann. Prozessorspezifische Unterschiede spielen da noch nicht mal eine Rolle. Und meistens benutzt man leider einen anderen Assembler... Dann kommt hinzu, daß solche Programme meist hoch optimiert sind und daher nicht unbedingt leichter nachvollziehbar. Und sorry: Aber wenn mir irgendwer direkt unterstellt, daß ich mit der Mathematik auf Kriegsfuß stehe weil das Wurzelziehen aus gigantischen Zahlen nicht viel schwerer als 1+1 sei, dann empfinde ICH das als beleidigend und offensiv allen gegenüber, die nicht die geborenen Zahlentheoretiker sind. Daß ich danach keine besonders große Lust auf Freundlichkeit mehr hege sollte Dir vorher klar sein und Dich nicht wundern. Wie man in den Wald rein ruft, so schallt's auch wieder raus! Der Rest wäre eine Grundsatzdiskussion über die Forengemeinschaft wenn man jetzt von von Moderatoren vorgeworfen bekommt, man sei zu faul oder zu doof für Google, mit der ich mir jetzt nicht den Sonntag versaue. Wie gesagt, mir reichen die zuvor hilfreichen Beiträge. Es ist offenbar doch nicht so leicht, als das irgendwer hier den optimalen Rechenweg weiß. Oder einen genausten/schnellsten...
So wie ich deine Frage verstanden hatte, ging es um ganzzahlige Wurzeln. Also aus Potenzen von ganzen Zahlen diese wiederherzustellen. Da halte ich die Verwendung von Floating Point Zahlen für ungeeignet, weil sie nur annähern können. Das gilt sowohl für das Berechnen über den Logarithmus als auch für das Newton-Verfahren. Ich habe dir eine Methode mit ganzen Zahlen vorgeschlagen, aber die wolltest du auch nicht, weil sie dir zu ineffizient schien. Rück doch einfach mal klarer mit deiner Aufgabe und den Bedingungen raus, dann ist dir auch besser zu helfen.
Diese Frage ist echt nicht leicht zu beantworten. Falls es ein echtes Rechenverfahren gegeben hätte, dann hätte ich dieses gerne verstanden um es auf 128 (oder mehr) Bit Integers anzuwenden. Mehr nicht. Im Moment denke ich nur über Optimierungen an den hier genannten Verfahren nach. Also z.B. ob es mit geringem Aufwand möglich ist, festzustellen, ob es überhaupt eine ganzzahlige Wurzel gibt. Wenn nicht, könnte man sich evtl. den Rest der Berechnung sparen wenn man nur die ganzzahlingen Lösungen haben möchte. Ansonsten könnte man sich einfach iterativ annähern und die Rechenzeit in Kauf nehmen. Irgendwann hat man entweder einen direkten Treffer oder schießt drüber (dann gibts keine ganzzahlige Lösung). Mit der "Bitschiebe-Methode" könnte man sich auch noch ein Stück annähern und Rechenschritte einsparen.
Ben B. schrieb: > Also nur um das nochmal darzulegen. > > Die 3Mio^7 waren nur ein Beispiel, wie man auf eine verdammt große Zahl > kommt. Es hätten auch 5Mio^9 oder meiner wegen die Anzahl Sandkörner am > Strand vom El Arenal sein können. Oder die Anzahl Atome im Universum, > falls tatsächlich jemand die Sandkörner zählen können möchte und > feststellt so viele sind's gar nicht. Einfach nur eine riesengroße Zahl. > Die Strategie zum Wurzel ziehen aus sowas sollte gleich sein. Ist sie auch. Es ist allerdings ein Unterschied, ob man die Berechnung für ganze Zahlen macht - und das meint man üblicherweise, wenn man von "riesigen" Zahlen spricht. Oder ob man mit Fließkommazahlen rechnet. Letztere decken einen sehr großen Wertebereich ab, aber eben nicht exakt. Ganzzahlen hingegen sind zwar exakt, andererseits kann man nicht aus jeder Zahl die Wurzel ziehen, weil nur ein sehr geringer Teil der Zahlen aus dem Wertebereich tatsächlich Potenzen sind. > Was mir wirklich schleierhaft ist, wenn ich eine so große Zahl in 64 bit > quetsche, wieviel Genauigkeit bleibt dann übrig? Wie wäre es dann, wenn du dich mal schlau machen würdest? Das Format von Fließkommazahlen ist normiert. IEEE 754. Du könntest schon lange wissen, wieviel Bits Mantisse das sind und wieviel Dezimalstellen das entspricht. > Es ist auch nicht unbedingt trivial, ein fremdes Assemblerprogramm auf > seine eigenen Bedürfnisse anzupassen. Es gibt da heute viele > verschiedene Assembler, die meistens Unterschiede in der Syntax > aufweisen, wodurch einer lange nicht jedes Programm assemblieren kann. Das ist vollkommen irrelevant. Arithmetische Algorithmen sind abstrakt, die kann man sowieso nicht 1:1 in Assembler hinschreiben. Wenn man mit breiteren Zahlen rechnen will als die ALU kann, werden schon die Grundrechenarten eigene kleine Programme. Deswegen ist auch die Kenntnis der Algorithmen das wichtige. > Und sorry: Aber wenn mir irgendwer direkt unterstellt, daß ich mit der > Mathematik auf Kriegsfuß stehe weil das Wurzelziehen aus gigantischen > Zahlen nicht viel schwerer als 1+1 sei, dann empfinde ICH das als > beleidigend und offensiv allen gegenüber, die nicht die geborenen > Zahlentheoretiker sind. Niemand, wirklich niemand kommt mit dem angeborenen Wissen auf die Welt, wie man Wurzeln zieht. Alle müssen das lernen. Alle können das lernen. Wenn sie bereit sind, sich die Mühe zu machen. Und eben das kann ich bei dir in keinster Weise erkennen. Du stellst hier Fragen nach hochgradig trivialen Dingen, die jedes einschlägige Fachbuch erläutert. Das meiste davon dürfte sogar bei Wikipedia nachzulesen sein. Du erwartest nicht ersthaft, daß wir dir das alles vorlesen? Oder es extra für dich noch einmal hinschreiben? [Mod: beleidigende Aussage gelöscht]
:
Bearbeitet durch Moderator
Beitrag #5168740 wurde von einem Moderator gelöscht.
Ben B. schrieb: > Die 3Mio^7 waren nur ein Beispiel, wie man auf eine verdammt große Zahl > kommt. Es hätten auch 5Mio^9 oder meiner wegen die Anzahl Sandkörner am > Strand vom El Arenal sein können. Oder die Anzahl Atome im Universum, ... oder vielleicht noch viel, viel größer. Heißt das, dass es überhaupt keine Beschränkung der Größe der Zahlen, mit den du rechnen willst gibt? Dann brauchst du einen Rechner ohne Speicherlimit, den es vermutlich nie geben wird. Ben B. schrieb: > Was mir wirklich schleierhaft ist, wenn ich eine so große Zahl in 64 bit > quetsche, wieviel Genauigkeit bleibt dann übrig? Etwa 15 Dezimalstellen. Welche Genauigkeit brauchst du denn? Jobst Q. schrieb: > So wie ich deine Frage verstanden hatte, ging es um ganzzahlige Wurzeln. Das dachte auch erst, bis diese Aussage kam: Ben B. schrieb: > Erreiche ich dadurch eine sichere obere oder untere Grenze für den > gesuchten Wert oder ist das nur ein Schuss ins Blaue, der sowohl über > als auch unter dem gesuchten Ergebnis liegen kann? Das hatte ich so verstanden, dass eine Näherungslösung in Ordnung ist, wenn man dafür Fehlergrenzen angeben kann. Ben B. schrieb: > Also z.B. ob es mit geringem Aufwand möglich ist, festzustellen, ob es > überhaupt eine ganzzahlige Wurzel gibt. Das ist eine neue Frage, für die es evtl. auch neue Antworten gibt. > Wenn nicht, könnte man sich evtl. den Rest der Berechnung sparen wenn > man nur die ganzzahlingen Lösungen haben möchte. Heißt das, du bist bspw. an der 7-ten Wurzel aus 300000 gar nicht interessiert, weil das Ergebnis 6,0596… nicht ganzzahlig ist? Ich dachte, du wolltest in diesem Fall zumindest den ganzzahligen Anteil des Ergebnisses, also 6. Ben B. schrieb: > Ansonsten könnte man sich einfach iterativ annähern und die Rechenzeit > in Kauf nehmen. Welche Rechenzeit könntest du denn in Kauf nehmen? Sooo langsam ist die iterative Methode gemessen an der Größe der damit verarbeiteten Zahlen ja auch wieder nicht. Ben B. schrieb: > Wenn ich jetzt darlege wofür ich das "brauche" wirds sehr ausschweifend. Ich glaube, das wäre wesentlich weniger ausschweifend, als wenn du hier tröpfchenweise in unpräzisen Formulierungen deine Anforderungen postest, so wie es seit Beginn dieses Threads vor 4 Tagen der Fall ist.
Nachdem sich hier, wie so oft, die "Idioten" eingeschossen haben, will ich noch einmal sagen, dass man sowas in Ganzzahlarithmetik macht! Es gibt in den diversen Programmierprachen solche Klassen und man muß einiges an Mathematik, besonders Zahlentheorie, mitbringen, um sie vernünftig anwenden zu können! Bei großen bis ganzgroßen Zahlen macht man zuerst immer eine Abschätzung des zu erwarteten Zahlenbereichs und dann versucht man einen Lösungsansatz. Gleitkommazahlen sind hier völlig ungeeignet und auf einem AVR soll es doch wahrscheinlich eh nicht laufen?! Gruß und viel Spass weiterhin.
guest...Rainer schrieb: > Nachdem sich hier, wie so oft, die "Idioten" eingeschossen haben, will > ich noch einmal sagen, dass man sowas in Ganzzahlarithmetik macht! Warum sollte man ausgerechnet für das Wurzelziehen Ganzzahlen verwenden wollen? Für den weit überwiegenden Teil der darstellbaren Zahlen existiert gar keine ganzzahlige Wurzel. Wenn du bspw. mit unsigned long long rechnest (64 Bit) dann sind von den 18446744073709551616 darstellbaren Zahlen gerade mal 4294967296 Quadratzahlen. Für die restlichen 18446744069414584320 (also: fast alle) existiert keine Quadratwurzel. Für höhere Wurzeln und längere Zahlen wird das Verhältnis immer ungünstiger. > gibt in den diversen Programmierprachen solche Klassen und man muß > einiges an Mathematik, besonders Zahlentheorie, mitbringen, um sie > vernünftig anwenden zu können! Wie kommst du auf dieses schmale Brett? Lange Ganzzahlarithmetik kann man im wesentlichen genauso verwenden wie normale Integer. Wenn die Programmiersprache Operatorüberladung bietet, praktisch ganz genauso. Die einzigen Überraschungen wird man vielleicht bei der Laufzeit erleben, etwa wenn sich die unschuldig aussehende Ausgabe einer solchen Zahl in Dezimaldarstellung plötzlich als zeitfressend erweist.
Hi, Wurzelziehen ist ein Teilgebiet. Der TO hat nach "großen Zahlen" gefragt! Ob Wurzel oder PI, ist dann egal. Axel S. schrieb: > Wie kommst du auf dieses schmale Brett? Lange Ganzzahlarithmetik kann > man im wesentlichen genauso verwenden wie normale Integer. Ja, kann man, wenn man keinen Schimmer hat. Habe jetzt keine Lust, jemandem, der immer wieder das wiederholt, was er schon hundertmal geschrieben hat, noch mal meine Aussage zu wiederholen. Mach dich mal schlau... Gruß und der TO wäre der bessere Adressat!
> Du bist ein Idiot.
Danke für das Kompliment. Über sowas freut sich ggf. der Anwalt.
So, damit bin ich hier raus, bevor euer Niveau ansteckend wird.
Danke - reicht.
guest...Rainer schrieb: > Hi, Wurzelziehen ist ein Teilgebiet. Der TO hat nach "großen Zahlen" > gefragt! Ob Wurzel oder PI, ist dann egal. Und du wirfst anderen Ahnungslosigkeit vor? LOL > Axel S. schrieb: >> Wie kommst du auf dieses schmale Brett? Lange Ganzzahlarithmetik kann >> man im wesentlichen genauso verwenden wie normale Integer. > > Ja, kann man, wenn man keinen Schimmer hat. > Mach dich mal schlau... Doppelt LOL. Ich habe mit langen Ganzzahlen schon gerechnet, da hast du wahrscheinlich noch in die Hosen gemacht. Ich habe damals sogar meine eigene BIGNUM Arithmetik geschrieben. In C++, vor über 20 Jahren und auch nur als Fingerübung nebenbei - das echte Ziel war Arithmetik mit Polynomen bis Grad ~1000 mit sehr großen ganzzahligen Koeffizienten. Wurzelziehen habe ich damals nicht implementiert. Warum auch - es ergibt ja praktisch keinen Sinn mit Ganzzahlen. Mittlerweile sehe ich das eher als Jugendsünde und würde zu einer fertigen Library greifen. Z.B. GNU MP für ganze Zahlen. Oder hfloat für hochpräzise Fließkommazahlen.
Yalu X. schrieb: > Ben B. schrieb: >> Ansonsten könnte man sich einfach iterativ annähern und die Rechenzeit >> in Kauf nehmen. > > Welche Rechenzeit könntest du denn in Kauf nehmen? Sooo langsam ist die > iterative Methode gemessen an der Größe der damit verarbeiteten Zahlen > ja auch wieder nicht. Ich habe die iterative Methode (also das Durchprobieren der einzelnen Ergebnisbits mit Big-Integer-Arithmetik) mal programmiert (wenn auch nicht in Assembler, sondern in Haskell), um einen Eindruck von der benötigten Rechenzeit zu bekommen. Für die Berechnung der 10-ten Wurzel aus einer 101-stelligen Zahl im Bereich von 1e100 braucht damit mein Laptop mit i5-6267U-Prozessor 7,8µs. Da Haskell eine Very-High-Level- Sprache ist, kann ein guter Assemblerprogrammierer die Zeit sicher noch deutlich unterbieten.
1 | import Data.Bits |
2 | |
3 | -- nthroot: berechnet den ganzzahligen Anteil der k-ten Wurzel einer |
4 | -- Zahl n nach der Methode des "bitweisen Durchprobierens" |
5 | |
6 | nthroot :: Integer -> Int -> Integer |
7 | nthroot n k = nthroot' 0 p |
8 | where nthroot' b 0 = b |
9 | nthroot' b p = nthroot' b' (p `shiftR` 1) |
10 | where b' | (b .|. p) ^ k > n = b |
11 | | otherwise = b .|. p |
12 | |
13 | p = 1 `shift` nrbits n (-1) |
14 | |
15 | nrbits 0 m = m |
16 | nrbits n m = nrbits (n `shiftR` k) (m + 1) |
17 | |
18 | -- test: überprüft, ob die 10-te Wurzel aus der 10-ten Potenz einer |
19 | -- Zahl n wieder n ergibt |
20 | |
21 | test n = nthroot (n^10) 10 == n |
22 | |
23 | -- main: wendet die obige Testfunktion auf die Zahlen 10.000.000.000 bis |
24 | -- 10.000.999.999 an |
25 | |
26 | main = do |
27 | print $ all test [10^10 .. 10^10+999999] |
Die gemessene Laufzeit von 7,8µs ist zwar nicht schlecht, trotzdem geht's mit Floating-Point noch sehr viel schneller: Mit 64-Bit-Floating- Point dauert dieselbe Berechnung auf demselben Rechner unter 59ns, was einen Geschwindigkeitsfaktor von 132 ergibt. Da die Wurzeln 11-stellig sind, sind die Ergebnisse auf 3 bis 4 Nachkommastellen genau. Wenn es nur um Ganzzahlige Ergebnisse geht, ist also noch ordentlich Reserve vorhanden. Anders sieht es aus, wenn nicht die 10-ten, sondern bspw. die 3-ten Wurzeln der 101-stelligen Zahlen berechnet werden sollen. Dann sind die Ergebnisse 34-stellig, so dass ihr ganzzahliger Anteil im 64-Bit-FP- Format nicht mehr in voller Genauigkeit dargestellt werden kann. Es gibt sicher effizientere Big-Integer-Algorithmen für die Berechnung n-ter Wurzeln als der obige. Allerdings sind diese schwieriger zu verstehen und auswendiger zu programmieren, vor allem dann, wenn man das komplett in Assembler machen möchte. Welchem von all den Verfahren man letztendlich den Vorzug gibt, hängt von der Größenordnung der Zahlen, der geforderten Genauigkeit und der zur Verfügung stehenden Rechenzeit ab. Irgendeinen Kompromiss wird man immer eingehen müssen.
Ben B. schrieb: > Und sorry: Aber wenn mir irgendwer direkt unterstellt, daß ich > mit der Mathematik auf Kriegsfuß stehe weil das Wurzelziehen > aus gigantischen Zahlen nicht viel schwerer als 1+1 sei, dann > empfinde ICH das als beleidigend und offensiv allen gegenüber, > die nicht die geborenen Zahlentheoretiker sind. Das möchte ich so nicht stehenlassen. Ich habe den Beitrag, der Dich in Rage gebracht hat, nochmal gelesen, und verstehe Deinen Ärger. Ich war auf das Rechnen mit (sehr) großen Zahlen fokussiert. Meine Aussage war: "Das Wurzelziehen (aus sehr großen Zahlen) ist nicht wesentlich schwieriger als die Grundrechenarten (mit sehr großen Zahlen). Wenn man also die Grundrechenarten für sehr große Zahlen hinbekommt, sollte man auch das Wurzelziehen für sehr große Zahlen hinbekommen." Ich bitte für die schlechte Formulierung um Entschuldigung.
Jobst Q. schrieb: > So wie ich deine Frage verstanden hatte, ging es um > ganzzahlige Wurzeln. Also aus Potenzen von ganzen Zahlen > diese wiederherzustellen. Ja, so hatte ich die Frage auch aufgefasst. > Da halte ich die Verwendung von Floating Point Zahlen für > ungeeignet, Ich nicht. > weil sie nur annähern können. Das gilt sowohl für das > Berechnen über den Logarithmus als auch für das Newton-Verfahren. Ja - und inwiefern stört das? Wenn eine nicht-ganzzahlige Wurzel herauskommt, testet man die beiden nächstliegenden ganzen Zahlen darauf, ob sie Lösungen sind. Entweder man hat dann eine ganzzahlige Lösung, oder man weiss, dass es keine gibt. (Vermutlich könnte man auch einen der beiden Tests einsparen.) Ein schnelleres und einfacheres Verfahren ist für mich kaum vorstellbar.
> Ich bitte für die schlechte Formulierung um Entschuldigung. Angenommen und dann entschuldige ich mich auch fürs direkte Zurückschießen. > Etwa 15 Dezimalstellen. Welche Genauigkeit brauchst du denn? Auf jeden Fall wollte ich direkte Treffer erkennen, also wenn eine Zahl wirklich eine x-te Potenz ist (wobei x bekannt ist). Das Problem ist ja, daß es gerade bei den höheren Potenzen nicht viele Zahlen gibt, die tatsächlich eine Potenz aus einer ganzen Zahl sind, aber selbst die paar wenigen kennt man vorher nicht. Man kann sie (durch Berechnung der Potenzen) suchen, dann sind wir wieder bei der Annäherung. Manche neuen Fragen ergeben sich aus den vorangegangenen Antworten. Mir kommt jedes Annäherungsverfahren prinzipiell erstmal langsamer vor als ein direkter Rechenweg. Muß nicht unbedingt so sein, kommt mir aber so vor. Also als Folgerung - wenn Annäherungsverfahren, wie bekommt man es schneller? Kann man Zahlenbereiche ohne großen Aufwand ausschließen, in denen man nicht suchen muß? Daher die neuen Fragen und darauf Antworten wie diese binäre Verschiebung, die meiner Meinung nach ein guter Ansatz ist. Damit kann man sich alle Tests unterhalb dieser Grenze sparen. Ich habe auch mal ein paar Tests gemacht, mein i7-2720 Laptop braucht zur Berechnung von 300k Potenzen auf bis zu 128 Bit deutlich weniger Zeit als ich zum Blinzeln. Wenn man den Code im Debugger startet, blitzt nicht mal irgendeine "läuft"-Anzeige oder ähnliches auf, so schnell ist der, obwohl ich nur das einfachste Verfahren (wiederholte Multiplikation) gewählt habe. Da gibts bestimmt auch schnelleres. Allerdings würde der x86 über 128 Bit viel an Geschwindigkeit verlieren. Er kann bis auf 128 Bit direkt multiplizieren, aber nur bis 65 Bit addieren (Reg64+C). Sprich bei Multiplikationen über 128 Bit kommen pro Multiplikations-Operation drei Additions-Operationen dazu, über 192 Bit die vierte usw. MMX konnte im 32-Bit-Modus schon recht früh (ab dem P1 MMX) die volle 64 Bit Registerbreite addieren - was der x86 heute im 64-Bit-Modus schon allein mit den Haupregistern kann. SSE/AVX usw. hat zwar 128/256 Bit Registerbreite, kann diese aber nicht "einfach" addieren. Wenn man sich den Spaß machen möchte und das auf einem 20-Mhz AVR mit 8 Bit implementiert, wird man die Laufzeit der Berechnung schon recht deutlich merken. Sinnvolle Maximalgröße... Ich glaube das ist nicht groß relevant, weil spätestens wenn man sich eine Routine schreibt, die mit Puffern im Speicher arbeitet (und nicht mehr nur mit den Prozessorregistern)... hm, wer mag mir mal schnell berechnen, welche Dezimalzahl sich mit 16GB Hauptspeicher binär abbilden ließe? ;) Die größte bekannte Primzahl ist 2^74.207.281−1 und hat 22,3 Millionen Stellen. Eine Routine, die mit Speicherpuffern arbeitet, sollte damit kein Problem haben -> völlig ausreichend.
Ben B. schrieb: > Ich habe auch mal ein paar Tests gemacht, mein i7-2720 Laptop braucht > zur Berechnung von 300k Potenzen auf bis zu 128 Bit deutlich weniger > Zeit als ich zum Blinzeln. Wenn man den Code im Debugger startet, blitzt > nicht mal irgendeine "läuft"-Anzeige oder ähnliches auf, so schnell ist > der, obwohl ich nur das einfachste Verfahren (wiederholte > Multiplikation) gewählt habe. Da gibts bestimmt auch schnelleres. In der Tat: https://de.wikipedia.org/wiki/Binäre_Exponentiation > Allerdings würde der x86 über 128 Bit viel an Geschwindigkeit verlieren. > Er kann bis auf 128 Bit direkt multiplizieren, aber nur bis 65 Bit > addieren (Reg64+C). Sprich bei Multiplikationen über 128 Bit kommen pro > Multiplikations-Operation drei Additions-Operationen dazu, über 192 Bit > die vierte usw. Naja. Mit langen Zahlen hat das aber irgendwie nichts zu tun. Da verwendet man dann auch andere Algorithmen. Entweder Karatsuba. Oder gleich FFT-Multiplikation. Andererseits kann man das auch einfach nur anwenden. GNU MP wählt den besten Algorithmus selbständig anhand der Größe der Operanden.
Ben B. schrieb: > Auf jeden Fall wollte ich direkte Treffer erkennen, also wenn eine Zahl > wirklich eine x-te Potenz ist (wobei x bekannt ist). Wieviel Speicher hast du zur Verfügung? Einen riesigen, unübersichtlichen, extrem dünn besetzten Raum kann man auch mit Tabellen erschlagen. Das oben genannte Beispiel von Axel benötigt zwar 32 GB für alle Quadratzahlen innerhalb von uint64_t, aber das Verhältnis wird für größere Potenzen besser. > Man kann sie (durch Berechnung der > Potenzen) suchen, dann sind wir wieder bei der Annäherung. Je nach Wunschgröße der Tabelle (Anzahl Stützstellen) kannst du das beliebig beschleunigen, je nach CPU-/Speichergeschwindigkeit. > Manche neuen Fragen ergeben sich aus den vorangegangenen Antworten. Mir > kommt jedes Annäherungsverfahren prinzipiell erstmal langsamer vor als > ein direkter Rechenweg. Das ist ein Trugschluss. Ein direkter Rechenweg schenkt dir die exakte Lösung (im Rahmen der Genauigkeit), eine Annäherung schenkt dir eine ungefähre Lösung in meist deutlich kürzerer Zeit (oder deutlich weniger Speicher, je nach Wahl des Kompromisses). > Muß nicht unbedingt so sein, kommt mir aber so vor. Also als > Folgerung - wenn Annäherungsverfahren, wie bekommt man es schneller? Indem man schneller konvergierende Abschätzungen nimmt. > Kann man Zahlenbereiche ohne großen Aufwand ausschließen, in > denen man nicht suchen muß? Ja, indem du den Suchraum vorher passend stückelst. "Mein Ergebnis muss irgendwo zwischen 2e20 und 3e20 liegen" ist eine gute Voraussetzung, und "in diesem Intervall ist Newton schlecht, also mach Intervallschachtelung" ist auch gut. Hängt davon ab, wieviel Aufwand du vorher bereit bist zu treiben und wie schnell du Antworten auf deine Fragen brauchst und in welcher Genauigkeit (z.B. Echtzeitanforderungen).
Ich habe übrigens nach wie vor den Eindruck, daß das in die falsche Richtung geht. Die Frage "hat x^n = y eine ganzzahlige Lösung x für gegebenes y und n?", ist eine ganz andere als "berechne x". Und mußmaßlich ist das auch noch nicht die Frage, die sich dem TE eigentlich stellt. Typischer Fall von X-Y Problem.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.