Langzahlentaschenrechner

Delphi-Laie · Verfasst: Fr 22.06.12 19:53

Los ging es bei mir bei diesem Programm ursprünglich mit einem kgV- und ggT-Programm auf der Basis der Integerdatentypen und nur des Euklidschen Algorithmus'. Doch viel Freude kommt damit wegen der Größenbeschränkung dieser Datentypen natürlich nicht auf. Irgendwann entschloß ich mich, meine Sammlung heruntergeladener Langzahlen-Units zu durchforsten. Am besten gefielen mir die beiden von Benny Baumann hier in diesem Forum vorgestellten, und die Implementation war relativ rasch erledigt. Einmal Blut geleckt, wollte ich damit diese feinen Units, vor allem die Nr. 2, für die ich Benny auch an dieser Stelle noch einmal danke und lobe, komplett ausprobieren, und außerdem kamen noch weitere Funktionen hinzu (Fakultät, Primfaktorenzerlegung). Herausgekommen ist dabei dieser

"Langzahlentaschenrechner".

Als seine Clous stufe ich

- die Primzahlenenumeration (wurde hier im Forum schon meinerseits vorgestellt),
- die verschiedenen Fakultätsgenerierungen (teilweise nach Peter Luschnys Internetseite)
- die Primzahlzerlegungen nach Fermat und Lehmann sowie
- die beschleunigte Exponentensuche bei der Primzahlzerlegung durch das Intervallhalbierungsverfahren

ein. Die Unit "BigNum2" erforderte kleine Korrekturen (nannte ich in seiner Diskussion), und ich fügte ihr einige wenige Funktionen hinzu, um den Quelltext meines Programmes etwas übersichtlicher zu gestalten. Dennoch sind manche Aufrufe wahre Monster an Funktionsverschachtelungen.

5.000! oder auch 10.000! sind kein Problem, und die Primfaktorenzerlegung dieser an Primfaktoren wahrlich reichen Zahlen ebensowenig eines.

Die Voreinstellungen sind so gewählt, daß sich der Geschwindigkeitszuwach tendenziell bei großen / langen Zahlen bemerkbar macht. Beispiel: Bei der Primzahlfaktorzerlegung muß maximal bis zur Quadratwurzel nach Primteilern gesucht werden. Das Wurzelziehen großer bzw. langer Zahlen dauert jedoch viel zu lang, also nehme ich einfach als Näherung die halbe Ziffernanzahl - wenn die bei den bis dato ergebnislosen Probedivisionen überschritten wird, ist die Zahl sicher prim. Das überschreitet die Wurzel teilweise deutlich, doch bei kleinen Zahlen macht es sich nicht sehr bemerkbar bzw. deren Wurzel ist schnell gezogen, und bei großen Zahlen findet man, wenn diese nicht nur aus relativ kleinen Primteilern bestehen, ohnehin keine vollständige Zerlegung.

Sollte ihn jemand ausprobieren: Viel Spaß damit, und Fehlermitteilungen sind willkommen. Allerdings prüfte ich ihn recht ausführlich, aber bei Programmen dieser Größe...

Etwas ähnliches schwebt mir nunmehr mit Polynomen vor, die letztlich auch eine ähnliche (prinzipiell gleiche? Naja, Polynome als Exponenten kenne ich nicht) Arithmetik erlauben... So eine Art Polynomtaschenrechner. Bei denen existieren allerdings zwei Formen (Produkt- und Summenform), und das Zerlegen der Summenform für die Gewinnung der Produktform ist schwierig (Nullstellensuche ist bei großen Polynomen nicht formal oder gar trivial möglich), umgekehrt geht es ja mit dem Wurzelsatz nach Vieta. Daß manche Polynome trotz ganzer bzw. reeller Koeffizienten keine reellen Nullstellen und damit reelle Linearfaktoren haben (sondern nur reelle Quadratfaktoren), kommt noch erschwerend hinzu.

