Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Umwandlung eines Bruchs in ein anderes Positionssystem


Mathematiker - So 17.02.13 21:09
Titel: Umwandlung eines Bruchs in ein anderes Positionssystem
Hallo,
für eine Zahlenspielerei, den Pi-Code http://www.cadaeic.net/picode.htm, versuche ich möglichst viele Dezimalstellen eines Bruchs, hier konkret der Näherung von Pi, in das 26ziger System umzuwandeln.
Während die Transformation einer natürlichen Zahl natürlich kein Problem ist, stoße ich hier an meine Grenzen.

Habe ich die Dezimalzifferfolge 0,abcde... gegeben, so multipliziere ich den ganzen Bruch mit der Zielbasis 26 durch. Der entstehende ganzzahlige Anteil ist meine nächste Ziffer. Mit dem gebrochenen Anteil verfahre ich wieder so usw.
Und da liegt das Problem.

In meinem Beispielprogramm benötigt mein Rechner für 10000 Ziffern 0,3 s, bei 100000 Ziffern schon 30,3 s; alles ohne Ausgabe. Rechne ich das auf mein eigentliches Ziel von mehr als 1 Milliarde Ziffern um, so dürfte die Sonne schon ein Weißer Zwerg sein, bevor ich zum Ziel kommen würde. Nun nicht ganz. Es wäre "nur" etwa 100 Jahre Rechenzeit! :mrgreen:

Kennt jemand ein schnelleres Verfahren, die Dezimalziffern eines Bruchs in ein beliebiges Positionssystem zu transformieren? :flehan: Die Behandlung der Kommastellen als riesengroße natürliche Zahl bringt nichts, da z.B. 0,14159 im 26er Sytem die Zeichenfolge [0,3HIF60...]26 besitzt, 14159 dagegen [KOF]26.

Dem Programm liegt noch eine Datei pi.000 bei, die 1 Million Nachkommaziffern von Pi enthält. Deshalb ist der Anhang auch relativ groß. Jedes Mal Pi erst ausrechnen, war mir zu aufwendig. :wink:

Vielen Dank für Hinweise und beste Grüße
Mathematiker

Rev 1: Die Ziffern werden nicht mehr nur mit der Basis, sondern mit Basis^Exponent berechnet. Der Exponent wird so gewählt, dass kein Arithmetiküberlauf entsteht.
Außerdem habe ich einen schweren Fehler entfernt. Das Programm berechnete nur die ersten Stellen korrekt.
Rev 2: Int64 wieder auf Integer geändert. Berechnung läuft schneller ab.
Rev 3: Integer gegen Cardinal getauscht, da bei kleinen Basen "Blödsinn" berechnet wurde.
Rev 4/5: zusätzlich mit Demonstration des PI-Codes.
Rev 6: deutliche Beschleunigung der Umwandlung und weitere Ergänzungen.
Rev 7: zusätzlich mit Umwandlung in PI-Code 27.


jfheins - Mo 18.02.13 00:57

Als erstes würde mir einfallen, nicht nur eine Ziffer zu extrahieren sondern gleich mehrere auf einmal. Ist vielleicht auch langsamer aber einen Versuch wäre es Wert.
==> Nicht mit 26 multiplizieren sondern mit 26^2 oder gar 26^3 und dann aus dem Ganzzahlanteil direkt bis zu 3 Ziffern errechnen.


Tranx - Mo 18.02.13 06:29

Steffen,

ich weiß nicht, wie Du es Dir vorstellst, aber leider ist ja das Problem, dass jede Dezimalziffer einen Bruchteil in dem jeweiligen Ziffernsystem darstellt:

im Zehnersystem:

0,01 = 1/10^2 = 1/100
0,0005 = 5/10^4 = 5/10000

das Gleiche im 26er:

0,01 = 1/26^2 = 1/676
0,0005 = 5/26^4 = 1/456976

wenn Du z.B. also eine (!!) x-beliebige Ziffer (im Nachkommabereich) des 10er in das 26er-System umwandeln willst, erhältst du (da 26 und 10 ja nicht nur gemeinsame Teiler haben) einen rationalen (vereinfacht, periodischen) Bruch mit mehreren Ziffern als Ergebnis. Also bei der Genauigkeit von 1 Millionen Ziffern ebenfalls eine Millionen Ziffern.

Demhingehend ist die Umwandlung der Ziffern vor dem Dezimalkomma einfacher, da es zwar auch mehrere Ziffern aus einer werden, aber die "Bruchfolge" endet bei der ersten Vorkommastelle, als Rest der Bruchrechnung:

3000 im Zehner: 3000:676 = 4 Rest 296; 296:26 = 11 Rest 10 somit ergibt sich : 3000(10) = 4BA(26)


Ich hoffe, mich verständlich gemacht zu haben.


Horst_H - Mo 18.02.13 11:48

Hallo,

wie esuser profile iconjfheins vorschlägt , habe ich es auch bei http://www.entwickler-ecke.de/viewtopic.php?p=457804 gemacht.
Die Nachkommastellen mit 1e5 multiplizieren und die entstehenden Vorkommastellen ausgeben.
Wobei Format die Umwandlung zu Basis 10 macht.

Delphi-Quelltext
1:
2:
  mult(A,100000); 
  write(Format('%.5d',[a[1]]));

Bei 200000 Stellen funktionierte das einwandfrei.
Man kann also mit 26^3= 17576 als Faktor arbeiten und so immer 3 neue Stellen bestimmen.
Ich hatte aber die Zahl als Binärzahl, wodurch der Einsatz von Assembler für die Multiplikation leicht möglich war ohne die aufwendigen DIV/MOD Rechnereien, um bei der Basis 1e6 zu bleiben.
Es gibt aber auch subquadratische Basisumwandlungen, aber wo ?
http://gmplib.org/manual/Binary-to-Radix.html

Gruß Horst


Mathematiker - Mo 18.02.13 12:06

Hallo,
vielen Dank für Eure Hinweise.

Das Multplizieren mit mehr als der Basis ist eine sehr gute Idee.
In der Revision 1 multipliziere ich jetzt mit Basis^Exponent, wobei der Exponent so gewählt wird, dass kein Arithmetiküberlauf entsteht. Für die 26 ist es 26^6, für die Basis 2 sogar 2^29.

Leider hat sich herausgestellt, dass meine Lösung einen extremen Fehler hatte. :autsch: Da ich zuwenig PI-Ziffern eingelesen habe, wurden nur die ersten Stellen korrekt berechnet.
Aufgefallen ist es mir, als ich als Basis 10 wählte und viele, viele Nullen bekam.

Schlimm ist nur, dass jetzt 10000 Stellen schon 4,1 s benötigen, 100000 Ziffern sogar 7 Minuten, d.h. es ist noch viel schlechter als vorher, trotz des größeres Faktors. :nixweiss:

Beste Grüße
Mathematiker


Gammatester - Mo 18.02.13 12:42

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Es gibt aber auch subquadratische Basisumwandlungen, aber wo ?
http://gmplib.org/manual/Binary-to-Radix.html

