Pi berechnen

[Chriss1006]

HAllo Leute,

ich würd gern man infos zusammentragen wie man ein Programm erstellen könnte mit dem man PI auf beliebig viele Stellen nach dem Komma berechnen kann und damit einen Quadcore auslasten kann. Super Pi kann ja nur einen Core auslasten, ich würd aber gern mal alle vier cores auslasten und gucken wie schnell das dann geht, bzw würd ich auch gern mal mehr als "nur" 32M stellen ausrechnen.

Also falls mir jemand sagen kann wie das zu machen ist, nur raus damit :-)

Danke
Gruß
Chris

 

[-Kenny-]

Ich denke nicht, dass es "mal eben" programmierbar ist.

Die Programmierer kommerzieller Software bzw. Games tuen sich sehr schwer mit solchen multi-thread-fähigen Anwendungen gerade in bezug auf einen Quad-Core.

 

[carom]

Bei Anwendungen wie Games etc ist die Interaktion der Threads auch viel komplexer, glaube nicht, dass man das vergleichen kann.
Ich sehe das Problem ganz wo anders. Ehrlich gesagt hab ich aus dem Stehgreif keine Ahnung, wie man Pi berechnet, aber es wird so sein, dass man Nachkommastelle nach Nachkommastelle hintereinander nach und nach bekommt. Da kann der zweite, dritte und vierte Kern nichts berechnen, solange der erste Kern nicht fertig ist mit seiner Nachkommastelle. Und wenn er fertig ist, dann könnte er die nächste Nachkommastelle auch gleich selbst berechnen, denn er hat ja nix zu tun, und Core 2, 3 und 4 stehen wieder gelangweilt rum. Man bräuchte eine Funktion, welche für eine x beliebige Nachkommastelle den passenden Wert berechnet, dann könnten die Kerne parallel arbeiten, denn kein Kern ist dann mehr auf die Ergebnisse der anderen angwiesen.

 

[asdfman]

http://en.wikipedia.org/wiki/Computing_π
http://en.wikipedia.org/wiki/OpenMP

 

[Humptidumpti]

So ein Programm gibt es schon. PiFast.

Lastet beliebig viele Kerne aus und berechnet Pi bis 17 billionen Nachkommastellen.

http://numbers.computation.free.fr/Constants/PiProgram/pifast.html

 

[Backslash]

Nur so, es sind Milliarden
Außerdem lastet das Programm zumindest bei mir nur einen Kern aus. Bin auch der Meinung, dass Multithreading bei der Berechnung nicht möglich ist, wenn doch jedenfalls nicht einfach.

/edit: quark, siehe unten

 

[Ack der III]

Ich habe mir mal die Mühe gemacht, ein bisschen was zusammenzutragen.
Ich habe eine Formel gefunden, die recht einfach ist und mit der schon die 51,5 Milliardste Nachkommastelle berechnet wurde. Hier mal die Formeln:

a = 1
x = 1
b = 1 / Wurzel aus 2
c = 0.25

            y = a;
            a = (a + b) / 2;
            b = Wurzel aus (b * y);
            c = c - x * (a - y) * (a - y);
            x = 2 * x;
            pi = ((a + b) * (a + b)) / (4 * c);

Die eingerückten Funktionen wiederholt man beliebig oft.
Wenn ich richtig liege, müsste zumindest teilweise Multi-Threading möglich sein.
Ich habs mal eben schnell programmiert und nach dem dritten mal kommt Pi auf die 14 Nachkommastelle korrekt raus.
Das Problem dabei ist aber, das der Computer max. mit 15 Nachkommastellen rechnet, also relativ ungenau und so kommt man nichtmal an die Millionen.

Die Lösung: Man muss einen neuen Datentyp schreiben, der die millionste(oder was weiß ich) Nachkommastelle speichern kann(Wahrscheinlich mit einem Array).
Dann schreibt man noch Funktionen für das binäre Addieren, das binäre Subtrahieren, das binäre Multiplizieren und das binäre Wurzelziehen und dann kann man die funktionen oben entsprechend schreiben, dann nurnoch binär in dezimal umrechnen(wenn man denn eine Ausgabe haben möchte; evt. stellt das aber ein Problem dar) und dann müsste es passen. Viel Spaß!^^

Edit: Ok, der Computer der mit dieser Formel die 51,5 Millionen Stellen berechent hatte, hatte insgesamt 212 GB Arbeitsspeicher. Und der ist auch nötig^^ Da müsste man ja gleich die Festplatte benutzen. Auch nicht schlecht: Ein Programm was das Zusammenspiel zwischen CPU und Festplatte testet^^

Ich hab mir mal den Link von STFU-Sucker angeschaut. Da wird auch der Algorithmus mit angegeben. Anscheinend fügt der pro Berechnung immer ungefähr 14 Stellen hinzu. Das Programm verfolgt also eine weniger speicherlastige Methode.^^ Ich raff aber die Formel nur zur Hälfte...mal Morgen schauen^^

 

