wirklich große Zahlen unter Delphi

[CalganX]

Zitat von Der_Unwissende:

Was heißt denn hier wenn überhaupt? Natürlich wird ein Exponent abgespeichert! Wie soll denn bitte eine Gleitkommazahl ohne berechnet werden?

Ungünstig formuliert, stimmt...

Zitat:

Wo kommt denn jetzt dieses Wissen her? Hilfe! Ich meine schau in die Delphi Hilfe, da steht dass Extended 10 Byte verwendet, 10 Byte = 80 Bit > 64 Bit.

Ich habe kein Delphi installiert und somit auch keine Delphi-Hilfe, auf die ich auf die Schnelle zugreifen könnte. Aber wenn das dort so steht, dann habe ich mich falsch erinnert. Errare humanum est.

Zitat:

Dann kannst du gleich deine eigene Quelle bemühen, da steht:
Extended = 64 Bit Mantisse und 15 Bit Exponent (1 VZ Bit).

Ich war mir nicht sicher, ob die Angaben dort mit Delphi übereinstimmen...

Chris

[r2c2]

Zitat von 3_of_8:

Wenn du wirklich große Zahlen suchst, nimm Extended. Das Teil kann sehr große Zahlen verarbeiten, allerdings dann nur noch auf maximal 20 Stellen genau, dafür jedoch fast beliebig groß.

Beliebig groß nicht. Maximal 2^80(25 Stellen). Da Extended ein Float is, eigenet sich das Viech wohl eher weniger für die Faktorisierung...

Zitat:

Ansonsten geht Int64 genauso wie Integer, nur ist es kein Ordinaltyp, das heißt du kannst sie nicht für Schleifen verwenden.

Seit wann das? *grad nochmal nachguckt* Ui...jo...hast Recht...

Zitat:

EDIT: Wenn dus noch größer brauchst, verwende die DECMath von Hagen.

Wollt auch grad sagen. Es gibt u.a. von Hagen Lösungen für dieses Problem. Wie das dann allerdings mit der Performance aussieht, weiß ich nicht. Wobei ich Hagen zutraue alle Register zu ziehen und das ganze auch sehr performant hinzukriegen...

//Edit:
Ah.... Hilfeee.... So langsam war ich auch noch nicht. Der Post um 17:50 Uhr war der letzte den ich gesehen hab... 2h zu spät.... ich werd alt... kommt davon, wenn man zwischendurch was anderes macht(essen...) und später antworten will... Und der rote Kasten hat mich noch nichtmal gewarnt... *heul* Ich will den roten Kasten wieder haben *quängel* Hoffentlich beeilt sich Cheffe mit der DP 2006... *schluchtz*

mfg

Christian

[3_of_8]

Hehe, gibts irgendwas was die DEC respektive Hagen nicht kann?

Und wenn, dann auch noch schnell.

Also ich konnte mich eigentlich nicht beschweren, als mir Hagens DEC Math in 10 Sekunden ein paar Millionen Nachkommastellen der Quadratwurzel von 2 geliefert hat.

[Antigo]

danke für soviele antworten


Dieses Decmath scheint vielversprechend. Jetzt muss ich das nurnoch in mein Programm einbauen ^^
Gibt es irgendwo eine Dokumentation für alle Funktionen der Unit NInts? Das fände ich ziemlich hilfreich, denn ohne weiss ich noch nichtmal wie ich überhaupt eine Variable des typs IInteger erzeuge...


jetzt werde ich wohl auch von for auf while schleifen umsteigen müssen...

[Antigo]

Ich habe jetzt ein Array von IInteger Werten, in dem ich meine Primzahlen speichern möchte. Ich hab eine Funktion die mir die "nte" Primzahl geben soll. Die guckt nach ob die geforderte Primzahl schon im Array steht, wenn nicht dann wird sie errechnet. Dabei mache ich (bisher) folgendes:

Delphi-Quellcode:

 if length(primzahlen)-1 >= n then begin
  //wenn Primzahl bereits errechnet, dann ausgeben
    result:=primzahlen[n];
  end
  else begin