Edit 1: Die Primzahlenenumeration wurde korrigiert, sie verschlang zuviel Speicher (s. "Ein Algorithmus zur Primzahlenenumeration").
Edit 2: Kleinen Fehler in der Eingabeprozedur behoben: Die Trim-Funktion funktionierte ab der 2. Eingabe nicht mehr, Grund unbekannt.
Edit 3: Fehler bei Argumenteingabe für Randomfunktion behoben.
Edit 4: Langzahlenquelle "Multipräzisionsarithmetik (MPA)" von gammatester bzw. Wolfgang Ehrhardt (www.wolfgang-ehrhard...e/mpa_2012-09-14.zip) hinzefügt. Etliche kleine Fehler beseitgt.
Edit 5: Berechnung der Catalanschen Zahlen hinzugefügt. Russische Bauernmultiplikation vereinfacht. "Doppelte" Buttons für separate Berechnungen iterativ/rekursiv entfernt; das ist dafür nun mit einer Radiogroup umschaltbar.
Edit 8: Funktion für Potenzturm (=Kettenpotenz?) hinzugefügt.
Edit 9: Mehrere Fehler beseitigt. Neue Funktionen hinzugefügt. Formular "aufgeräumt" (visuelle Eingabe-/Steuerelemente entfernt, Bedienlogik korrigiert und etwas vereinfacht). Sammlung noch zu implementierender Langzahlenunits hinzugefügt.
Edit 10: Nunmehr ist die Eingabe negativer Zahlen möglich. BigNum2 wurde auf negative Zahlen erweitert. Zwei weitere Langzahlenbibliotheken (die Unit "FGInt" von Walied Othmann (an etlichen Stellen im Internet zu finden) sowie die Unit Ziffernlisten aus dem Arbeitsbuch zu Turbo-Pascal 4.0) wurden hinzugefügt - weitere sind geplant. Und zuguterletzt (wie immer): Mehrere Fehler, die ich nicht alle einzeln aufzählen möchte (sind ja schließlich Geschichte), korrigiert.
Edit 11: Berechnungen in jeweils einen Extrathread ausgelagert (das Formular ist damit währenddessen nicht "eingefroren"). Karazuba-Multiplikation hinzugfügt. Und natürlich, wie immer, einige kleine Fehler beseitigt.
Edit 16: Mehrere kleine Überarbeitungen (Fehlerbeseitigungen sowie Verbesserungen hinsichtlich Geschwindigkeit)
Edit 17: Langzahlenarithmetikquelle (Unit) namens GNURZ von Alexander Staidl (forge.lazarusforum.de/projects/gnurz) hinzugefügt. Code für Steuerelemente überarbeitet und etliche kleine Fehler beseitigt.
Edit 18: Langzahlenarithmetikquelle (Unit) namens uBigIntsV3 aus dem Archiv DFFLibV14 von Gary Darby hinzugefügt, außerdem mehrere Fehler beseitigt.
Edit 19: Funktion "Subfakultät" sowie Langzahlenbibliothek "PMPInteger" au den Open StreamSec Tools Version 2.1 (www.streamsec.com) von Katja Wibell und Henrick Wibell Hellström hinzugefügt (inkl. zwei Fehlerkorrekturen in der Divisionsfunktion, erhalten von Henrick Hellström). Etliche Detailkorrekturen und -verbesserungen.
Edit 20:
- Langzahleneingabe im Edit verbessert, jetzt nur noch zahlenrelevante Eingaben möglich,
- iterativen ggT beschleunigt (bricht bei 1 ab),
- Wurzel- bzw. Wurzelstellenanzahl nach jeder Primdivion jetzt optional,
- Langzahlenbibliothek DECMath von negaH (Hagen Reddmann) hinzugefügt (deshalb jetzt D-5-Compilat),
- Fehler bei Primzahlenumeration und Lehman-Primzahlfaktorisierung beseitigt und
- Reihenfolge der Langzahlenbibliotheken alphabetisch geordnet.
Edit 21:Da meiner letzten Veröffentlichung auf unerklärliche Weise die Pacal-Unit-Dateien fehlten, schiebe ich hier eine Arbeitsversion, in der die Langzahlenbibliothek "NX" von Marcel Martin erstmal nur bis zur neu hinzugefügten Quadratierungsfunktion implementiert ist, nach. Außerdem ist es nun wieder ein Delphi-4-Compilat. Weitere Neuigkeiten:
- Kopieren von Listbox zu Editfeld autoamtisch,
- Ausgabe-Edit (Richedit) schaltet jetzt seinen Scrollmodus automatisch um: Scrollt nur noch bei den Primzahlausgaben nach - unten (letzteres auch automatisch),
- optionales Anzeigen der Wurzelberechnungsphase bei den Primfaktorzerlegungen,
- Rechenabbruchmöglichkeit durch gewaltsames Beenden des Rechenthreads (deshalb unsicher bis fragil, kann zum Absturz führen) und
- Speicherlecks teilweise vermindert (wird fortgesetzt),
- markierte Position nach Eingabe jetzt auch am Anfang möglich,
- Quadratierungsfunktion hinzugefügt,
- Zufallszahlen jetzt mit unterer Grenze>0 (für ggT-Berechnungen günstiger),
- Möglichkeit, die Listbox beschleunigt mit Zufallszahlen zu füllen, was sich insbesondere bei vielen lohnt, sowie
- viele kleine Fehler beseitigt.
Edit 22: Langzahlenbibliothek "NX" von Marcel Martin komplett interiert (Dank für die Zurverfügungstellung an Horst_H & ub60!). Multifakultät und "Produkt von bis" zu einer Funktion verein(ig)t.

Das Projekt kann wegen der mit Delphi 4 compilierten Units des DECs nur mit Delphi 4 compiliert werden, bei einem anderen Delphi (5-7) bitte die veröffentlichten DCUs für das jeweiligen Delphi verwenden oder sich vertrauensvoll an mich wenden, vielleicht kann ich weiterhelfen.

Einloggen, um Attachments anzusehen!

Delphi-Laie · Verfasst: Sa 23.06.12 18:33

An alle Interessenten dieses Programmes: Die Erstversion hatte natürlich doch noch ein paar Unsauberkeiten, die ich behob (neue Version oben). So konnte man z.B. Buttons, die zwei Zahlenwerte für die dahinterstehende Berechnung als Eingabe erfordern, auch dann bedienen, wenn nur ein Wert in der Eingabeliste war, was zu einer Fehlermeldung führte.

