Unbegrenzt viele Nachkommastellen

[OregonGhost]

Ich habe ganz gute Erfahrungen mit apfloat gemacht (http://www.apfloat.org).
Ich glaube, irgendwann gab es da auch mal einen Link zu einer Pascal-Variante, aber den finde ich nicht mehr...
Unter hfloat sind auch noch ein paar andere entsprechende Bibliotheken zu finden.

GMP hatte ich mal ausprobiert, bin damit aber nicht auf Anhieb klargekommen ;c)

CLN scheint auch ganz gut zu sein, beispielsweise wurde die Bibliothek für GiNaC (... is Not a CAS) ausgewählt.

[negaH]

apfloat und CLN sind um Längen besser zu benutzen als GMP. Aber all diesen Libraries ist eines gemeinsam, es sind Bibliotheken die sehr stark an das Denkkonzept von C/C++ anlehenen und darauf aufbauen. Aus meiner Sicht also unmodern und kompleziert.

Zitat:

Kennt einer was besseres?
Oder eine Library, die schon in Delphi übersetzt wurde?

Ja ich. Da ich selber eine solche Library von Grund auf entwickelt habe, in Delphi, finde ich naürlich meine Library wesentlich besser
Ich kann aber auch Fakten sprechen lassen.
- automatische Referenze Counting der Zahlenobjecte
- automatische Garbarge Colllection
- Typsicherheit
- Copy on Write Demand, also so wie es bei LongStrings der Fall ist
- völlig transparent für den benutzer, nicht wie bei GMP wo man sich um jeden Kleinktram selber kümmern muß
- super schnell, in weiten Teilen schneller als GMP, apfloat, CLN usw. Meine Implementation zur Berechnung von Pi ist auf Rang 3 der Weltliste.
- das GUI bleibt über interne Idle-Cacllbacks bedienbar und jede langandauerende Berechnung kann ohne Problem abgebrochen werden
- Speichermanagement ist vollständig Threadsafe und jeder Thread benutzt interen seine eigene Speicherverwaltung, dies bedeutet das mehrere Threads absolut voneineander abgespaltet sind bis runter zur Speicherverwaltung (also kein Blocking und Konsorten nötig)
- die Gesamtperformance aller Operationen ist über einen weiten Zahlenbereich optimiert. D.h. egal ob man mit Zahlen ca. 4096 Bit groß in der Kryptographie üblich arbeitet oder ob man Pi auf Millionen Stellen berechnen will, die Berechnung sind alle hoch optimiert weil die besten bekannten Verfahren benutzt wurden.


Und hier mal der komplette Pi Berechnungs-Source, einmal die Methode der Chudnovski Brüder und einmal nach dem Arithmetischen Mittel.

Delphi-Quellcode:

procedure NPi_Fast_Chudnovsky(var R: IInteger; Decimals: Cardinal);
// Chudnovsky's brothers Ramanujan with binary splitting
// this code is most only 2-3 Times slower as the fastests special PI-programs
// Some optimizations can be done, but here i wanted a readable code.
// One way to made it faster (~2 times) could be to avoid NBinarySplitting() and its
// callback.
{
1      12   inf  (-1)^n (6n)! (A+nB)
-- = ------ SUM: -------------------
pi   C^1.5  n=0  (3n)! (n!)^3 C^(3n)


A=13591409 B=545140134 C=640320

a(n) = (A+nB)
p(n) = -1(6n-5)(6n-4)(6n-3)(6n-2)(n6-1)(6n)
b(n) = 1
q(n) = (3n-2)(3n-1)(3n)(n^3)(C^3)
}
const
  k_A = 163096908;          // 12 *  13591409
  k_B = 6541681608;         // 12 * 545140134
  k_C = 53360;              // 640320 / 12
  k_D = 1728;               // 12^3 = 24 * 72
  k_E = 262537412640768000; // 1727 * k_C^3

  procedure DoPI(N: Integer; var D: TIIntegerSplitData); register;
  // the callback for binary splitting
  // max. n < ~306783379 then 6n << MaxInt
  // B[1] = 1, P[0] = 1, Q[0] = 1
  // don't touch B,P[0],Q[0] because NIL interfaces are here assumed to value +1
  begin
    if N > 0 then
    begin
      NSet(D.A, k_B);                  // a = k_A + n * k_B
      NMul(D.A, N);
      NAdd(D.A, k_A);

      NSet(D.P,   2 * N -1 );
      NMul(D.P,   6 * N -1 );
      NMul(D.P, -(6 * N -5));          // p = - (6*n -5) * (6*n -1)* (2*n -1)

      NSet(D.Q, k_C);                  // q = 72(n * k_C)^3      // 72 * n^3 * k_C^3
      NMul(D.Q, N);
      NPow(D.Q, 3);
      NMul(D.Q, 72);
    end else
      NSet(D.A, k_A); // A[0] = k_A
  end;

var
  P,Q: IInteger;
  S: Cardinal;