Jetzt ist n aber auch eine IInteger Zahl. length(primzahlen)-1 hingegen ist eine Integer Zahl. Wie vergleiche ich die beiden miteinander? Und bekomme ich nachher Probleme weil mein Array zu groß wird?

[negaH]

Hi

Da will ich mich mal nicht lumpen lassen und einige zusätzliche Infos rüberwachsen lassen.

1.) im Ordner \Intf\ des ZIPs findest du alle Interfaces der Units aus dem DECMath. In der Datei NInts.pas findest du dann auch alle Funktionen samt Remarks dazu.

2.) DECMath enthält schon ein Objekt TSmallPrimeSieve in Unit Prime.pas. Mit diesem Sieb hats du sehr schnell alle Primzahlen zwischen 2 bis 2^32-1 zur Verfügung.

Beispiel für die Benutzung

Delphi-Quellcode:

var
  I,P: Cardinal;
begin
// Ausgabe der 100'ten bis 1000'ten Primzahl
  for I := 100 to 1000 do
    WriteLn( Primes[I] );

// suche Index der Primzahl 13
  WriteLn( Primes.IndexOf(13) )

// Überprüfung ob Cardinal eine Primzahl ist
  if IsPrime(123456789) then

end;

3.) diese Primzahlsieb wird nun in einigen Faktorizations Funktionen der IInteger benutzt

Beispiel

Delphi-Quellcode:

var
  N: IInteger;
  F: Cardinal;