Außerdem fügte ich noch die Binomialkoeffizientenberechnung (mit drei verschiedenen Methoden) und drei weitere, "besondere" Fakultäten hinzu: Superfakultät, Hyperfakultät und Multifakultät (nachzulesen im peinlichen Internetuniversallexikon bzw. in der peinlichen Interentenzyklopädie). Die Superfakultät ist die Fakultät der Fakultäten. Das läßt sich sogar folgendermaßen verallgemeinern, sodaß Superfakultäten aller Grade oder Ordnungen oder Ränge (oder was auch immer) möglich sind:

Grad 0: Die Zahl n selbst
Grad 1: n!
Grad 2 (= 1. Superfakultät): Fakultät über alle n!, also 2!*3!* usw.
Grad 3 (=Superfakultät 2. Grades): Fakultät über alle Superfakultäten, die dann die Faktoren sind,
Grad ...usw.

Das zu implementieren hätte ich ohne die von mir einstmals verschmähte Rekursion nie geschafft. Kurzum, (auch) damit lassen sich herrlich große Zahlen erzeugen, die nur auf ihre weitere Verarbeitung, allem voran ihre Primfaktorenzerlegung, warten. Gut zerlegbar sind sie, denn sie enthalten nur kleine Primteiler.

Gruß Delphi-Laie

IhopeonlyReader · Beiträge: 600 Erhaltene Danke: 23 Delphi 7 PE

Soweit ganz gut, aber du könntest den Quelltext erheblich vereinfachen, wenn du z.B. bei Buttons_Deaktivieren
folgendes Schreibst:
(anstatt: Form1.Button1.Enable := False;
Form1.Button2.Enable := False;...)

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

var i:integer; k: Tcomponent;
begin
for i:=0 to ComponentCount-1 do
  begin
  K := Components[i];
    if K.ClassType = TButton then
      begin
      (K as TButton).Enabled := False;     
      end;
  end;
end;

_________________
Sucht "neueres" Delphi

Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!

Nersgatt · Verfasst: Mo 25.06.12 08:05

Würde vielleicht Übersichtlichkeit bringen, aber auch unnötige Arbeit. Immerhin muss das Programm dann alle Komponenten iterieren und abfragen ob es ein Button ist. Halte ich nicht für sinnvoll.

_________________
Gruß, Jens
Zuerst ignorieren sie dich, dann lachen sie über dich, dann bekämpfen sie dich und dann gewinnst du. (Mahatma Gandhi)

Delphi-Laie · Verfasst: Mo 25.06.12 09:22

Hallo IhopeonlyReader und auch Nersgatt, danke!

An so etwas dachte ich auch schon, allerdings hatte ich bisher nur einmal mit FindComponent zu tun und war froh, als ich es damals schaffte. Und "as" als Schlüsselwort setzte ich noch nie ein.

Außerdem ist die Numerierung der Buttons im Verlaufe der Programmierung doch etwas unübersichtlich und inkonsistent geworden: Sie kamen - und so auch ihre aufsteigenden Nummern - in der Reihenfolge, wie die Ideen aus mir sprudelten. Und nicht alle Buttons sind zu (de-)aktivieren.

Gruß Delphi-Laie

IhopeonlyReader · Beiträge: 600 Erhaltene Danke: 23 Delphi 7 PE

Delphi-Laie hat folgendes geschrieben :

Hallo IhopeonlyReader und auch Nersgatt, danke!

Gerne, ich muss ja auch was zurückgeben

Vorallem da ich Selbstbeibringer bin und ihr mir SEHR helft

Delphi-Laie hat folgendes geschrieben :

Außerdem ist die Numerierung der Buttons im Verlaufe der Programmierung doch etwas unübersichtlich und inkonsistent geworden: Sie kamen - und so auch ihre aufsteigenden Nummern - in der Reihenfolge, wie die Ideen aus mir sprudelten. Und nicht alle Buttons sind zu (de-)aktivieren.

Ist doch kein Problem, das lässt sich leicht mit einbauen

Mit einer If-Abfrage kannst du Abfragen ob es einer von den buttons ist, der aktiviert werden soll oder eben nicht...

also

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

var i:integer; k: Tcomponent;
begin
for i:=0 to ComponentCount-1 do
  begin
  K := Components[i];
    if K.ClassType = TButton then
      begin
      if not(K.name='Button3') and not (K.name='Button6')  then
      (K as TButton).Enabled := False;     
      end;
  end;
end;

Aber vielleicht ist ja auch ein kompletter Enable-Change das einfachste ;D
Also alle Enabled = true werden zu false und andersrum...
das würde mit folgendem quelltext gehen:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

var i:integer; k: Tcomponent;
begin
for i:=0 to ComponentCount-1 do
  begin
  K := Components[i];
    if K.ClassType = TButton then
      begin
      (K as TButton).Enabled := not (K as TButton).Enabled;     
      end;
  end;
end;

Ich hoffe ich konnte helfen

PS.: Das ganze lässt sich natürlich auch kombinieren, denn falls diese Prozedure (ich glaub bei dir wurde sie mit Enter aufgerufen, aber allgemein mal) mit einem Button aufgerufen wird, dann sollte dieser Button natürlich dabei NICHT unenabled gemacht werden

Dazu dann mal

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

//Abfragen ob es ein button ist und wenn dann
begin
if not (K.Name=TButton(Sender).Name) then
(K as TButton).Enabled := not (K as TButton).Enabled;     
end;
//und die andern abfragen mit end abschließen