begin
  S := NBinarySplitting(P, Q, Trunc(Decimals / 14.181) +2, @DoPI, False);  // decimal approximation is very roughly !!

  NPow(R, 100, Decimals);
  NMul(R, NInt(k_E));
  NSqrt(R);           // R = (k_C^3 * 12^3 * 100^Decimals)^(1/2) * Q / P

  NMul(R, Q);
  NShl(R, S);
  NDiv(R, P);         // R = R * Q / P = R / S

end;

procedure NPi_AGM(var R: IInteger; Decimals: Cardinal);
{ computation of Pi with Arithmetic-Geometric Mean 

 AGM start with:
   a = 1, b = 1/Sqrt(2), t = 1/2, k = 1

 iteration:

   s = (a + b) / 2
   d = a - s
   d = d^2
   a = s
   s = s^2
   t = t - d * 2^k
   b = Sqrt(s - d)
   k = k +1

 final:
   pi ~ (a + b)^2 / 2t }

var
  A,B,D,T: IInteger;
  W: Integer;
begin
  Inc(Decimals, 3);           // +3 digits reserve
  NPow(R, 5, Decimals);       // R =  5^Decimals
  NShl(A, R, Decimals);       // A = 10^Decimals
  NShl(D, R, Decimals -1);    // D = 10^(Decimals -1)^2
  NSqr(D);
  NSqr(B, A);                 // B = (10^Decimals^2 * 2)^0.5 div 2
  NShl(B, 1);
  NSqrt(B);
  NShr(B, 1);
  W := 0;
  repeat
    NAdd(T, A, B);            // T = (A + B) div 2, new A
    NShr(T, 1);
    NMul(B, A);               // B = (B * A)^0.5
    NSqrt(B);
    NSub(A, T);               // A = (A - T)^2 * 2^W
    NSqr(A);
    NShl(A, W);
    Inc(W);
    NSub(D, A);               // D = D - A
    NSwp(A, T);
  until NCmp(B, A) = 0;
  NShr(D, Decimals);
  NDiv(D, R);
  NMul(D, 1000);
  NSqr(R, A);
  NDiv(R, D);
end;

IInteger ist der große Ganzzahl Typ, keine Allozierungen oder Deallozierungen sind nötig. Man arbeitet also mit IInteger'n so als wären es normale Integer Datentypen, obwohl sie enorm große Speicherbereiche dynamisch verwalten.
Ein Manko gibt es allerdings, bisher habe ich nicht die Zeit gefunden auch Fließkommazahlen zu implementieren. Es gibt also Vorzeichenbehaftete Ganzzahlen -> IInteger, Gebrochene Zahlen -> IRational, Modulare Polynome -> IPoly und alle nötigen Berchnungen in Elliptischen Kurven.

Gruß Hagen

[Dagon]

@ Hagen: Ich bin fast ein bisschen neidisch! So eine slebst geschriebene Bibliothek hätte ich auch gerne *träum*!

[Tyrael Y.]

@Hagen

hört sich super an.
Ist das ganze in einer Library gepackt oder kann man auch den Source haben?
Wo kann ich mir deinen Source bzw. deine Library runterladen?

Möchte es gerne mal testen.

Wenn noch die Fließkommaimplementierung dazu kommt und alles so ist wie du erklärt hast bin ich gespannt auf das Resultat.

Gruß

[negaH]

@the_master: mir ging es bei der Library nicht um besitzen, sondern um den Spaß die komlizierten math. Verfahren zu implementieren.

@Tyrael Y.: tja das ist so'ne Sache. Eigentlich liegt die Library bei mir auf'm rechner rum, ohne das sie weiterverwendet wird, heul. Momentan finde ich nicht die Zeit sie weiter zu entwickeln, geschweige denn überhaupt was daran zu machen. Andererseits habe ich über 3 Jahre daran gebastelt, und ganz nebenbei ca. 5 Gigabyte an mathematischen Dokumenten, Dissertationen, Sourcen usw. gesammelt. Im gesammten sind ca. 150.000 Zeilen Source in der Bibliothek davon ca. 75% in Assembler.
Nun, dies erklärt vielleicht warum ich so dran hänge und eigentlich noch nicht bereit bin sie frei in Netz zu stellen, könnt ja sein das ich als Freelancer noch Brötchen damit verdienen kann.

Ich habe aber in letzter Zeit einigen Leuten eine Version zur Verfügung gestellt. Sie ist für Delphi 5-7 verfügbar, und enthält alle DCU + Packages und ausgewählte Sourcen. So zB. die vollen Sourcen zur Berechnung von transzendente Konstanten wie Pi,Sqrt(2),ArcSin,e. Desweiteren meine Sourcen zur Berechnung der Fakultät einer Zahl, sprich N!, denn es gibt dafür ca. 7 verschiedene Algorithmen.

Leider ist das bisherige Feedback doch ziemlich gering, d.h. für mich persönlich ist dabei nicht viel rüber gekommen (sprich Bugs, Handling, verbesserungen usw.).

