Autor Beitrag
jfheins
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 918
Erhaltene Danke: 158

Win 10
VS 2013, VS2015
BeitragVerfasst: 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. 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:
ausblenden 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.)
Einloggen, um Attachments anzusehen!

Für diesen Beitrag haben gedankt: Mathematiker
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: 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

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 3661
Erhaltene Danke: 604

Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
BeitragVerfasst: 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.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Für diesen Beitrag haben gedankt: Mathematiker
jfheins
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 918
Erhaltene Danke: 158

Win 10
VS 2013, VS2015
BeitragVerfasst: 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.

Für diesen Beitrag haben gedankt: Mathematiker
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: 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

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
jfheins
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 918
Erhaltene Danke: 158

Win 10
VS 2013, VS2015
BeitragVerfasst: 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:
Einloggen, um Attachments anzusehen!

Für diesen Beitrag haben gedankt: Mathematiker
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 3661
Erhaltene Danke: 604

Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
BeitragVerfasst: 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.

ausblenden 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]
{...}

ausblenden 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. Bitte an Byte 2 einen "." dazwischendenken, die Information bekommt man zwar von RealDigits, ich hab das der Einfachheit halber aber mal ignoriert.
Einloggen, um Attachments anzusehen!
_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Für diesen Beitrag haben gedankt: Mathematiker
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: 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.

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein


Zuletzt bearbeitet von Mathematiker am So 24.02.13 00:25, insgesamt 1-mal bearbeitet

Für diesen Beitrag haben gedankt: Martok
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 3661
Erhaltene Danke: 604

Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
BeitragVerfasst: 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 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 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)
ausblenden Quelltext
1:
Reverse[Mod[NestWhileList[Floor[#/k] &, n, # >=k &], k]]					

and from a sequence of digits using FromDigits[list,k] or
ausblenden 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
ausblenden Quelltext
1:
Floor[k NestList[Mod[k #, 1]&, x, m-1]]					


_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Für diesen Beitrag haben gedankt: Mathematiker
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: 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
ausblenden 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

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1652
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: So 24.02.13 03:31 
Guten morgen,

[user]jfheins[/useer] hats doch members.shaw.ca/fran...lyster/pi/chart.html schon angegeben und siehe da, dort steht ein Verweis auf apfloat 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:
ausblenden volle Höhe 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.

Für diesen Beitrag haben gedankt: Mathematiker
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 3661
Erhaltene Danke: 604

Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
BeitragVerfasst: 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...
ausblenden 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:
ausblenden 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:

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Für diesen Beitrag haben gedankt: Mathematiker
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: 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 members.shaw.ca/fran...lyster/pi/chart.html schon angegeben und siehe da, dort steht ein Verweis auf apfloat 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
ausblenden 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

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
jfheins
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 918
Erhaltene Danke: 158

Win 10
VS 2013, VS2015
BeitragVerfasst: 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.
Einloggen, um Attachments anzusehen!
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: So 24.02.13 20:18 
Hallo,
mit Hilfe von 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

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Tranx
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 648
Erhaltene Danke: 85

WIN 2000, WIN XP
D5 Prof
BeitragVerfasst: 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. ;)

_________________
Toleranz ist eine Grundvoraussetzung für das Leben.
Mathematiker Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: 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.

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein


Zuletzt bearbeitet von Mathematiker am So 24.02.13 20:58, insgesamt 1-mal bearbeitet
Tranx
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 648
Erhaltene Danke: 85

WIN 2000, WIN XP
D5 Prof
BeitragVerfasst: So 24.02.13 20:37 
Was ist erst, wenn Du dann Mathematiker findest!!!

_________________
Toleranz ist eine Grundvoraussetzung für das Leben.
Martok
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 3661
Erhaltene Danke: 604

Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
BeitragVerfasst: So 24.02.13 21:21 
Ich überlege grade, ob man nicht BBP 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.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1652
Erhaltene Danke: 243

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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