_________________
Sucht "neueres" Delphi

Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!

Delphi-Laie · Verfasst: Mo 25.06.12 14:25

Danke, aber das ist mir viel zu umständlich. Ich bin kein "Hardcoreprogrammierer", kein Programmierer aus Leidenschaft, sondern ergebnisorientiert: Nicht der Weg ist mein Ziel, sondern nur das Ziel als solches. Code muß deshalb bei mir nicht die maximal (möglich)e Komplexität besitzen, das lenkt meine Konzentration nur vom gewünschten Ergebnis ab, korrekt hingegen muß er schon sein. Dennoch ist es natürlich wertvoll, daß solch ein Code hier veröffentlicht wird.

IhopeonlyReader hat folgendes geschrieben :

denn falls diese Prozedure (ich glaub bei dir wurde sie mit Enter aufgerufen, aber allgemein mal) mit einem Button aufgerufen wird, dann sollte dieser Button natürlich dabei NICHT unenabled gemacht werden

Mit Enter rufe ich das Verschieben eines manuell eigegebenen Wertes in die Startwertelistbox auf. Ich lasse die Buttons deshalb deaktivieren (läßt sich aber über die Checkbox auch abschalten), damit man gezwungen ist, den eingegebenen Wert auch dorthin zu verschieben, bevor die nächsten Rechnungen begonnen werden. Das deshalb, weil ich dieses Hinüberschieben vergaß und mich über Inkonsistenten wundert. Wirf das Zeugs raus, wenn es Dich stört. Mein Ergebnis ist sozusagen eine Arbeitsprobe und, da quelltextoffen, für jedermann beliebig veränderbar. Allerdings benötigen solche Programme genaugenommen nur Schüler, und die auch nicht unbedinggt, denn die sollen ja das Rechnen lernen und sich mathematisches Grundverständnis aneignen. Ist also eher eine Demonstration des Rechnens mit großen Zahlen.

IhopeonlyReader · Beiträge: 600 Erhaltene Danke: 23 Delphi 7 PE

Sagen wir einfach, es war ein Selbstversuch und Veranschaulichungsmaterial deiner Künste

_________________
Sucht "neueres" Delphi

Wer nicht brauch was er hat, brauch auch nicht was er nicht hat!

Delphi-Laie · Verfasst: Mo 02.07.12 16:47

IhopeonlyReader hat folgendes geschrieben :

Sagen wir einfach, es war ein Selbstversuch und Veranschaulichungsmaterial deiner Künste

Richtig, aber das trifft genaugenommen für jedes meiner Programme und letztlich sogar für die meisten Programme der meisten Programmierer (wenigstens im Freizeit-/Hobbybereich) zu.

Hallo Delphifreunde!

Wem obiges Programm gefiel und gefällt, den wird auch die neue Version interessieren: Ich implementierte die nächste Langzahlenbibliothek, und zwar die MP-Integerarithmetik von Wolfgang Ehrhardt.

Zunächst das Positive: Der Geschwindigkeitsunterschied zu der von mir schon als schnell empfundenen BigNum2-Unit ist beeindruckend (konkret: um ein Mehr- bis Vielfaches). Außerdem fand ich doch noch einige Fehler im Programm, die mir mit BigNum2 verborgen blieben.

MP-Arithmetik hat spürbar eine lange Entwicklungsgeschichte (scheint noch aus der Turbo-/Borlandpascalzeit zu stammen, da alles, was einen nichtfundamentalen Datentyp als Ergebnis liefert, nur als Prozeduren vorliegt) und ist deshalb sicher auch sehr ausgereift. Leider versäumte (oder vermied bewußt?) es der Autor, eine Anpassung an Delphi insoweit vorzunehmen, neben den Prozeduren auch Funktionen anzubieten oder wenigstens die Prozeduren in / mit Funktionen zu kapseln, um flexibler hantieren zu können. Das Arbeiten damit ist insgesamt eine Mühe, Geduldsprobe bis teilweise schon Qual und Zumutung: Kaum etwas funktioniert auf Anhieb, doch mit sehr viel Geduld bekommt man die "Zicken" (fast) beseitigt. Da intern alles mögliche "verzeigert" ist (sicher ein Hauptgrund für die hohe Geschwindigkeit), ist das Benutzen dieser Prozeduren/Funktionen ziemlich fragil, und es zeigen sich unerwartete und teilweise auch (mir) unerklärliche Phänomene. Die Hand kann ich deshalb für die Ergebnisse, die mit dieser Arithmetik gewonnen werden oder daß es keine Exceptions gibt, nicht ins Feuer halten. Noch vorhandene Fehler sind schwierig zu entdecken und setzen vor allem Reproduzierbarkeit voraus.

Mit dieser Arithmetikquelle lassen sich auch Fakultäten auch mit Argumenten jenseits der 10.000 gut bilden und wieder primfaktorisieren (also i.S.v. in Primfaktoren zerlegen).

Weitere Langzahlenbibliotheken/-units sollen folgen, ich habe noch einige gesammelt, so z.B.FGInt, aber auch andere. Kennt jemand noch eine schnellere (außer natürlich Hagen Reddmanns geheime Quelltexte)?

Gruß Delphi-Laie

Mathematiker · Verfasst: Mo 02.07.12 19:36