begin
  NRnd(N, 128);  // 128 Bit großen Integer erzeugen

  repeat
    F := NSmallFactor(N);
    if F > 1 then 
    begin
      WriteLn(F); 
      NDiv(N, F);  // N := N / F; 
    end; 
  until F <= 1;

  WriteLn(NStr(N)); // N ausgeben

  if NIsProbablePrime(N) then WriteLn('is prime)
    else WriteLn('is composite');
end;


function NSmallFactor(const A: IInteger; Bound: Cardinal): Cardinal;
// Result == 0 if A = 0
// Result == 1 if A is not divisible by all primes <= bound or
//             if A is < 2^32 if A is prime
// Result >= 2 small prime divisor
// about <10000 Cycles per digit and Bound = $FFFF and A >= 2^960
// 2.6 times faster as with the use of normal NMod() operation
// about <96 Cycles per digit and Bound = 239 and A >= 2^960
// the growrate isn't linear, bigger A are faster tested per digit

NSmallFactor(N) ermittelt ob eine Zahl N durch eine Primzahl bis < 2^32 teilbar ist. Wenn ja gibt NSmallFactor() diesen Faktor zurück. Dabei arbeitet diese Funktion mit hocheffizienten Verfahren die die modulare Division -> mod -> die normalerweise notwendig wäre ersetzt. Damit dürfte diese Funktion weitaus schneller sein als jeder normale TrialDivisons Ansatz. Gearbeitet wird in dieser Funktion mit einer Multiplikation zum moduarem Inversen der kleinen Primzahlen bis 2^32. Im Bereich bis 2^16 werden zb. durch ein einzigste dieser Multiplikation gleich 2 Primzahlen abgetestet. Ein weitere sehr performanter Test der als erstes durchgeführt wird wird mit einer Addition modulo 2^96-1 gearbeitet. Dieser Test reduziert die Zahl N modulo 2^96-1, was mit reinen Additionen durchführbar ist. Das Resultat (96 Bits Zahl) wird nun mit einer speziellen modularen DIvision ausgewertet und kann in einem Rutsch gleich 12 der kleinen Primzahlen austesten.

NTrialDivision(N) testet N ob es durch ein der kleinen Primzahlen geteilt werden kann. Diese Funktion liefert nur die Antwort ob die Zahl N "teilbar" oder "nicht teilbar" ist.

NIsProbablePrime(N) ist nun ein Pseudo Primzahl Test, so was ähnliches wie das Rabin Miller Verfahren. Damit kann man also jede beliebige Zahl auf Primzahl testen. Die Wahscheinlichkeit das diese Zahl dann auch eine Primzahl ist beträgt 1/N wobei N unser zu testende Zahl ist. Wenn du also zb. ein 512 Bit große Zahl damit testest dann ist die Wahrscheinlichkeit das sie denoch keine Primzahl ist obwohl der Test es meint nur 1/2^512 gruß, also fast unendlich klein. Deshalb nennt man solche getesteten Zahlen auch "industrielle Primzahlen". Nun, NIsProbablePrime() benutzt ein sehr sehr modernes Verfahren, das wesentlich schneller und auch sicherer ist als ein Rabin Miller Test. Das Verfahren das benutzt wird ist ein "Strong Probable Lucas Prime Test" nach "Pomerance, Selfridge, Wagstaff und Bailie". Zusätzlich testet dieses Verfahren auch noch ob N ein perfektes Quadrat ist -> N = X^2.

NIsProbablePrime() ist eine Allround Funktion, d.h. sie benutzt verschiedene Testverfahren um dann ein gutes ergebnis zu liefern. Als erstes eine Trial Divison mit NTrialDivison() und danach den SPP Test -> NSPP().

NSPP(N, array of Primes) -> Example: if NSPP(N, [2,3,5,7]) then

testet mit einem Strong Pseudo Primality Algorithmus die Zahl N. Dabei wird im Array [] die Zahlen angegeben zu denen getestet werden wollen (fast immer Primzahlen). Normalerweise reicht der Auffruf NSPP(N, [1, 2]) aber aus. In diesem Moment wird mit dem moderneren Bailie-Pomerance-Selfridge-Wagstaff-Test gearbeitet.


NMakePrime() erzeugt eine industrielle Primzahl

Delphi-Quellcode:

var
  P: IInteger;
begin
  NRnd(P, 512); // P zufällige Zahl mit 512 Bit Größe erzeugen

  NMakePrime(P, [1,2]); // erzeuge eine starke Pseudo Primzahl

  WriteLn( NStr(P) );
end;

So, das als grundsätzliches Handwerkszeug. Interessant sind auch noch die Lucas Funktionen -> NLucasMod() usw.

Aber das ist leider nur der Anfang. Auch deine Methode per Trial Divisionen mit den kleinen Primzahlen zu arbeiten ist wirklich nur der Anfang. Solche Verfahren sind die von der Komplexität her gesehen schlechtesten die es gibt. Dh. bei zahl größer 2^64 wird es weitaus besser Verfahren geben als die Trial Divison. Zb. Faktiorsation mit dem Zahlensieb (das bisher beste Verfahren), es arbeitet mit hoch komplexer Mathematik und sehr oft in Elliptischen Kurven (auch da enthält DECMath in den Units GFPs.pas zb. alles was man für Elliptische Kurven in GF(p) benötigt). Oder die Methoden nach Rabin, Williams+1, Pollard Rho, Pollard PP+1 usw.
Das sind alles Verfahren die weitaus effizienter Zahlen faktorisieren können.


Gruß Hagen

[Antigo]

danke für die ausführliche Antwort, die wird sicher auch vielen anderen weiterhelfen

Es ist mir klar das die Trial and Error Methode die ich implementiert habe bei weitem nicht effizient ist. Das war aber auch gar nicht mein Ziel. Genauso wenig ist es aber mein Ziel eine Methode zu implementieren die ein anderer geschrieben hat, und die ich (im Moment zumindest )nicht mal im Ansatz verstehe


Ich wollte auch eigentlich nur mein Programm an größeren Zahlen testen. Mit deinen IIntegers zu arbeiten ist dabei aber für mich leider nicht ideal. Ich muss dafür viel zu viel umwerfen. ich kann nicht einfach schreiben if i < round(sqrt(zahl)) sondern muss dafür ewig viele Schritte machen (zumindest nach meinem jetzigen Kenntisstand und nachdem was ich bisher rausgekriegt habe )

Ich hatte mir eigentlich einen Datentyp erhofft den ich einfach mit dem Standard Integer vertausche und fertig. Leider scheint das nicht so einfach zu sein (was ich irgendwo nicht verstehe) wie ich dachte.
Von daher werd ich mein Programm wohl so belassen.

Trotzdem vielen Dank für eure Mühe

[negaH]

Zitat:

Gibt es irgendwo eine Dokumentation für alle Funktionen der Unit NInts? Das fände ich ziemlich hilfreich, denn ohne weiss ich noch nichtmal wie ich überhaupt eine Variable des typs IInteger erzeuge...

Nach dem Entpacken hast du 2 Möglichkeiten:

1.) im Ordner \LibIntf\ sind alle PASCAL Header der Units enthalten. Da kannst du nachschlagen.
2.) im Ordner \Part_II\Demo\ findest du ein DEMO Projekt. In diesem wird die Benutzung der IInteger demonstriert