MPArith [http://www.wolfgang-ehrhardt.de/misc_de.html#mparith] hat auch schon seit mehr als einem Jahr eine subquadratische mp_radix_astr-Routine, basierend auf dem FastIntegerOutput-Algorithmus in Brent/Zimmermann's Buch Modern Computer Arithmetic (PDF vom Author über http://maths-people.anu.edu.au/~brent/pub/pub226.html) und halt GMP.


Horst_H - Mo 18.02.13 16:41

Hallo,

@user profile iconGammatester:
dann müsste man dies wie testen?
Stellenzahl S_10 von pi als String einlesen( die 3 zu Beginn weglassen) und zu einem mpint wandeln als rationalen Bruch RZ durch 10^S_10 teilen.
Dieses RZ mit neueBasis^neueStellenzahl multiplizieren -> RZ und den ganzzahligen Anteil GZ von RZ bestimmen.
Dieses GZ dann zur Basis neueBasis zu einem String konvertieren.

@user profile iconMathematiker zu Revision1:
Int64 ist auch wesentlich langsamer als mit 32-bit integer zu rechnen.
Muss der Übertrag nicht von unten ( groesse-1) nach oben ( 1) gerechnet werden?

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
       //Übertrag
       for q:= groesse-1 downto 1 do begin
         r := feld[q] div grenze;  
         inc(feld[q-1],r);
         dec(feld[q], r*grenze);//feld[q]:=feld[q] mod grenze; feld[q]:=feld[q]-r*grenze; 
       end;


Gruß Horst


Tranx - Mo 18.02.13 17:13

Das Problem bei der umwandlung von pi() vom Zehner in ein anderes System sind die dazu notwendigen Operatuionen mit einer Genauigkeit von 1 Millionen Stellen!!!!! Das kann man nicht durch einfaches Dividieren zweier Zahlen oder Multiplizieren derselben erreichen, weil die Genauigkeit dieses Ergebnisses bestenfalls 29 Stellen oder ähnliches beträgt. Hier muss sozusagen jede einzelne Stelle in eine Ziffernfolge des anderen Systems überführt werden. Und dann die einzelnen Ergebnisse der Überführung der einzelnen Stellen Addiert werden. Was dann wieder zu Verschiebungen einzelner Ziffen wegen Überlaufes führen kann. Aber das kann am Ende der ganzen Operation sozusagen von hinten nach vorne abgearbeitet werden. Was will ich mit letztem sagen: Angenommen man erhielte durch Addition folgende "Ziffernfolgen" im 26er System:

0, 23, 3, 56, 8, 5, 45, 5, 0, 9, 98

dann wäre die Abfolge der Bereinigungsoperation:

0, 23, 3, 56, 8, 5, 45, 5, 0, 12, 20
0, 23, 3, 56, 8, 5, 45, 5, 0, 12, 20
0, 23, 3, 56, 8, 5, 45, 5, 0, 12, 20
0, 23, 3, 56, 8, 5, 45, 5, 0, 12, 20
0, 23, 3, 56, 8, 6, 19, 5, 0, 12, 20
0, 23, 3, 56, 8, 6, 19, 5, 0, 12, 20
0, 23, 3, 56, 8, 6, 19, 5, 0, 12, 20
0, 23, 5, 4, 8, 6, 19, 5, 0, 12, 20
0, 23, 5, 4, 8, 6, 19, 5, 0, 12, 20

Endergebnis:

0, 23, 5, 4, 8, 6, 19, 5, 0, 12, 20

(Anmerkung: Durch dieAbarbeitung von Hinten nach Vorne benötigt man nur genau x Operationen für x Stellen, da ja automatisch jede Ziffer auf den Bereich 0..n-1 normiert wird. (n = Basiszahl des Zahlensystems)

Aber - wie gesagt, die Ziffern müssen - soweit ich weiß - für jede Ziffer des alten Zahlensystems im neuen Zahlensystem belegt werden. Und das kann logischerweise bei 1 Millionen Ziffern etwas dauern. Einen Vorteil hat das Ganze jedoch. Die Belegung der Ziffern des neuen Zahlensystems sollte immer eine periodische Folge ergeben, so dass man nur einmal die Periode ermitteln muss, und dann kann man einfach die Periode in die folgenden Positionen kopieren.

Aus:http://de.wikipedia.org/wiki/Rationale_Zahl#Dezimalbruchentwicklung

Jede reelle Zahl lässt sich einer Dezimalbruchentwicklung zuordnen. Bemerkenswerterweise besitzt jede rationale Zahl eine periodische Dezimalbruchentwicklung, jede irrationale Zahl dagegen eine nichtperiodische (beachte: eine endlich abbrechende Dezimalbruchentwicklung ist ein Spezialfall der periodischen Dezimalbruchentwicklung, bei der sich nach der endlichen Ziffernfolge die Dezimalziffer 0 oder 9 periodisch wiederholt).

Der sich wiederholende Teil wird mit einem Überstrich kenntlich gemacht.

Beispiele sind:
1/3 = 0,3 = 0,33333… = [0,01]2
9/7 = 1,285714 = 1,285714 285714… = [1,010]2
1/2 = 0,50 = 0,50000… = [0,10]2
1 = 1/1 = 1,0 = 0,9 = 1,00000… = 0,99999… = [1,0]2 = [0,1]2

In den eckigen Klammern sind die entsprechenden Entwicklungen im Dualsystem angegeben. Mehrstellige Perioden sind hier jeweils durch Leerzeichen abgetrennt.
Auch die b-adischen Bruchentwicklungen zu anderen ganzzahligen Zahlenbasen b <> 10 sind für alle rationalen Zahlen periodisch und für alle irrationalen Zahlen nichtperiodisch



Mathematiker - Mo 18.02.13 18:01

Hallo Horst_H,
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Int64 ist auch wesentlich langsamer als mit 32-bit integer zu rechnen.

Danke für den Hinweis. Ich habe es wieder auf integer (Rev 2) geändert und nun läuft es wieder schneller: 1 s für 10000 Ziffern, 98 s für 100000.

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Muss der Übertrag nicht von unten ( groesse-1) nach oben ( 1) gerechnet werden?

Hier nicht, da die ersten Ziffern nach dem Komma im 1.Glied des Feldes stehen.

Hallo Tranx,
Dein Hinweis klingt sehr interessant. Es wird aber etwas dauern, bis ich das richtig verstanden habe.

Beste Grüße
Mathematiker


Tranx - Mo 18.02.13 18:11

Ich versuche das mal in einer Excel-Datei zu veranschaulichen. Aber irgendwie habe ich da einen Kn oten im Kopf. Bei Bruchzahlen klappt das, doch bei Ganzzahlen habe ich da noch Probleme.


Mathematiker - Mo 18.02.13 21:21

Hallo,
damit es vielleicht besser klar wird, was ich eigentlich bezwecke, habe ich in Revision 4/5 die PI-Codesuche ergänzt.
Dabei wird in der Buchstabenfolge (26er System) von PI nach dem Auftreten von sinnvollen deutschen Wörtern gesucht. Im rechten Teil kann dazu die Wortlänge von 3 bis 8 festgelegt werden. Bei der Suche wird aus einer Liste von 13500 Wörtern etwas Brauchbares ermittelt.
3- und 4buchstabige Wörter findet man schnell, ein 5-buchstabiges bis 15000 Stellen nicht, dagegen OXYGEN (deutsch?) ab Stelle 11602. 7buchstabige oder längere deutsche Wörter sind, meines Wissens nach, noch nicht gefunden worden.
Natürlich ist das alles nur Spielerei, aber interessant doch irgendwie.

Und außerdem:
Wenn die Kreiszahl eine normale, irrationale Zahl ist, so müssen alle möglichen Buchstabenkombinationen irgendwann einmal in der Ziffernfolge auftauchen. Auch wenn es kaum vorstellbar ist, so muss man ab einer noch so fernen Stelle auch den Text dieses Beitrages finden, ebenso jedes irgendwann einmal von einem Menschen geschriebene Buch und alle die in Zukunft noch geschrieben werden! D.h., PI enthält das ganze schon erworbene und jemals erwerbbare Wissen! :hair: Unvorstellbar!

Von mathematischer Seite aus ist die Umwandlung von transzendenten Zahlen in andere Positionssysteme ohnehin interessant.

Beste Grüße
Mathematiker


Horst_H - Di 19.02.13 08:49

Hallo,

ist die Suche nach Texten nicht eher eine statistische Analyse.
Man stellt sich doch dann eine irrationale Zahl als perfekte Zufallsbuchstabenfolge vor.
Wie groß ist die Länge dieser Folge, um zum Beispiel einen Satz wie "was ist denn das fuer ein sinnfreies zeug" mit einer Wahrscheinlichkeit von 50% zu finden.
Oder die Fragestellung, ab wieviel Stellen habe ich alle 7-buchtstabigen Zeichenfolgen gefunden.
Im Grunde läuft es darauf hinaus, das wir wahrscheinlich nie soviel Stellen von Pi berechnen können, um einen sinnhaften längeren Text zu finden.

Gruß Horst


Gammatester - Di 19.02.13 10:20

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
D.h., PI enthält das ganze schon erworbene und jemals erwerbbare Wissen! :hair: Unvorstellbar!
Ich denke, daß ist zu vereinfacht ausgedrückt! So enthält (die Dezimalentwicklung von) Pi ja noch nicht einmal die Dezimalentwicklung von 1/7 ganz zu Schweigen von anderen wie zB 2Pi.


Mathematiker - Di 19.02.13 15:19

Hallo Horst_H,
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Wie groß ist die Länge dieser Folge, um zum Beispiel einen Satz wie "was ist denn das fuer ein sinnfreies zeug" mit einer Wahrscheinlichkeit von 50% zu finden.

Für 50% Wahrscheinlichkeit brauchst Du bei diesem Satz etwa 10^53 Stellen von PI. Also wird man ihn mit großer Wahrscheinlichkeit nicht finden.
Würde jedes Atom im sichtbaren Weltall (etwa 10^85) eine Stelle von PI speichern, dann sind gerade mal 60buchstabige Folgen mit 50% zu finden.
Natürlich ist das alles nur theoretisch. Faszinierend finde ich die Vorstellung von einem PI mit allen möglichen Zeichenfolgen doch.

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Im Grunde läuft es darauf hinaus, das wir wahrscheinlich nie soviel Stellen von Pi berechnen können, um einen sinnhaften längeren Text zu finden.

Ja, leider.

Hallo Gammatester,
user profile iconGammatester hat folgendes geschrieben Zum zitierten Posting springen:
Ich denke, daß ist zu vereinfacht ausgedrückt! So enthält (die Dezimalentwicklung von) Pi ja noch nicht einmal die Dezimalentwicklung von 1/7 ...

Vollkommen klar. Ich habe mich falsch ausgedrückt. Besser wäre: "Jede Zeichenfolge (Gespräch, Artikel, Buch, ...), die ein Mensch bisher oder in Zukunft von sich gibt."
Da dies endlich ist, stimmt's wieder.
Andererseits. Wenn PI im mathematischen Sinne eine normale Zahl ist (http://de.wikipedia.org/wiki/Normale_Zahl), dann gibt es in ihr jede beliebige Näherung von 2PI.
Die unendliche Folge von 2PI kann ein Mensch ja ohnehin nicht erfassen.
Ich weiß, dass ist jetzt schon ziemlich "philosophisch".

Dennoch, noch einmal. Das ist alles nur eine kleine Spielerei.
In seinem genialen Buch "Contact" hat Carl Sagan über eine im Dualsystem in PI verschlüsselte Botschaft spekuliert.
Im Buch enthält die Binärdarstellung von PI bei einer unvorstellbar hohen Stellenzahl dieses Muster:
Zitat:
000000000000000000000000000000000000000
000000000000000000100000000000000000000
000000000000000100000001000000000000000
000000000000100000000000001000000000000
000000000100000000000000000001000000000
000000010000000000000000000000010000000
000001000000000000000000000000000100000
000010000000000000_00000000000000010000
000100000000000000000000000000000001000
001000000000000000000000000000000000100
010000000000000000000000000000000000010
100000000000000000000000000000000000001
100000000000000000000000000000000000001
010000000000000000000000000000000000010
001000000000000000000000000000000000100
000100000000000000000000000000000001000
000001000000000000000000000000000100000
000000010000000000000000000000010000000
000000000100000000000000000001000000000
000000000000100000000000001000000000000
000000000000000100000001000000000000000
000000000000000000100000000000000000000
000000000000000000000000000000000000000
Viele interpretierten, Sagan hätte einen transzendenten Schöpfer gemeint. Er war aber glühender Atheist (wie ich auch) und fand die ganze Sache nur interessant.

Beste Grüße
Mathematiker


Mathematiker - Do 21.02.13 20:27

Hallo
von user profile iconHorst_H habe ich eine deutlich verbesserte Umwandlungsroutine erhalten, die ich in Revision 6 eingebaut habe. 100000 Stellen im 26er-System werden jetzt in nur 10 Sekunden ermittelt.

Die Hauptidee von Horst_H war, die Anzahl der Multiplikationen der Feldglieder mit fortlaufender Berechnung sinnvoll zu verkürzen. Dafür besonderen Dank.
Eine weitere Idee von Horst_H die Multplikation mit ASM zu beschleunigen, muss ich erst noch richtig verstehen.

Weiterhin habe ich ein paar kleinere Änderungen vorgenommen. Die Ausgabe kann nun direkt in eine Datei picode.26 erfolgen, was natürlich schneller ist.
Bei der Suche nach Wörtern kann nun auch rückwärts gesucht werden.

Heute habe ich mit der neuen, schnellen Methode 2 Millionen Stellen im 26er-System in rund 2 Stunden ermittelt. Unter diesen konnte ich noch kein 7buchstabiges Wort finden. Bei der Rückwärtssuche entsteht aber schon relativ zeitig ALPHORN.
Am Wochenende will ich 5 Millionen Stellen erreichen. Aufhören werde ich wohl erst, wenn das erste sinnvolle Wort mit 7 Buchstaben gefunden ist.

Beste Grüße
Mathematiker


Horst_H - Fr 22.02.13 09:25

Hallo,

bei mir brauchen 100000 Stellen mit Deiner exe 11,7 Sek, mit Lazarus 1.0.2 ( welches TabWidth für Listbox nicht kennt ) kompiliert, sind es 2,69 Sek. Es hat sich also doch etwas getan.
Der Löwenanteil der schlechten Rechenzeit geht aber auf die Verarbeitung des Strings t. Deine Revision5 brauchte bei mir für 100000 Stellen sage und schreibe 218 Sekunden.
Aber es ändert nichts an der Tatsache, das diese Vorgehensweise durch ihr quadratisches Laufzeitverhalen nicht zu schnellen Zeiten führt.

Gruß Horst


Tranx - Fr 22.02.13 10:32

Eine sinnvolle Ergänzung wäre es, die Verteilung der einzelnen Buchstaben mit auszuwerten. Außerdem könnte das Ganze ja auf ein 29er System erweitert werden. Dann müsste als Buchstaben 26 - 28 die Buchstaben "Ä", "Ö" und "Ü" genommen werden.

Ich nehme mal an, dass die Verteilung der "Buchstaben" annähernd gleichverteilt ist, was ja der "normalen" Verteilung in einem Text widerspricht. "E" ist in vielen Texten sehr viel häufiger als z.B. "L" oder gar "Q", "X".


Mathematiker - Fr 22.02.13 22:37

Hallo,
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Aber es ändert nichts an der Tatsache, das diese Vorgehensweise durch ihr quadratisches Laufzeitverhalen nicht zu schnellen Zeiten führt.

Ja, leider. Ich habe jetzt eine "Dauertransformation" gestartet, 10 Millionen Zeichen. Nach der ersten Schätzung wird es etwa 40-45 Stunden dauern.
Ich überlege schon, ob es eine elegante Lösung gibt, schon vorhandene berechnete 26er-Ziffern um weitere zu ergänzen, ohne alle noch einmal zu berechnen. Im Moment habe ich noch keine Idee.

user profile iconTranx hat folgendes geschrieben Zum zitierten Posting springen:
Eine sinnvolle Ergänzung wäre es, die Verteilung der einzelnen Buchstaben mit auszuwerten. Außerdem könnte das Ganze ja auf ein 29er System erweitert werden. Dann müsste als Buchstaben 26 - 28 die Buchstaben "Ä", "Ö" und "Ü" genommen werden.

Wird auch gemacht. Eine Variante ist, das Leerzeichen aufzunehmen, d.h. also ein 27er-System. Nur dann treten Wörter noch seltener auf.
user profile iconTranx hat folgendes geschrieben Zum zitierten Posting springen:
Ich nehme mal an, dass die Verteilung der "Buchstaben" annähernd gleichverteilt ist, was ja der "normalen" Verteilung in einem Text widerspricht. "E" ist in vielen Texten sehr viel häufiger als z.B. "L" oder gar "Q", "X".

Das ist ein wichtiger Grund, weshalb normale Wörter eben nicht so schnell auftreten. Eigentlich müsste z.B. ein E 18mal häufiger als ein Z auftreten, usw.
Aber wie soll man das umsetzen?

Beste Grüße
Mathematiker


jfheins - Sa 23.02.13 03:50

Oha, schon wieder so ein Performance-Wettbewerb über ein total sinnloses Problem. Und das ausgerechnet jetzt, wo ich eigentlich ganz was anderes arbeiten müsste.

ich kann leider nicht widerstehen, daher anbei mein Programm, das noch relativ spartanisch ist. Aber es kann die Dezimalversion von PI in Basis 26 umrechnen. Es erzeugt immer 7 (basis26) Ziffern auf einmal und speichert 9 Dezimalziffern in einem Arrayelement.

Das Programm macht viel gebraucht von 64bit Zwischensummen, daher ist eine 64bit CPU im Vorteil: Die 32bit Ausführung benötigt ca. 40% mehr Zeit.
Auf meinem Rechner ist die 32bit Variante etwas schneller wie Revision 6, die 64bit Variante braucht nur ca. die halbe Zeit.

Im Anhang ist die AnyCPU Binary, d.h. es läuft auf beiden Betriebssystemen und jeweils in der "höchstbittigen" Variante. Mit dabei sind 10M Stellen von Pi.

Weitere Optimierungsfelder:
- Ich glaube da kann man noch ne Menge mit Parallelisierung machen. Das ganze ist eigentlich gut trennbar ... mal gucken.
- Wenn die Zahl PI nicht als Dezimal sondern als Binärbruch gespeichert wird, sollte das ganze nochmal schneller werden. Weil dann kann ein zeitaufwändiger Schritt (berechnen des Übertrags und der neuen ziffer) statt als Division einfach als bitweiser shift ausgeführt werden.

Ach ja, und das hat jetzt ca. 5h Zeit gebraucht geklaut.


Mathematiker - Sa 23.02.13 10:14

Hallo,
user profile iconjfheins hat folgendes geschrieben Zum zitierten Posting springen:
Oha, schon wieder so ein Performance-Wettbewerb über ein total sinnloses Problem.

Ja, so ist das. Der Spruch ist zwar steinalt, aber er stimmt: "Ein Computer löst die Probleme, die wir ohne ihn nicht hätten." :lol:

user profile iconjfheins hat folgendes geschrieben Zum zitierten Posting springen:
ich kann leider nicht widerstehen

Geht mir auch immer so. Sehe ich irgendwo so eine, wenn auch sinnfreie, Aufgabe, muss ich es versuchen. Sind wir süchtig? :mrgreen:

user profile iconjfheins hat folgendes geschrieben Zum zitierten Posting springen:
Das Programm macht viel gebraucht von 64bit Zwischensummen, daher ist eine 64bit CPU im Vorteil: Die 32bit Ausführung benötigt ca. 40% mehr Zeit.
Auf meinem Rechner ist die 32bit Variante etwas schneller wie Revision 6, die 64bit Variante braucht nur ca. die halbe Zeit.

Auf meinem alten Rechner läuft Deine Lösung ein klein wenig schneller als Revision 6. Die 64bit-Variante kann ich erst am Dienstag testen. Ich bin schon sehr gespannt.

Bei der Suche nach einem noch schnelleren Programm zur PI-Berechnung als "pifast", bin ich auf "qpi" von Steve Pagliarulo gestoßen. http://members.shaw.ca/francislyster/pi/pi.html
Das ist superschnell! :zustimm:

In der Revision 7 habe ich noch die Umwandlung in PI-Code 27 ergänzt, d.h. 0=Leerzeichen, 1..27=A..Z.

Beste Grüße
Mathematiker


jfheins - Sa 23.02.13 19:32

Hallo,
sooo, nachdem ich ausgeschlafen habe, konnte ich noch ein bisschen was optimieren.

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:

Bei der Suche nach einem noch schnelleren Programm zur PI-Berechnung als "pifast", bin ich auf "qpi" von Steve Pagliarulo gestoßen. http://members.shaw.ca/francislyster/pi/pi.html
Das ist superschnell! :zustimm:

Ja schon. Habe ich auch benutzt um die 10 Mio. Stellen Datei zu erzeugen. Leider habe ich bis jetzt kein Programm finden können dass PI wirklich binär erzeugt. (Das birgt m.e. nach wesentliches Potenzial für Optimierungen) Dadurch ist nicht nur die Datei kleiner, sondern jedes Element in dem Ausgangsarray speichert maximal viel Information. Und der Übertrag ist schneller berechnet.
Mein Profiler zeigt mir, dass in diesen beiden Zeilen jeweils 38% der Rechenzeit verbraten wird:

C#-Quelltext
1:
2:
carry = (ulong)(result / MaxElement);
decimalPI[i] = (uint)(result % MaxElement);

Die CPU kann auf jeden Fall beides mit einem Befehl liefern, ich weiß nicht ob das aktuell schon derart optimiert wird. Ansonsten ist da nochmal so 35% Zeitersparnis drin. (Das kannst du in delphi mit inline-Assembler besser als ich in C# ;-) )

Ich habe das Programm jetzt noch parallelisiert und etwas schicker gemacht: Es reagiert während der Berechnung noch, man kann die Berechnung abbrechen und es gibt einen tollen Fortschrittsbalken :-)
Auf einem Single-Core PC wird es jetzt wohl langsamer laufen. Aber die Beschleunigung durch 4 parallele Threads hat sich gewaschen.

Auf meinem PC (mit Q6600 Quadcore und 64-bit) erreiche ich jetzt folgende Zeiten:
Zitat:
600k Stellen:
Rev. 6: 232,5 Sekunden
Mein Programm: ca. 40 Sekunden

150k Stellen:
Rev.6: 14,5 Sekunden
Meins: 2,5-2,8 Sekunden

Das geht echt ab :-D Ich muss aber dazu sagen, dass ich das ganze nicht ohne deinen Sourcecode geschafft hätte. :zustimm:

Ergebnisse sind 100% identisch. Mein Programm braucht irgendwie immer unterschiedlich lange. Wird wohl mit dem ganzen .net Kram zusammenhängen, aber solange es schnell ist, passt das schon :D

Nachdem ich dir jetzt erstmal eine Nuß zu knabbern gegeben habe kann ich mich dem anderen Zeug widmen, das ich noch machen muss. Das Problem ist, dass mir das hier mehr Spaß macht und daher eher erledigt wird auch wenn es unwichtiger ist :mrgreen:

Anbei sind meine Sourcen, der Code steckt in Mainwindow.xaml.cs, die wichtigstzen Funktionen sind:
MultiplyCarryover (hier findet die wirkliche Rechnerei statt auf einem Teil des Arrays)
GetDigitsBase26 (Hier wird die Parallelisierung erzeugt und wieder zusammengeführt)
Calculate (Hier wird dann aus dem zurückgegebenen 64bit Wert die eigentlichen Ziffern gebildet.)


Mathematiker - Sa 23.02.13 20:04

Hallo,
user profile iconjfheins hat folgendes geschrieben Zum zitierten Posting springen:
Ich habe das Programm jetzt noch parallelisiert und etwas schicker gemacht: Es reagiert während der Berechnung noch, man kann die Berechnung abbrechen und es gibt einen tollen Fortschrittsbalken :-)
... Aber die Beschleunigung durch 4 parallele Threads hat sich gewaschen.

Wow. Das ist richtig schnell. Bei meinen 2 Kernen brauche ich nur noch 4 s für 100000 Stellen. Deine Geschwindigkeiten erreiche ich auf meiner alten Mühle nicht. Ich brauche einen neuen Computer. :lol:

user profile iconjfheins hat folgendes geschrieben Zum zitierten Posting springen:
Nachdem ich dir jetzt erstmal eine Nuß zu knabbern gegeben habe kann ich mich dem anderen Zeug widmen, das ich noch machen muss.

Das hast Du auf jeden Fall. Besonders interessiert mich die Aufteilung auf die Threads. Mir ist nämlich schleierhaft, was an dem Algorithmus parallelisiert werden kann.

Beste Grüße
Mathematiker


Martok - Sa 23.02.13 20:52

Wenn ich dir sage, dass das mit Mathematica in 5 Zeilen Code ca 3 Sekunden für 10M Stellen (dezimal) braucht, ist das demotivierend, oder? :mrgreen:
Einziges Problem: Basis 26 bedeutet natürlich [0-9a-p], das ist noch nicht das richtige Alphabet... ob das ohne ReplaceRule geht, muss ich mal noch rausfinden.

Die haben allerdings auch irgend einen Trick, der die erste Million Stellen von Pi quasi ohne Rechenzeit liefert und von dort aus fortsetzen kann.


jfheins - Sa 23.02.13 20:57

Hi,
es kommt noch besser - ich habe soeben noch einmal viel 'rausgeholt. 600k Stellen jetzt in knapp 13s :-D
Ich habe den modulo Operator gespart (15%) und durch die einfache Rechnung ersetzt. Dann habe ich Maxelement (=1E9) als Konstante deklariert. Hierdurch konnte der Compiler aus der Division eine Multiplikation mit dem Kehrwert machen (der Kehrwert muss nur einmal ausgerechnet werden) und das geht wesentlich schneller.

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:

Das hast Du auf jeden Fall. Besonders interessiert mich die Aufteilung auf die Threads. Mir ist nämlich schleierhaft, was an dem Algorithmus parallelisiert werden kann.

Ich habe das auch erst auf einem Stück Papier ausprobiert, aber es geht. Du kannst die gesamte Menge in vier Teile zerteilen. Um die nächste Ziffer zu erhalten brauchst du ja nicht alle Nachkommastellen, es reichen die ersten x oder so.
Als Beispiel 120000 Dezimalziffern:
Wenn du jetzt also vier Teile hast, kannst du jeden mit 26 multiplizieren. Bei jedem Teil bleibt ein Übertrag, der noch in den Teil einfließen muss, der weiter vorne liegt. Es ist nun logisch, dass der Übertrag von Teil 2 (Ziffern 30k bis 60k) nichts mehr am Ergebnis ändert. Der Übertrag vom ersten Teil ist die neue Ziffer im 26er System, die anderen drei Übertrage werden an den passenden Positionen eingefügt.
das geht natürlich besser für große Zahlen, ab 100 Ziffern findet daher keine Parallelisierung mehr statt.

Die Schritte sind dann etwa so:
1. Finden/definieren der Trennstellen
2. Parallele Berechnung jedes Teils
3. Zusammenfügen der Übertrage
4. Übertrag des ersten Teils zurückgeben

@Martok: Ja schon ein wenig. Andererseits habe ich kein Mathematica und keine Ahnung was du für einen Rechner hast. Und diesen "Trick" benutzen wir ja auch, die Dezimalversion wird aus der Datei eingelesen und der Teil geht nicht in die Zeitrechnung ein.


Mathematiker - Sa 23.02.13 22:19

Hallo,
user profile iconMartok hat folgendes geschrieben Zum zitierten Posting springen:
Wenn ich dir sage, dass das mit Mathematica in 5 Zeilen Code ca 3 Sekunden für 10M Stellen (dezimal) braucht, ist das demotivierend, oder? :mrgreen:

Das ist nicht nur demotivierend, das ist ... mir fehlen die Worte. :bawling: :bawling: :bawling:
Mein Rechner arbeitet nun mehr 36 Stunden(!) und wird noch etwa 5-6 brauchen, um 14 Millionen Dezimalstellen in 10M 26er-System zu transformieren. Da bin ich nicht nur frustriert!
3s bei Mathematica bedeutet aber, dass dort ein anderer Algorithmus verwendet wird. Die Frage ist nur: Welcher? :nixweiss:

Wenn es nicht zu viel Mühe macht, könntest Du ja mal z.B. 25M 26er-Zeichen berechnen lassen. Wenn deren Algorithmus auch quadratisch wächst, wären das etwa 30-40 s Rechenzeit. Ich weiß nur nicht, ob über die EE eine solche große Datei als Anhang zu versenden geht.

user profile iconjfheins hat folgendes geschrieben Zum zitierten Posting springen:
Hi,
es kommt noch besser - ich habe soeben noch einmal viel 'rausgeholt. 600k Stellen jetzt in knapp 13s :-D

Sehr schön. Könntest Du mir bitte die Exe senden. Ich habe kein C# und ganz ehrlich, ich verstehe es auch kaum.
Danke für die Erklärung der Parallelisierung des Prozesses.

Beste Grüße
Mathematiker


jfheins - Sa 23.02.13 22:28

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:

Sehr schön. Könntest Du mir bitte die Exe senden. Ich habe kein C# und ganz ehrlich, ich verstehe es auch kaum.

Klar, ist im Anhang.

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
Danke für die Erklärung der Parallelisierung des Prozesses.
Beste Grüße
Mathematiker

Gerne. Falls noch etwas unklar ist, sag Bescheid :wink:


Martok - Sa 23.02.13 23:48

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
3s bei Mathematica bedeutet aber, dass dort ein anderer Algorithmus verwendet wird. Die Frage ist nur: Welcher? :nixweiss:
Der ist auf jeden Fall "neu": Mathematica 7 ist ähnlich "langsam", sobald man viele Stellen will. Mathematica 8 ist da wesentlich schneller - aber an den passenden Rechner komm ich grad nicht ran ;-)

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
Wenn es nicht zu viel Mühe macht, könntest Du ja mal z.B. 25M 26er-Zeichen berechnen lassen. Wenn deren Algorithmus auch quadratisch wächst, wären das etwa 30-40 s Rechenzeit.


Mathematica
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
//tabelle Stellenwert->Buchstabe (ja, das ist hier komplizierter als notwendig *g*)
table := Table[a[[2]] -> a[[1]], {a, 
    Transpose[{CharacterRange["A""Z"], Range[025]}]}]; 
//Liste von Stellen
konvert[val_] := RealDigits[val, 26][[1]] /. table;
//als String
konvertStr[val_] := StringJoin[konvert[val]];
//test mit Ausgabe (benutzerfreundlicher als *Timing[])
SetAttributes[measure, HoldAll];
measure[expr_] := 
  Block[{time, result}, {time, result} = AbsoluteTiming[expr]; Print["Time taken: ", time]; result];

//Ergebnis in Datei dumpen
doIt[stellen_] := Export["C:\\pi26-" <> ToString[stellen] <> ".txt", measure[konvertStr[N[Pi, stellen]]], "Text"];
doIt[1000]
{...}


Ausgabe
1:
2:
3:
4:
Time taken: 0.           Out[171]= "C:\\pi26-1000.txt"
Time taken: 2.2031250    Out[172]= "C:\\pi26-1000000.txt"
Time taken: 82.4062500   Out[173]= "C:\\pi26-10000000.txt"
Time taken: 249.0312500  Out[174]= "C:\\pi26-25000000.txt"

System: HP 6715b Bj.2007, Turion64 2x1.8Ghz, XPSP3x86, 3.8GB RAM (die aber nicht auffallend beansprucht wurden).
Die Laufzeit (png, 5.96 KB) sieht im oberen Teil fast linear aus, das irritiert mich etwas. Eigentlich steigt das zu wenig, selbst wenn man annimmt, dass es "unten" irgendwelche Lookuptabellen gibt.

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
Ich weiß nur nicht, ob über die EE eine solche große Datei als Anhang zu versenden geht.
Knapp 15MB gezippt, Dropbox geht immer (auch wenns ewig dauert): Link [https://www.dropbox.com/s/nycl37oj42150vb/pi26.zip?dl=1]. Bitte an Byte 2 einen "." dazwischendenken, die Information bekommt man zwar von RealDigits, ich hab das der Einfachheit halber aber mal ignoriert.


Mathematiker - Sa 23.02.13 23:56

Hallo Martok,
user profile iconMartok hat folgendes geschrieben Zum zitierten Posting springen:
Knapp 15MB gezippt, Dropbox geht immer (auch wenns ewig dauert):

Das ist super! Vielen Dank.
Damit kann ich heute noch auf Suche nach längeren Wörtern gehen.

user profile iconMartok hat folgendes geschrieben Zum zitierten Posting springen:
Die [Anhang: Laufzeit] sieht im oberen Teil fast linear aus, das irritiert mich etwas. Eigentlich steigt das zu wenig, selbst wenn man annimmt, dass es "unten" irgendwelche Lookuptabellen gibt.

Das ist wirklich verblüffend. Ich kann mir nur denken, dass irgendjemand ein Verfahren gefunden hat, dass auch für Dezimalbrüche so schnell ist wie das Euklidische Verfahren für ganze Zahlen. Sehr verwirrend.

Beste Grüße
Mathematiker

:beer: Supererfolg! :beer:
Dank Martoks Hilfe verkünde ich die "Entdeckung" der ersten 7buchstabigen Wörter im PI-Code. Das sind:
Zitat:
BREVIER 8284233
REICHEN 9774026
STAUNEN 10729194
ALGEBRA 13626059
GELTEND 16282425

Wenn auch das erste nicht so schön ist, ist zumindest ALGEBRA dabei.
Ein 8buchstabiges Wort war unter den ersten 17,6 Millionen Zeichen leider nicht zu finden.


Martok - So 24.02.13 00:24

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
Das ist wirklich verblüffend. Ich kann mir nur denken, dass irgendjemand ein Verfahren gefunden hat, dass auch für Dezimalbrüche so schnell ist wie das Euklidische Verfahren für ganze Zahlen.
Alles, was dazu heute geschrieben [http://reference.wolfram.com/mathematica/tutorial/SomeNotesOnInternalImplementation.html#23292] steht (interessante Seite übrigens, diese Notes hab ich noch nie gelesen :D ):
Zitat:
IntegerDigits, RealDigits, and related base conversion functions use recursive divide-and-conquer algorithms. Similar algorithms are used for number input and output.

In NKS [http://www.wolframscience.com/nksonline/page-901a-text] beschreibt Wolfram das etwas genauer (nein, ich weiß auch nicht was er da tut :roll:):
Page 901 hat folgendes geschrieben:

A whole number n can be converted to a sequence of digits in base k using IntegerDigits[n,k] or (see also page 1094)

Quelltext
1:
Reverse[Mod[NestWhileList[Floor[#/k] &, n, # >=k &], k]]                    

and from a sequence of digits using FromDigits[list,k] or

Quelltext
1:
Fold[(k #1 + #2)&, 0, list]                    

For a number x between 0 and 1, the first m digits in its digit sequence in base k are given by RealDigits[x, k, m] or

Quelltext
1:
Floor[k NestList[Mod[k #, 1]&, x, m-1]]                    



Mathematiker - So 24.02.13 00:39

Hallo Martok,
user profile iconMartok hat folgendes geschrieben Zum zitierten Posting springen:
(nein, ich weiß auch nicht was er da tut :roll:):
Page 901 hat folgendes geschrieben:
... For a number x between 0 and 1, the first m digits in its digit sequence in base k are given by RealDigits[x, k, m] or

Quelltext
1:
Floor[k NestList[Mod[k #, 1]&, x, m-1]]                    


Das ist sehr harte mathematische Kost. Aber ich werde mal suchen, was mit dem letzten Ausdruck gemeint ist.
Danke für diesen Hinweis und natürlich Gratulation :beer: zum Entdecken des ersten 7buchstabigen Wortes, denn es war ja Deine ermittelte Ziffernfolge im 26er-System.

Beste Grüße
Mathematiker


Horst_H - So 24.02.13 03:31

Guten morgen,

[user]jfheins[/useer] hats doch http://members.shaw.ca/francislyster/pi/chart.html schon angegeben und siehe da, dort steht ein Verweis auf apfloat http://www.apfloat.org/ , der direkt zu Basis 2..36 konvertiert.
Leere Textdatei erstellen und schon kann man diese als Ziel für die Umwandlung nehmen.
Das die Basis dann leider 0..9 a.. ist, wäre es auch eine Überlegung die Worte, die gesucht werden in dieses Format zu wandeln ;-)
Leider ist es etwas langsamer mit 44 gegenüber 2 Sekunden für 1M-Stellen von pi und 1140 für 16M

Gruß Horst
Mist ist bei 25 Mio Ziffern abgestürzt.... :-(
Das war ein IO-Fehler, beim Zugriff auf die Dateien.
Es werden viele kleine Dateien erstellt und sukzessive größere erstellt.
Aber 1Mio Zeichen( es fehlen am Ende 2) in 36 Sekunden funktioniert.

Ich habe mal mparith angetestet um die Zahl pi.flt=pi.000 mit "3." am Anfang wenigstens einzulesen:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
program unbenannt;
uses
  sysutils,strutils,mp_types, mp_base, mp_numth,
  mp_rcalc, mp_real;
var

  a: mp_float;
  s : Ansistring;

function FileEinlesen(const Fname:ansiString):ansistring;
var
  f : file;
  l : integer;
begin
  Assignfile(f,FName);
  Reset(f, 1);
  l := filesize(f);
  writeln(l);
  setlength(result,l);
  BlockRead(f,result[1],l);
  closeFile(f);
end;

procedure Aufbereiten(var s:AnsiString);
//alle ZeilenPositonsMarker entfernen
const
  ZPM = #13#10;
  lZPM = length(ZPM);
var
  l,i,p0,p1,p2 : integer;
begin
  p0 := Pos(ZPM,s);
  p1 := p0+lZPM;
  p2 := p0;

  repeat
    p2 :=PosEx(ZPM,s,p1);
    IF p2 = 0 then
      break;
    i := p2-p1;
    IF p2 <> p1 then
      begin
      //Kürzen
      move(s[p1],s[p0],i);
      inc(p0,i);
      end;
    p1 := p2+lZPM;
  until p2 = 0;
  setlength(s,p0);

  s[p0] := #0;
  writeln(p0:8);
end;

var
  T1,t0: TDAteTime;
begin
  s := FileEinlesen('pi.flt');
  Aufbereiten(s);
  writeln('MPArith V', MP_VERSION, ' with MAXDigits = ',MAXDigits, ', MP_MAXBIT = ',MP_MAXBIT);

  mpf_init(a);
  T0 := now;
  mpf_read_decimal(a,pChar(s));
  T1 := now;
  mpf_writeln('Pi: ',a,100);
  writeln(FormatDateTime('HH:NN:SS.ZZZ',T1-T0 ));

  mpf_clear(a);
end.

Leider dauert alleine die Umwandlung des Strings in ein mpf 128 Sekunden.
Vielleicht ist das Einlesen der Nachkommastellen als Integer und anschliessender Division durch die passende Zehnerpotenz schneller.


Martok - So 24.02.13 04:29

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
Das ist sehr harte mathematische Kost. Aber ich werde mal suchen, was mit dem letzten Ausdruck gemeint ist.
Mehr "seltsame Syntax", er mischt da munter Expressions mit Funktionen...
Ich hab jetzt mal eine Weile auf die Dokumentation gestarrt, das ist eigentlich trivial.
Spoiler: es ist mit ziemlicher Sicherheit nicht dass, was sie in Mathematica tun. Gar nicht mal wegen der Laufzeit, aber...

Quelltext
1:
2:
3:
No more memory available.
Mathematica kernel has shut down.
Try quitting other applications and then retry.

:lol:

NestedList wendet eine Funktion (erster Parameter) wiederholt (dritter Parameter) auf ihr Ergebnis an (beginnend mit dem zweiten Parameter) und sammelt die Ergebnisse ein. "&" hinter einem Ausdruck macht den zu einer Anonymous Function mit dem Standardparameter "#", Mod[x,1] ist das gleiche wie FractionalPart[x].
Also: man multipliziere mit der Basis (eine Stelle hochschieben), nehme den Nachkommateil davon ("die nächste Stelle"), speichere diesen, wiederhole so oft wie Stellen gewünscht sind. Am Ende mit der Basis multiplizieren wandelt in Stellen um, das Floor außenrum schneidet die Nachkommastellen ab.

Diese beiden sind für x in (0..1] identisch untereinander und zu RealDigits:

Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
fu[x_, k_, m_] := Floor[k*NestList[(Mod[k *#, 1]) &, x, m - 1]];
fu2[x_, k_, m_] := Block[{result, work, n},
  result = {};
  work = x;
  For[i = 0, i < m, i++,
   work = work*k;
   result = Append[result, Floor[work]];
   work = FractionalPart[work];
   ];
  result
  ]

Funktioniert natürlich nur, wenn man schnell Arbitrary Precision-Multiplizieren kann.
Eigentlich reicht Fixedpoint, das Komma ist ja (außer im ersten Durchlauf) immer an der 2. Stelle, es steht immer "0.xxxx".
Die Kopie in work ist hier nur, weil x als Argument nicht bearbeitet werden kann. Eigener Code könnte das ja dann...

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
Danke für diesen Hinweis und natürlich Gratulation :beer: zum Entdecken des ersten 7buchstabigen Wortes, denn es war ja Deine ermittelte Ziffernfolge im 26er-System.
Na, wenn dann müssen wir dem Herrn Wolfram gratulieren :zwinker:


Mathematiker - So 24.02.13 11:04

Hallo,
da ich heute bei der Korrektur der Sächsischen Matheolympiade bin, kann ich leider Eure Hinweise nur kurz beantworten.
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
user profile iconjfheins hats doch http://members.shaw.ca/francislyster/pi/chart.html schon angegeben und siehe da, dort steht ein Verweis auf apfloat http://www.apfloat.org/ , der direkt zu Basis 2..36 konvertiert.

Ist sehr interessant. Ich werde einmal sehen, wie viele Stellen möglich sind. Evtl. 100 Millionen wäre schön.
Dass die Zeichen im Format 0..9,a.. vorliegen, ist nicht schlimm. Das kann man ja bei der Wortsuche berücksichtigen.

Hallo Martok,
wenn ich es richtig verstehe, ist

Quelltext
1:
fu[x_, k_, m_] := Floor[k*NestList[(Mod[k *#, 1]) &, x, m - 1]];                    

nicht viel anders, als wir es hier versuchen.
Dann müsste die Rechenzeit aber quadratisch wachsen, und Du hast vollkommen recht: Mathematica macht es intern anders!

Beste Grüße
Mathematiker


jfheins - So 24.02.13 19:30

Also ich bin inzwischen übrigens bei 600k Stellen in 6,25 Sekunden. Das Programm benötigt PI jetzt allerdings in Binärdarstellung als Eingabe. Da ich nur 4M Stellen von PI im Binärsystem berechnet habe, geht das Programm nur bis ca. 830000 Basis 26 Stellen. (Und braucht dafür bei mir ca. 11,5 Sekunden)

Die quadratische Laufzeit bleibt leider. Aber ich könnte mir vorstellen dass man mit native Code und ganz vielen Informatikern noch etwas flotteren Code hinbekommt :P

Die exe befindet sich im Unterordner \piTransform\bin\Release.


Mathematiker - So 24.02.13 20:18

Hallo,
mit Hilfe von http://www.apfloat.org/ habe ich 50 Millionen PI-Stellen im 26er-System in etwa 2 Stunden meinen Computer berechnen lassen. Bei einer anschließenden Suche mit nun mehr 1,4 Millionen Wörtern der deutschen Sprache gab es einige interessante Treffer:

Als erstes Wort mit 7 Buchstaben ergab sich LEINOEL (1263143) und ohne Umlaut ERBZINS (2731952). Besonders wichtig ist, dass ab der 5854017.Stelle ECKSOFA auftritt. Das EE-Sofa ist in PI kodiert! Wahnsinn! :zustimm:
Das erste 8buchstabige Wort ist HOHLNIET (1547729), das erste und einzige gefundene mit 9 Buchstaben REFORMIST (5204510). Eins mit 10 Buchstaben konnte ich nicht finden.
Allerdings ist die Suche nicht mehr so spannend. Praktisch geht es jetzt nur noch, in dem apfloat für längere Zeit eingesetzt wird.

Die Umwandlung eines Bruchs in ein beliebiges System ist natürlich weiter sehr interessant. Und gerade die Ergebnisse von user profile iconjfheins sind toll.
Aber es ist schon deprimierend, wenn man Programme im Netz findet, die so schnell sind, dass ich dies wahrscheinlich nie erreichen kann.

Beste Grüße
Mathematiker


Tranx - So 24.02.13 20:25

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
Hallo,
Als erstes Wort mit 7 Buchstaben ergab sich LEINOEL (1263143) und ohne Umlaut ERBZINS (2731952). Besonders wichtig ist, dass ab der 5854017.Stelle ECKSOFA auftritt. Das EE-Sofa ist in PI kodiert! Wahnsinn! :zustimm:
Das erste 8buchstabige Wort ist HOHLNIET (1547729), das erste und einzige gefundene mit 9 Buchstaben REFORMIST (5204510). Eins mit 10 Buchstaben konnte ich nicht finden.
Allerdings ist die Suche nicht mehr so spannend. Praktisch geht es jetzt nur noch, in dem apfloat für längere Zeit eingesetzt wird.

Die Umwandlung eines Bruchs in ein beliebiges System ist natürlich weiter sehr interessant. Und gerade die Ergebnisse von user profile iconjfheins sind toll.
Aber es ist schon deprimierend, wenn man Programme im Netz findet, die so schnell sind, dass ich dies wahrscheinlich nie erreichen kann.

Beste Grüße
Mathematiker


Soso, Hohlniet und Reformist. Wer weiß, was man da noch so alles findet. ;)


Mathematiker - So 24.02.13 20:33

Hallo Tranx,
user profile iconTranx hat folgendes geschrieben Zum zitierten Posting springen:
Soso, Hohlniet und Reformist. Wer weiß, was man da noch so alles findet. ;)

Ich weiß, dass die ganze Suche eigentlich ziemlich sinnfrei ist. Aber es macht(e) Spaß.

Übrigens: Ein weiterer "Durchbruch"! :lol:
An 49335488.Stelle steht tatsächlich MARTOK. :!:
Jetzt suche ich nach TRANX und JFHEINS.

Beste Grüße
Mathematiker

Nachtrag:
TRANX steht an 18252116.Stelle. JFHEINS ist nicht unter den ersten 50 Millionen Stellen, d.h. ich brauche dringend mehr Stellen.


Tranx - So 24.02.13 20:37

Was ist erst, wenn Du dann Mathematiker findest!!!


Martok - So 24.02.13 21:21

Ich überlege grade, ob man nicht BBP [http://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula] direkt in eine andere Basis bringen kann. 26 zum Beispiel ;)

user profile iconMathematiker hat folgendes geschrieben Zum zitierten Posting springen:
Übrigens: Ein weiterer "Durchbruch"! :lol:
An 49335488.Stelle steht tatsächlich MARTOK. :!:
TRANX steht an 18252116.Stelle. JFHEINS ist nicht unter den ersten 50 Millionen Stellen, d.h. ich brauche dringend mehr Stellen.
:lol:

Ich hab mal Mathematica auf 100M losgelassen. Keine Ahnung, ob das dieses Jahr noch fertig wird :D Bis dahin haben wir aber vielleicht was, was die Zahlen nicht erst in den RAM legt...
EDIT: okay, das wird so nix, der MathKernel crasht mir mit OutOfMemory weg. Da hat irgendwer mit Signed Int gerarbeitet.


Horst_H - So 24.02.13 23:17

Hallo,

wie wäre es mit einer Ausgabe in HEX, dies lässt sich dann je nach Gemütslage in jede Basis bringen und ist sehr schnell einlesbar.
50 MB lassen sich schneller herunterladen, als die Anzahl Pi Stellen zu bestimmen.

Gruß Horst


Horst_H - Mo 25.02.13 13:40

Hallo,

ich habe mal piFast43 unter wine laufen lassen.
Dort werden 500e6 Dezimalen in 1,75 h berechnet, also 10 mal so schnell wie apfloat, was mir auch unter wine mit assertion fehler abbricht.
Gibt es irgendeine Formel mit der man zum Beispiel sagen kann 1247 Stellen Basis 10 = 844 Stellen Basis 26 dann könnte man Paketeweise rechnen.
ln(26 {=2*13})/ln(10 {=2*5})= 1,414973348..... ist ja nicht wirklich hilfreich.

Gruß Horst


Mathematiker - Mo 25.02.13 14:37

Hallo Horst_H,
user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
ln(26 {=2*13})/ln(10 {=2*5})= 1,414973348..... ist ja nicht wirklich hilfreich.

Warum sollte ln(26)/ln(10) nicht korrekt sein?
Hat eine Dezimalzahl n Stellen, so liegt sie zwischen 10^(n-1) und 10^n. Rechnet man das auf die 26er-Darstellung um, ergibt sich gerade 26^((n-1) ln(10)/ln(26)) bis 26^(n ln(10)/ln(26)).


Mit extremen Computereinsatz habe ich nun doch mit apfloat 120 Millionen Stellen ermittelt. 6 Stunden war mein "armer" Computer beschäftigt und gab am Ende auch schon komische Töne von sich. :wink:
Da mein Drucker wegen Nichtbeachtung schon böse blinkt, könnte ich die Stellen auch ausdrucken. Das sind nur schlappe 250000 A4-Seiten. Vielleicht lerne ich sie ja auch auswendig. :mrgreen:

Die Suche nach den 1,4 Millionen Wörtern hat auch noch einmal 4 Stunden gedauert (keine Hash-Tabelle verwendet!). Das Ergebnis hänge ich als PDF an, wobei jedes Wort nur mit seinem ersten Auftreten angegeben wird. Deshalb werden die Abstände der gefundenen Wörter bei hohen Stellenzahlen auch scheinbar größer.
Die 3-, 4- und 5-buchstabigen Begriffe wurden alle gefunden. EULER kam erst an Stelle 72568145, ausgerechnet EULER!
Weitere wichtige Begriffe: GAUSS 23549046.Stelle, FERMAT 61130151, DELPHI 71889200 und EUKLID 86405187. KEPLER und PASCAL treten nicht auf.

Bei dem einzigen Wort mit 9 Buchstaben blieb es, zehn Buchstaben und mehr waren wieder nicht zu finden. Damit war die ganze Mühe eigentlich umsonst. :cry:
So, nun ist es gut! Der PI-Code hat sich erst einmal erledigt.

Jetzt werde ich Euren tollen Hinweis nutzen und versuchen mein Delphi-Programm zur Umwandlung eines Bruchs in ein anderes System (auch Basis 26 :wink: ) zu verbessern.

Beste Grüße
Mathematiker


Anika - Mo 25.02.13 15:13

Guten Tag,
ich habe in dem Text nach meinem Namen Anika gesucht und nicht gefunden.
Annika ist auch nicht drin. Mein Name hat nur ein n und müsste doch da sein wenn alle mit fünf Buchstaben drin sind.
Mache ich etwas falsch?

Viele liebe Grüße
Anika


Mathematiker - Mo 25.02.13 15:26

Hallo Anika,
user profile iconAnika hat folgendes geschrieben Zum zitierten Posting springen:
... ich habe in dem Text nach meinem Namen Anika gesucht und nicht gefunden.

Stimmt. In meiner Wortsuchliste ist nur ANNIKA mit zwei N enthalten. Das Wort tritt bis 120 Millionen Stellen nicht auf.
Die Variante ANIKA mit einem N habe ich nicht gesucht (Entschuldigung) und jetzt nachgeholt.
ANIKA tritt an der Stelle 13329838 auf und ebenso die andere Variante ANICA schon an der 324286.Stelle.

Beste Grüße
Mathematiker