Hallo Delphi-Laie,
schöne, neue Variante Deines Programms. Es ist deutlich schneller.

Die Umsetzung mit MPArith ist interessant und vor allem die Kapselung der Prozeduren in Funktionen erleichtert die Arbeit ungemein.

Eine weitere interessante Möglichkeit wäre die Berechnung der Catalanschen Zahl. Die Catalansche Zahl tritt bei vielen Permutationsproblemen auf, z.B. bei der Anzahl von Klammerungen eines Produktes oder der Zerlegungsmöglichkeiten eines N-Ecks in N-2 Dreiecke.
Die n-te Catalansche Zahl C(n) ist die Summe aller Produkte C(k) C(n-k) für k=1,...,n-1, wobei als Startwerte C(0)=0 und C(1)=1 verwendet werden. Die 2500.Catalan-Zahl hat schon 1500 Ziffern.
Ich habe im Moment nur eine Variante mit FGInt. Vielleicht kannst Du es ja mit MPArith enbauen.

markieren

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:

procedure catalanzahl;
var z,i:integer;
    f1,f2,f3,f4 : TFGInt;
    Base10 : String;
begin
   z:=strtoint(edit1.text);    
   numberToFGInt(1,f1);
   i:=1;
   repeat
     numberToFGInt(2*z+1-i,f2);
     FGIntMul(f1,f2,f3);
     f1:=f3;
     numberToFGInt(i,f2);
     FGIntDivMod(f1,f2,f3,f4);
     f1:=f3;
     inc(i);
   until i>z;
   numberToFGInt(z+1,f2);
   numberToFGInt(i,f2);
   FGIntDivMod(f1,f2,f3,f4);
   FGIntToBase10String(f3,Base10); //in Base10 steht Resultat
   FGIntDestroy(f1);
   FGIntDestroy(f2);
   FGIntDestroy(f3);
   FGIntDestroy(f4);
end;

Beste Grüße
Mathematiker

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

Delphi-Laie · Verfasst: Mo 02.07.12 20:22

Hallo Mathematiker, danke!

Die Catalansche Zahlen kannte ich bis vor wenigen Minuten gar nicht. Scheinen "irgendwie" mit der Fibonacci-Folge verwandt zu sein, die Folge wächst aber doch deutlich schneller.

Also werde ich sie als nächstes implementieren - wohl nur iterativ. Rekursiv dauert schon bei Fibonacci mit Integer, spätestens Int64 viel zu lang (wegen der immer mehr zunehmenden, sich eben wiederholenden Mehrmalsberechnungen). Gerade wenn bei n über k n das Doppelte von k beträgt bzw. umgekehrt k die Hälfte von n, wird der Binomialkoeffizient maximal. Rekursion bringt also bei großen n nichts.

Fallen mir gleich wieder mindestens zwei Methoden ein: Fakultäten, Multiplikationen und zum Schluß die Division, oder - intelligenter - mit vorheriger "Kürzung", so daß die Laufvariablen nicht so lang laufen müssen. Allerdings kann man Fakultäten effizienter als mit der Kettenmultiplikation berechnen, was sich bei großen Fakultäten positiv bemerkbar macht.

Gruß Delphi-Laie

Gammatester · Beiträge: 328 Erhaltene Danke: 101

Mathematiker hat folgendes geschrieben :

Die 2500.Catalan-Zahl hat schon 1500 Ziffern.
Ich habe im Moment nur eine Variante mit FGInt. Vielleicht kannst Du es ja mit MPArith enbauen.

Die einfachste Methode ist doch wohl die Standard-Definition (siehe zB zu Wiki) verwenden: C(n) = binomial(2*n,n)/(n+1). Dafür gibt es die Funktion mp_binomial. Ohne extra ein Programm zu schreiben, hier ein paar Werte mit dem MPArith-Rechner; ich erhalte C(2500) in 0.259 ms und weiter:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

D:\Xtools\MPArith>t_calc.exe
Test of MPArith V1.20.24 (31/32 bit) [mp_calc]   (c) W.Ehrhardt 2006-2012
Type "?<enter>" to get some info about commands, "\q" or "quit" to end.

[D]:=> x=25
X = 25
[D]:=> binomial(2*x,x)/(x+1)
Result = 4861946401452
[D]:=> x=2500
X = 2500
[D]:=> binomial(2*x,x)/(x+1);
Result =  [>0,   4983 bits,  chksum=$7DC91C0F,  time=0.259 ms]
[D]:=> x=250000
X = 250000
[D]:=> y=binomial(2*x,x)/(x+1);
Y =  [>0, 499973 bits,  chksum=$6DF86E2B,  time=226.699 ms]
[D]:=> y mod 10^50
Result = 6047347006833293489207343995766341969796356416640

D.h. C(250000) wird in 0.226 s berechnet, hat ca 150000-Stellen; und die letzen 50 lauten: 6047347006833293489207343995766341969796356416640

Moderiert von Narses: Beiträge zusammengefasst

Delphi-Laie hat folgendes geschrieben :