Ein IInteger ist wie ein normaler Integer anzusehen nur mit dem Unterschied
a.) das er so groß wir der gesamte Speicher sein könnte (als Zahl wohl gemerkt)
b.) er mit eigenen Funktionen rechnen muß (in Unit NInts)

ansonsten gibts fast keine Unterschiede, besonders nicht bei Zuweisungen, Allokation und Freigeben. Darum musst du dsich nicht kümmern und DECMath macht das alles automatisch für dich.

Beispiel

Delphi-Quellcode:

procedure DEMO;
var
  Sum: IInteger;

  function DoTest(const N: IInteger): Boolean; register;
  begin
    NAdd(Sum, N);
    Result := False;
  end;

var  
  A,B,C: IInteger;
  X: IIntegerArray;
begin
  // A,B,C sind hier schon auf NIL initialisiert. NIL ist per Definition im DECMath identisch zum Zahlenwert 0 !!

  NSet(A, 12);  // A := 12;
  NSet(B, A);   // B := A;  // @B == @A, B und A sind gleiches Speicherobjekt
  C := B;       // C := B := A;

  NAdd(B, C);   // B := B + C;  
  
  SetLength(X, 3);
  X[0] := A;
  X[1] := B;
  X[2] := C;
  
  NForEach(X, @DoTest); // für jedes Element eine Callback -> DoTest aufrufen.
                        // Diese Callback kann auf unsere Variablen im Stack zugreifen, hier Sum !!
     

  WriteLn( NStr(Sum) );  // ergibt Sum := A + B + C; 
end;

Wie du siehst, nichts freigeben, nichts allozieren, alles wird autom. gemacht.

Zitat:

if i < round(sqrt(zahl)) then

Delphi-Quellcode:

var
  T: IInteger;
begin
  NSqrt(T, Zahl);  // T := Zahl^0.5
  if NCmp(NInt(I), T) < 0 then ;
end;

1.) NSqrt(T, Zahl), berechne Quadratwurzel der Zahl und speichert das Resultat in T
2.) NInt(I), wandelt I in einen IInteger um
3.) NCmp(NInt(I), T) vergleich I mit T und gibt < 0 zurück wenn I < T, = 0 wenn I == T und > 0 wenn I > T.

Also nur 1 Variable und 1 Zeile Source mehr

Gruß Hagen

[Shaman]

Hey there

Ich spiele mit dem Gedanken, eine Unit für komplexe Zahlen zu schreiben und dafür ebenfalls Interfaces zu verwenden...
Wie siehts aus bezüglich Overhead? Also wenn man ganze Matrizen voll mit solchen Interfaced Numbers verwendet...

Gruss
Shaman

[Antigo]

Zitat:

Also nur 1 Variable und 1 Zeile Source mehr

jo in diesem speziellen Falle. Allerdings muss ich an vielen Stellen eine Variable und eine Zeile COde mehr hinschreiben

Aber jetzt bin ich auf jeden fall schonmal schlauer. NCmp(a,b) gibt -1 aus wenn a <b. 0 wenn a=b und 1 wenn a>b ist. Damit komme ich schonmal weiter.


Vielen Dank nochmal