Gruß Hagen

[Tyrael Y.]

@Hagen
danke dir.

Ich werde es mal am Wochenende bissel testen, in der Woche bin ich
mit Projekten von der Arbeit beschäftigt.

Falls mir etwas auffallen sollte, melde ich mich auf jeden Fall.
(auch für positive Kritik )


Gruß

[negaH]

Selbst über negative Kritik würde ich mich freuen
Ach übrigens, obiges Packages ist für D5, ich liebe D5. Ich habe aber auch noch D6 und D7 Versionen.

Am besten du fängst mit dem Testproject im Ordner ..\Test\ an. (entpacken MIT Ornder !).
Das Wesentliche findest du in TestUnit.pas inkulsive Remarks.
Die Units NCombi.pas und NInt_1.pas liegen als vollständiger Source vor. Im Ordner ..\libint\ findest du die Header aller Units.

Gruß Hagen

[Unwissender]

Also, dass eine Million stellen mit einem Programm in 2,5 sek. berechnet werden ist lustig. Leider ist das Ergebnis dann aber falsch. Liegt allerdings an der Hardware. Ich gehe zumindest mal davon aus, dass du eine normale CPU (x86 oder irgendein Motorola oder Alpha) benutzt hast.
Und da diese CPU's mit Mantissen rechnen, entsteht der so beliebte Rundungsfehler der bei 1 mio. Stellen schon relevant ist. Um ein wirklich mathematisch korrektes Ergebnis zu bekommen, musst du diesen Fehler berücksichtigen und kannst einfach nicht mit der GPU deiner CPU arbeiten. Und alles andere schafft es nicht, in 2,5 sek. eine Gleitkommazahl zu berechnen, die > 1 mio signifikante Stellen hat.

[negaH]

Zitat:

Leider ist das Ergebnis dann aber falsch. Liegt allerdings an der Hardware.

Ich weiß ja nicht wovon du redest, aber ich kann dir garantieren, auch unabhänig von der hardware, das das letzenliche Resultat bis auf's letzte Bit absolut exakt sein muss. Zumindestens bei meinen obigen Berechnungen.

Das liegt eben daran das per Software die Fähigkeiten der CPU exakte Berechnungen durchzuführen, stark erweitert wurde. Statt nun nur auf 32Bit/48Bit exakt zu rechnen, rechnet die CPU nun auf Millionen Bits absolut exakt. Im grunde werden alle Berechnungen der CPU die Millionen Bits benötigen auf viele kleine Berechnungen von 32 Bit größe per Software runtergebrochen. D.h. sollen zB. zwei Zahlen a 64 Bit Multipliziert werden, was ja eine 32 Bit CPU nicht von Hause aus kann, wird die zusätzliche Sofware die CPU insgesamt 3 mal eine 32 Bit Multiplikation ausführen lassen. Am Schluß werden diese 3 kleinen Multiplikationen wieder zusammen geführt und flux ensteht ein 128 Bit Resultat das absolut exakt das Produkt der beiden 64 Bit Zahlen ist.

Angenommen eine CPU kann nur Zahlen bis 100 exakt berechnen. Wir wollen aber 123 * 456 ausrechnen. So wie DU es logischerweise machst geht nun auch di Software vor. Sie zerlegt 123 in 1*100 + 2*10 + 3, und 456 in 4*100 + 5*10 + 6. Nun lässt die Software die CPU die Teilprodukte ausrechnen, also 1*4, 1*5, 1*6, 2*4, 2*5, 2*6, 3*4,3*5,3*6 und baut alle diese Produkte im Speicher unter berücksichtigung derer Potenzen zu basis 10 wieder zusammen. So kann man auf jeder beliebigen Hardware auch deren Grenzen exakte Berechnungen durchzuführen, auf's fast unendliche erweitern (abgesehen vom nötigen Speicher und Zeitaufwand).

Zitat:

Also, dass eine Million stellen mit einem Programm in 2,5 sek. berechnet werden ist lustig.

Nein, nicht lustig, sondern Schweißtreibende Denkarbeit !

Gruß Hagen

[c113plpbr]

Erstmal Danke für die vielen Antworten (ob hilfreich oder nicht )
Um alles nochmals richtig zu stellen:
Er wettete (d.h. er wusste/weis es nicht), das die Millionste (Dezimale) Nachkommastelle (also ohne die Stellen vor dem komma ) 7 wäre/ist.
Und ich (bzw. wir Schüler) wetteten dagegen ... und er meinte, dass es an uns liegt dies zu beweisen, was heißt, dass ich ein Programm brauche das (möglichst) vor ihm die richtige (soweit nachvollziehbar) Wurzel ausrechnet, was wiederum heißt, dass ich einen code brauche (er soll es ja nachvollziehen können), den ich ihm zeigen kann ...
Trotzdem danke ich allen für die Mühe, denn ich möchte ja keine Ansprüche stellen ...