MP-Arithmetik hat spürbar eine lange Entwicklungsgeschichte (scheint noch aus der Turbo-/Borlandpascalzeit zu stammen, da alles, was einen nichtfundamentalen Datentyp als Ergebnis liefert, nur als Prozeduren vorliegt) und ist deshalb sicher auch sehr ausgereift. Leider versäumte (oder vermied bewußt?) es der Autor, eine Anpassung an Delphi insoweit vorzunehmen, neben den Prozeduren auch Funktionen anzubieten oder wenigstens die Prozeduren in / mit Funktionen zu kapseln, um flexibler hantieren zu können.

Richtig, und da ich auch beruflich und privat noch viel mit BP7 arbeitete (mM ist die BP7-IDE den Delphis um Länge überlegen), wird die 16-Bit-Kompatibilität auch noch einige Zeit erhalten bleiben. Im übrigen haben auch die bekannten GNU-MP und MPIR genau diese prozedurale Struktur ohne die Hinterhalte von undurchschaubaren Compilermagics und dynamischen Arrays.

Delphi-Laie hat folgendes geschrieben :

Das Arbeiten damit ist insgesamt eine Mühe, Geduldsprobe bis teilweise schon Qual und Zumutung: Kaum etwas funktioniert auf Anhieb, doch mit sehr viel Geduld bekommt man die "Zicken" (fast) beseitigt. Da intern alles mögliche "verzeigert" ist (sicher ein Hauptgrund für die hohe Geschwindigkeit), ist das Benutzen dieser Prozeduren/Funktionen ziemlich fragil, und es zeigen sich unerwartete und teilweise auch (mir) unerklärliche Phänomene.

Das Arbeiten mit fremden Bibliotheken ist wohl oft Gewöhnungssache, aber der selbstprogrammierte Code ist ja nicht zu Wegwerfen, dafür kannst Du Rechnerprogramme oder Skriptsprachen benutzen. Natürlich ist es einfacher statt mp_add(a,b,c) zu schreiben c := a+b (wobei die Implementation über Objekte/Klassen/Records gehen könnte). Aber versuch mal sinnvoll mp_exptmod(a,b,c,d) effizient nachzubilden, die offensichtliche Methode d := a^b mod c wird gnadenlos in die Hose gehen, da ja gerade nicht erst a^b berechnet werden soll, um dann mod c zu reduzieren. Wie bringst Du das Deinen Objekten bei? Die "Verzeigerung" ist nur der explizite Pascalstandard, klar und deutlich, nicht wie Delphi, wo man raten muß, ob nicht doch irgendwo eine implizite Dereferenzierung stattfindet.

Im denke, ich das meine Dokumentationen und Debugmöglichkeiten verglichen mit anderen Pascal/Delphi-Bibliotheken sehr gut sind (natürlich nicht so gut wie GMP etc mit den Hunderten von Progammierern).