[krizzelfix]

Man könnte PI ja auch auf jedem Kern neu berechnet werden.
Dann werden alle Kerne ausgelastet und mann muss sich keine gedanken über das aufteilen von Berechnungen machen.

Grüße

krizzel

 

[Ack der III]

So, ich habe mich mal mit PiFast auseinandergesetzt. Eine Millionen Stellen in 1,9 sec. Hätte nicht gedacht, dass das so schnell geht. Braucht bei höheren Stellen auch eine ganze Menge Arbeitsspeicher.
Leider versteh ich immernoch nicht, wie die Formeln funktionieren... Auf jedenfall berechen diese Formeln PI nicht ganz, sondern stückchenweise(Also z.B. erst die ersten zehn Stellen, dann die zweiten u.s.w.).
Dann ist auch Multi-Threading möglich. Der erste Kern rechnet die ersten Stellen, der zweite Kern die zweiten Stellen u.s.w. und nach jedem Schritt, werden die Stellen aneinander gereiht.

 

[Backslash]

Aber man benötigt doch immer die vorangehenden Stellen, also wäre kein Multithreading möglich.

 

[ag3nt]

Also das ist absoluter Unsinn.
Genau dafür gibt es nämlich die Bailey-Borwein-Plouffe-Formel. Allerdings erschließt sich mir der Sinn des ganzen vorhabens nicht ganz, denn was nützen mir 2 Millionen Stellen von π, einmal abgesehen vom virtuellen Schw***-vergleich?

 

[michi12]

Und genau das ist das Problem:
1) Es werden ein paar Nachkommastellen berechnet,
2) dann werden die nächsten paar berechnet, jedoch haben diese die aus 1) als Grundlage
3) dann werden die nächsten paar berechnet, jedoch haben diese die aus 2) als Grundlage
usw.
Das heißt, die jeweils nächsten können nur berechnet werden, wenn die vorherigen bekannt sind.
Somit ist kein Multithreading möglich, da ja der 2te Kern auf den ersten Kern warten muss.
Wenn es dann soweit ist, kann der erste Kern auch gleich selber weiter machen.

So habe ich das einmal gelesen. Wenn es doch geht, lasst es mich wissen

Edit:
@ag3nt:
Ok, dann ist es wohl abhängig von der verwendeten Formel !

 

[Ack der III]

Nach mehreren Stunden und etlichen Webseiten von Universitäten und sonstigem später, bin ich mir sicher, dass es Formeln gibt, wo man sagt: "Ich möchte die Nachkommastelle an Position x" und dann kann die ausgerechnet werden. Also kann der erste Kern z.B. alle geraden Positionen ausrechnen und der zweite alle ungeraden. Natürlich müssen die aufeinander warten, damit die Reihenfolge erhalten bleibt.

Edit: Auch kann man das an etlichen anderen Formeln sehen, bei denen eine Zahl bei null startet und dann immer um eins erhöht wird.

 

[Backslash]

Cool, wusste ich nicht
Hier gibts ne Umsetzung in VB (Link aus Wikipedia)

 

[Ack der III]

Jap, hab ich gesehen. Das Programm scheint aber nicht zu funktionieren(Zumindest in Java nicht). Ich teste das mal eben schnell mit meinem anderen PC.

Edit: Ok, in VB geht das Programm. Allerdings kann der auch nur die ersten 15 Nachkommastellen anzeigen.
In Java gibt er die ganze Zeit nur 4.0 aus. Kann Java nicht rechen??

Edit2: Ok, jetzt kann Java das auch richtig anzeigen. Hab einfach aus Integer für i double genommen.

 

[Chriss1006]

Leute ihr seid krass. ICh hab irgendwie nicht mal ansatzweise überhaupt die Formel für Pi verstanden.
Ich will das ganze nicht für nen virtuellen Schwanzvergleich. Wir nehmen in der Schule grad Pi durch und ham überlegt wieviele Stellen man berechnen mit normalen mitteln. Also das hat schon einen tieferen sinn.

Danke schon mal für die ganzen tipps. Werde das mal alles genauer anschauen.

 

[Ack der III]

Was heißt mit normalen Mitteln?^^
Vielleicht per Hand? Nun, einige Mathematiker die sich mit PI beschäftigt und dafür Formeln aufgestellt haben, haben hunderte Stellen per Hand berechnet.

Was ich noch gefunden habe und ganz interessant finde, ist dass ein US-Bundesstaat 1897 einfach PI = 4 festgelegt hatte.^^
Darüber wird sich sicher jeder Mathematiklehrer freuen.^^

 

[Chriss1006]

naja normale mittel heißt in meinem Fall ein PC mit ner AM Phenom CPU, also nicht irgendein mega Supercomputer mit unendlich flops. Sonder ein ganz normaler arbeitsplatz pc. Mal sehn wie weit der kommt.

 

[Backslash]

Wenn du dich wirklich damit beschäftigen willst wäre noch interessant wie es auf einer GPU mit CUDA aussieht