Im Übrigen steht es jedem frei, eine OO-Shell um MPArith zuschreiben (so wie's das auch für Bignum2 gibt).

Viele Grüße
Wolfgang Ehrhardt (Gammatester)

Delphi-Laie · Verfasst: Di 03.07.12 18:00

Ob Du, gammatester, wirklich mit jenem Programmautor identisch bist, fehlt mir bisher der Nachweis. Ich nehme jedoch an, daß Du Dich nicht mit fremden Federn schmückst. Gemäß dem, was ich bisher hier im Forum bisher von Dir las, würde das zu Dir auch nicht passen. Mir ist auch klar, daß ein solches Werk das Ergebnis jahrelanger Mühen ist.

Solltest Du mein obiges Programm und vor allem dessen Quelltexte angeschaut haben (allen voran die mp_functions.pas), so käme Dir vielleicht das Grausen. Ich deklarierte in den Funktionen ständig eine Tempvariable, die ich allerdings nicht löschen kann/darf, um den an result übergebenen Wert nicht zu zerstören. Mit mp_copy(temp_mp_int,result) hingegen kommt es zu Exceptions. Beides schiebe ich auf die Zeiger, die ich noch nie mochte: Nicht nur wegen dieser Widrigkeiten, sondern weil sie umständlich zu handhaben sind und ihr Konzept als solches dem einer (jeden) Programmiersprache widerspricht (von Assembler einmal abgesehen, aber das ist keine Programmiersprache im engeren Sinne, da keine höhere - niedrige Programmiersprachen gibt es genaugenommen nicht). Und so zog sich das fast über die gesamte Implementierungsdauer hin, ich war leider überwiegend mit diesen Widrigkeiten beschäftigt. Die Mühe hat sich aber gelohnt, denn diese (Deine?!) Langzahlenbibliothek ist wirklich beeindruckend schnell. Und für diese Vorarbeit (wenn auch nicht speziell für mich geleistet) zolle ich Dir meinen Respekt und danke Dir!

Sei es, wie es sei, ich implementierte nunmehr auch die Berechnung der Catalanschen Zahlen (da wird sich der Mathematiker sicher freuen), und die russische Bauernmultiplikation vereinfachte ich, außerdem sparte ich Buttons für iterativ/rekursiv und verlagerte das in eine weitere RadioGroup (s.oben).

Im Internet findet man eine ganze Reihe Langzahlenbibliotheken für Pascal. Es gab sogar schon eine Pascal-Langzahlenbibliothek in "Das Arbeitsbuch zu Turbo Pascal 4.0" von Karl Udo Bromm, das ich mir erst noch besorgen muß (in der für Tubo-Pascal 6.0 scheint sie schon wieder verschwunden zu sein).

Gruß Delphi-Laie

Gammatester · Beiträge: 328 Erhaltene Danke: 101

Delphi-Laie hat folgendes geschrieben :

Solltest Du mein obiges Programm und vor allem dessen Quelltexte angeschaut haben (allen voran die mp_functions.pas), so käme Dir vielleicht das Grausen. Ich deklarierte in den Funktionen ständig eine Tempvariable, die ich allerdings nicht löschen kann/darf, um den an result übergebenen Wert nicht zu zerstören. Mit mp_copy(temp_mp_int,result) hingegen kommt es zu Exceptions. Beides schiebe ich auf die Zeiger, die ich noch nie mochte

Das hat überhaupt nichts mit Zeigern zu tun. Nehmen wir Deine Funktion:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

function mp_func_add(const a,b:mp_int):mp_int;
var temp_mp_int:mp_int;
begin
mp_init(temp_mp_int);
mp_add(a,b,temp_mp_int);
result:=temp_mp_int
end;

Eigentlich sollte es möglich sein, folgenden Funktion zu benutzen:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:

mp_func_add2(const a,b:mp_int):mp_int;
begin
  mp_init(result);
  mp_add(a,b,result);
end;

Was macht Delphi nun bei einer Anweisung c := mp_func_add2(a,b)? Es legt eine mp_int auf den Stack (das result in der Funktion), ruft die Funktion auf, und weist dann c := Result; zu. Und genau da liegt ein Problem: Dies geht gut, wenn c vorher nicht initialisert ist. Wenn doch wird, der Record von c einfach überschrieben und die gesamten Ziffern des alten c hängen irgendwo im Speicher. Man könnte, also immer mp_clear(c); c := mp_func_add2(a,b); schreiben, aber das ist ziemlich offensichtlich unschön.

Ja, Deine Funktionen können einen grausen machen :wink:

Wenn sie häufig benutzt werden, verbraten sie halt gnadenlos Speicher: ein paar Mal manuell für Quick-und-Dirty scheint OK, aber als Funktionen in einer Unit ohne Doku ist's halt ziemlich 'gefährlich'. Übrigens gibt es für diese Zwecke in MPArith die procedure mp_dump_meminfo in mp_supp (wenn Diagnostic oder Debug definiert ist), für einen Test mit Deiner Funktion

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

var
  a,b,c: mp_int;
begin
  mp_init3(a,b,c);
  mp_set(a,10);
  mp_set(b,42);
  c := mp_func_add(a,b);
  writeln(mp_decimal(c));
  mp_clear3(a,b,c);
  {$ifdef MPC_Diagnostic}
    mp_dump_meminfo;
  {$endif}
end.

ergibt sich dann die Ausgabe

markieren

Quelltext

1:
2:
3:
4:
5:
6:

52
Memory status:
 MemDiff : 64
 InitDiff: 1
 ACntHigh: 0
 ACntLow : 6

Das bedeutet: 6 Speicherallokation, 64 Bytes wurden nicht freigegeben, ein Variable wurde initialisiert aber nicht gelöscht.

Und noch ein Hinweis zur 'proceduralen' Schreibweise, ein Zitat des geschätzten Negah = Hagen Reddmann: Warum das Overloading nicht sinnvoll funktioniert und warum er letztendlich in seinem DecMath proceduren benutzt: www.delphipraxis.net/660648-post22.html

Gruß Gammatester

Delphi-Laie · Verfasst: Mi 04.07.12 11:07

OK, damit (z.B.)

markieren

Delphi-Quelltext

1:
2:

mp_init(result);
mp_add(a,b,result)

scheint es zu funktionieren, danke!

Warum allerdings

- ausgerechnet result initialisiert werden muß (das müßte doch "automatisch" mit jedem Funktionsaufruf vorliegen, jedenfalls wurde fehlendes mp_init(result) nie bemängelt!)
- dieses result dann nicht mehr gelöscht werden darf / muß (klar, der Wert geht sonst verloren) und das dann keinen Speicher mehr benötigt (oder entsteht die gleiche Speicherleiche wie beim unterlassenen Löschen der jeweiligen Temp-Variable?)

ist mir völlig unklar. Jedenfalls kam ich im Traume nicht darauf, result zu initialisieren, und so blieb mir die Chance, damit selbständig zum Erfolg vorzustoßen, leider verwehrt.

Gammatester · Beiträge: 328 Erhaltene Danke: 101

Delphi-Laie hat folgendes geschrieben :

Warum allerdings [...] ausgerechnet result initialisiert werden muß (das müßte doch "automatisch" mit jedem Funktionsaufruf vorliegen, jedenfalls wurde fehlendes mp_init(result) nie bemängelt!)

Result wird zwar (im aufrufenden Teil) angelegt, aber nicht initialisert,dafür bräuchte man halt Compilermagic, genau wir für die Anzweisung c := Result; eigentlich ein mp_copy(result,c) abgebracht wäre.

Delphi bzw. MPArith hat bei Deinen Funktionen ein nicht-initialiertes result deshalb nicht bemängelt, weil Du damit ja nicht 'gerechnet' hast. Du hast ja einfach (praktisch via Record-Move) result überschrieben; eigentlich wäre mp_copy(temp_mp_int, result) 'politisch' korrekt, und dann wär's bemängelt worden.

Ich habe übrigens Deine Catalan-Funktion ausprobiert. Du verwendest zwar jetzt offensichtlich Binomial-Koeffizienten (ist nicht ganz klar da der in einer Zeile mit Rudeln von strtoint auftaucht, wenn man solche Einzeiler sieht wird klar, weshalb Du Funktionen statt Prozeduren brauchst). Allerdings sollte man sinnvoller binomial(n,k) nicht als n!/k!/(n-k)! berechnen, da die einzelnen Fakultäten viel zu groß werden im Vergleich zu Ergebnis, und deshalb die Rechnungen auch langsamer sind:

markieren

Quelltext

1:
2:
3:
4:
5:
6:

[D]:=> binomial(50000,25000);
Result =  [>0,  49992 bits,  chksum=$44AC0268,  time=26.334 ms]
[D]:=> 50000!/25000!/25000!;
Result =  [>0,  49992 bits,  chksum=$44AC0268,  time=673.476 ms]
[D]:=> 50000!;
Result =  [>0, 708357 bits,  chksum=$6CD33357,  time=233.293 ms]

D.h. hier ist Zwischenergebnis 14mal größer als das Resultat, und die Rechnung ca 25mal länger. Besser ist es, eine optimierte Form von (n über k) = n*(n-1)*...*(n-k+1)/k! zu verwenden. Die schnelle mp_binomial findest Du in in mp_numth.pas.

Delphi-Laie · Verfasst: Mi 04.07.12 13:29

Deswegen stehen ja mehrere Catalan-Berechnungsmöglichkeiten zur Auswahl. "Zu große" Ergebnisse (seien es Fakultäten oder irgendwelche anderen Rechenergebnisse) gibt es mit Bitinteger-/-Number-Bibliotheken (fast) nicht mehr.

Ergänzung: Solche monströsen Einzeiler haben einen wesentlichen Vorteil: Sie verpacken Komplexität, die sonst mehrere Anweisungen mit stufenweisen Wertübergaben benötigen, in eine (eben komplexe) Anweisung und sparen damit Quelltext. Das ist ein, wenn nicht der wesentliche Vorteil der Funktionen. Dafür ist der Compiler schließlich da.

Delphi-Laie · Verfasst: Sa 11.08.12 17:41

Neue Version hochgeladen. Bei Interesse die Änderungen bitte dem Edit 10 des ersten Beitrages entnehmen.

Horst_H · Verfasst: Do 25.10.12 12:08

Hallo,

ein wenig offtopic, aber wäre es bei den vielen Multiplikationen und Divisionen nicht sinnvoll, auch die Primzahlzerlegung der Zahl mit zu speichern?Das hat ja den Effekt wie Logarithmus, Multiplikation wird zu Addition, Division zur Subtraktion, der Potenzen.
Bei Fakultäten würde man nur damit arbeiten und erst zum Ende die Zahl ausrechnen. ( Hat Hagen Reddmann nocht sowas auch mal in delphipraxis.net vorgestellt? )
Beispiel 1000!
Man bestimmt alle Primzahlen bis 1000. ( etwa 168 )
Dann addiert man die die Potenzen aller Faktorisierungen der Zahlen 2 bis 1000.
2 addiert eine 1 bei Primzahl 2
3 addiert eine 1 bei Primzahl 3
4 addiert eine 2 bei Primzahl 2
5 addiert eine 1 bei Primzahl 5
..
997 addiert eine 1 bei Primzahl 997
..
1000 addiert eine 3 bei Primzahl 2 und eine 3 bei 5 (2x2x2x5x5x5)

Damit hat man direkt die Primzahlzerlegung der Zahl und kann daraus die Zahl berechnen.
Mich wunderte nur die Zeitdauer der Primzahlzerlegung von 1000! Das waren ja mehrere Sekunden ;-)

Gruß Horst

Delphi-Laie · Verfasst: Do 25.10.12 12:24

Horst_H hat folgendes geschrieben :

Mich wunderte nur die Zeitdauer der Primzahlzerlegung von 1000! Das waren ja mehrere Sekunden ;-)

Yo, das ist natürlich unzumutbar lang, gerade für so eine Winzigzahl wie 1000! ;-)

Im Ernst, das Programm ist doch allgemeingültig, die eingegebenen Zahlen sind prinzipiell gleichberechtigt. Die Schnittstelle ist das Ergebnis, das als String vorliegt und dann optional als gleicher String in die Eingabelistbox überführt (kopiert) werden kann (oder eben manuell eigegebene Strings oder generierte Zufallszahlen). Mehr Informationen als die Zahl(en) selbst gibt es als Eingangsgröße für die Berechnungen (noch) nicht.

Anderenfalls müßte ich weitere dynamische Datenstrukturen im Hintergrund aufbauen und diese parallel zu jedem Langzahlentyp verwalten. Was für eine Heidenarbeit! Grundsätzlich denkbar wäre das, und ich kann mir auch vorstellen, wie ich das implementieren würde.

Mir geht es in erster Linie um Demonstration der wichtigsten, gebräuchlichsten Funktionen (was man darunter versteht - schon die der dritten Rechenstufe stellt nicht jede Langzahlengbibliothek zur Verfügung) und den Vergleich der Geschwindigkeit der Langzahlenbibliotheken (es werden noch mehr hinzukommen).

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme