Autor |
Beitrag |
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Sa 17.05.08 18:35
Viele werden diese Unit sicherlich schon im Forum gesehen haben, manche auch mein vor Kurzem veröffentlichtes Versprechen gelesen haben; hier ist sie nun:
Die Großzahlarithmetik-Bibliothek BigNum2
Die aktuelle Version ist Version 0.2.1.20080517. Download gibt's im Anhang.
Was macht BigNum2?
Mit großen Zahlen rechnen ... Mit sehr großen Zahlen ...
Was kann BigNum2?
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:
| Function BM_Add(Num1, Num2: TBigNumber): TBigNumber; Function BM_Sub(Num1, Num2: TBigNumber): TBigNumber; Function BM_Divide(Num1, Num2: TBigNumber): TBigNumber; Function BM_Modulo(Num1, Num2: TBigNumber): TBigNumber; Function BM_DivMod(Var Num1: TBigNumber; Num2: TBigNumber): TBigNumber; Function BM_Multiply(Num1, Num2: TBigNumber): TBigNumber; Function BM_MultiplyMod(Num1, Num2, Module: TBigNumber): TBigNumber; Function BM_Power(Base, Exp: TBigNumber): TBigNumber; Function BM_PowerMod(Base, Exp, Module: TBigNumber): TBigNumber; Function BM_Log(Power, Base: TBigNumber): TBigNumber; Function BM_SquareRoot(Num: TBigNumber): TBigNumber; Function BM_XRoot(Num, Exp: TBigNumber): TBigNumber;
Function BM_CompareC(Num1, Num2: TBigNumber): Boolean; Function BM_CompareNC(Num1, Num2: TBigNumber): Boolean; Function BM_CompareNZ(Num1, Num2: TBigNumber): Boolean; Function BM_CompareZ(Num1, Num2: TBigNumber): Boolean; Function BM_CompareE(Num1, Num2: TBigNumber): Boolean; Function BM_CompareNE(Num1, Num2: TBigNumber): Boolean; Function BM_CompareL(Num1, Num2: TBigNumber): Boolean; Function BM_CompareLE(Num1, Num2: TBigNumber): Boolean; Function BM_CompareG(Num1, Num2: TBigNumber): Boolean; Function BM_CompareGE(Num1, Num2: TBigNumber): Boolean; Function BM_GCD(Num1, Num2: TBigNumber): TBigNumber; Function BM_LCM(Num1, Num2: TBigNumber): TBigNumber;
Procedure BM_Assign(Var Result: TBigNumber; Const Number: TBigNumber); Procedure BM_Optimize(Var Result: TBigNumber); Procedure BM_GCDOptimize(Var Num1, Num2: TBigNumber);
Function BMD_StrToBigNum(Str: String; HexInput: Boolean): TBigNumber; Function BMD_BigNumToStr(Num: TBigNumber; HexOutput: Boolean): String; Function BMD_FractionToStr(Num1, Num2: TBigNumber): String; |
Was ist geplant?
- Die Unit noch etwas aufräumen
- Das Laden und Speichern von Zahlen etwas vereinfachen
- Einige Funktionen aus BigNum_Lib (Siehe zweiter Anhang) einbauen
- Neue Funktionen in Jänicke's Wrapper-Klasse einbauen
Zugabe: BibNum_Lib
BigNum_Lib ist eine NOCH ÄLTERE Version einer Großzahl-Bibliothek von mir, die damals noch vollständig auf OOP-Basis geschrieben wurde. Diese hat sowohl ihre Vorzüge, als auch eine ganze Reihe an Nachteilen. Da ich festgestellt hab, dass in BigNum2 noch einige Funktionen (gerade in Bezug auf Primzahl-Arithmetik) fehlen, die bereits in BigNum_Lib enthalten waren, hänge ich beide Units an. Diese sind jedoch ausdrücklich source- und binary-inkompatibel. Ein Mischen beider Units ist daher nicht möglich.
Lizenz (Gilt für beide Dateien):
- Die Bibliothek darf für nicht-kommerzielle Zwecke frei und kostenlos genutzt werden; eine kommerzielle Nutzung ist nur mit schriftlicher Genehmigung von mir gestattet.
- Bei der Verwendung meiner Unit muss sowohl in der Dokumentation (sofern vorhanden ) als auch im Programm in den Credits ein Eintrag für die Verwendung der Bibliothek vorhanden sein.
- Die Weitergabe des Quelltextes ist gestattet, solange der Kopfbereicht, mein Name als auch die Nutzungsbedingungen unverändert erscheinen.
Feedback:
Wie immer gern gesehen!
Einloggen, um Attachments anzusehen!
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
Zuletzt bearbeitet von BenBE am Sa 17.05.08 20:34, insgesamt 2-mal bearbeitet
|
|
g1o2k4
Beiträge: 493
|
Verfasst: Sa 17.05.08 18:59
super. vielen dank !
kanns nur weiterempfehlen !
|
|
Motzi
Beiträge: 2931
XP Prof, Vista Business
D6, D2k5-D2k7 je Prof
|
Verfasst: Sa 17.05.08 19:18
Frage: wieso verwendest du ein array of Byte und nicht ein array of Word? Das Ergebnis von Addition/Multiplikation zweiter 16-Bit Words kann ein 32-Bit DWord sowieso nicht überschreiten, aber du würdest nur mehr die halbe Anzahl an Rechenoperationen benötigen...
_________________ gringo pussy cats - eef i see you i will pull your tail out by eets roots!
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Sa 17.05.08 19:30
@ g1o2k4: Das hört man doch gerne. Bin über jegliche Anregungen, Verbesserungsvorschläge und Patches wie immer höchst erfreut.
@ Motzi: Das wäre zu überlegen, zumal es ja theoretisch sogar die Möglichkeit gäbe, mit DWORD zu rechnen und den 64-Bit-Datentyp der CPU (mit ein wenig ASM) herzunehmen. Muss ich mir mal in Ruhe anschauen, aber da ich derzeit noch einige Projekte offen hab, wird das sicherlich noch etwas Zeit in Anspruch nehmen, bis ich da dazu komme.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
ub60
Beiträge: 762
Erhaltene Danke: 127
|
Verfasst: Sa 17.05.08 19:55
Irgendwie waren noch 3 Copy&Paste-Fehler drin. So sollte es gehen:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18:
| Function BM_PowerMod(Base, Exp, Module: TBigNumber): TBigNumber; Const C: Array[0..7] Of Byte = ($01, $02, $04, $08, $10, $20, $40, $80); Var i, j: Integer; Begin Result := BMD_StrToBigNum('1', false); For i := High(Exp) Downto 0 Do Begin For j := 7 Downto 0 Do Begin Result := BM_Multiply(Result, Result); If (Exp[i] And C[j]) > 0 Then Result := BM_Multiply(Result, Base); Result := BM_Modulo(Result, Module); End; End; End; |
Ansonsten eine super Sache!
ub60
PS: Exp halte ich für keinen so sinnvollen Variablennamen.
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Sa 17.05.08 20:33
@ ub60: Ansichtssache. Als Exponent ist es zumindest aussagekräftiger als X.
So, hab mal eine neue Version hochgeladen. Download wie immer im ersten Beitrag.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
ub60
Beiträge: 762
Erhaltene Danke: 127
|
Verfasst: Sa 17.05.08 20:44
BenBE hat folgendes geschrieben: | @ub60: Ansichtssache. Als Exponent ist es zumindest aussagekräftiger als X.
|
Da stimme ich Dir zu. Ich meinte mehr die gleichnamige Exp-Funktion.
Ich hätte auch mit dem Namen "Exponent" leben können.
ub60
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Sa 17.05.08 20:47
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Motzi
Beiträge: 2931
XP Prof, Vista Business
D6, D2k5-D2k7 je Prof
|
Verfasst: So 18.05.08 12:00
BenBE hat folgendes geschrieben: | @Motzi: Das wäre zu überlegen, zumal es ja theoretisch sogar die Möglichkeit gäbe, mit DWORD zu rechnen und den 64-Bit-Datentyp der CPU (mit ein wenig ASM) herzunehmen. Muss ich mir mal in Ruhe anschauen, aber da ich derzeit noch einige Projekte offen hab, wird das sicherlich noch etwas Zeit in Anspruch nehmen, bis ich da dazu komme. |
Das ginge natürlich auch, allerdings müssten dann natürlich auch noch einige andere Stellen angepasst werden. Bei der Erweiterung von Byte auf Word müsste fast nichts geändert werden.
Gruß, Motzi
_________________ gringo pussy cats - eef i see you i will pull your tail out by eets roots!
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: So 18.05.08 14:19
Hallo,
was soll dieses divmodcar von mir in dem Code, wo es nicht benutzt wird?
Ich empfehle mal www.submanifold.be/triade/GInt/gint.html anzuschauen, welches mit longword/cardinal arbeitet aber nur 31 von 32 bit nutzt, damit kein Uebertrag beim Addieren auftritt.
www.efg2.com/Lab/Lib...tm#MultiplePrecision und dort angegeben
numbers.computation....ects.html#Algorithms ist auch eine schoene Seite fuer fft Multilplikation etc.
Mit freepascal und delphi kann man doch auch gmp nutzen
shootout.alioth.debi...idigits&lang=all
oder NX-numerics www.ellipsa.net/public/nx/nx.html mit Assembler in den Grundfunktionen
Gruss Horst
P.S.
Hagen Redmann hat ja leider keine sourcen dabei.
|
|
Motzi
Beiträge: 2931
XP Prof, Vista Business
D6, D2k5-D2k7 je Prof
|
Verfasst: So 18.05.08 19:10
@BenBE: solltest du auch auf DWords umstellen würd ich das aber nicht machen - ich würde die vollen 32-Bit ausnutzen und stattdessen die conditional move/conditional set ASM-Befehle verwenden um das Overflow Flag auszuwerten und den Übertrag zu addieren. Dadurch erspart man sich einen conditional jump und somit potenzielle branch misspredictions.
64-Bit Datentypen brauchst du dann nur beim Multiplizieren.
Schade nur, dass Delphi keine Intrinsics unterstützt...
Wegen der Optimierung beim Potenzieren kriegst du noch ne PN.
Gruß, Motzi
_________________ gringo pussy cats - eef i see you i will pull your tail out by eets roots!
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: So 18.05.08 21:19
Hallo,
warum nicht dann gleich www.ellipsa.net/public/nx/nx.html nutzen das wahlweise massiv Assemblerroutinen (nx_kernel.pas) nutzt .
Wozu alles neu erinden. Man müsste nur einen Vergleich zu GMP,BigNum2 oder Hagen Redmann DEC_5_1c haben.
Gruß Horst
|
|
ub60
Beiträge: 762
Erhaltene Danke: 127
|
Verfasst: So 18.05.08 21:41
NX funzt nicht mit älteren Delphi-Versionen.
Mein D7 (und das liebe ich ) schmettert DX leider ab.
ub60
|
|
g1o2k4
Beiträge: 493
|
Verfasst: Mo 02.06.08 15:22
@BenBe: sag mal...haste das eigentlich auch zufälligerweise als c-quelltext ?
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Mo 02.06.08 15:35
Nö, aber in C als Semester-Beleg mit nem Kumpel schon mal implementiert ... Am Ende 20 Seiten nur Doku der Funktionsköpfe und insgesamt ~10kLOC an Source (Doku zählt da auch mit rein, weil die geTeXt war ). Die Lib hatte aber noch ein paar Probleme bei manchen Rechenoperationen, Hatte aber nen vollwertigen RPN-Parser drin
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Allesquarks
Beiträge: 510
Win XP Prof
Delphi 7 E
|
Verfasst: Di 03.06.08 16:04
Wie Motzi schon sagte braucht man sich gar nicht auf 31 Bit beschränken, da die Überläufe im asm ja eh in flags kommen. Allerdings macht es bei Bigints wohl keinen Sinn alle dword signed zu halten, weshalb er wohl eher das carry flag meinte. Da braucht man dann gar keine conditional moves, sondern einfach adc (add with carry), wenn man darauf achtet, das Flag in der Schleife nicht zu verändern.
Ich habe das auf diesem Wege in assembler schon programmiert und hier ins Forum gestellt. Je nach deiner Formatierung (little oder Big-Endian) könnte meine Version sogar "binärkompatibel" sein, dann könntest du das einfach rüberkopieren. Insbesondere habe ich auch eine Funktion implementiert, die das dezimal ein- und ausgeben kann, welche (nach kurzem Überfliegen) glaube ich bei dir fehlt.
Ansonsten kann ich nur sagen Respekt: Ich bin bis heute noch nicht dazu gekommen mit den Grundrechenarten über Taylorreihen die komplexeren Funktionen zu implementieren. Mich würde aber brennend interessieren, was deine Wurzelfunktionen überhaupt zurückgeben (wenn ich das richtig gesehen habe sind das doch auch ganze Zahlen).
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Di 03.06.08 16:16
Allesquarks hat folgendes geschrieben: | Wie Motzi schon sagte braucht man sich gar nicht auf 31 Bit beschränken, da die Überläufe im asm ja eh in flags kommen. Allerdings macht es bei Bigints wohl keinen Sinn alle dword signed zu halten, weshalb er wohl eher das carry flag meinte. Da braucht man dann gar keine conditional moves, sondern einfach adc (add with carry), wenn man darauf achtet, das Flag in der Schleife nicht zu verändern.
Ich habe das auf diesem Wege in assembler schon programmiert und hier ins Forum gestellt. Je nach deiner Formatierung (little oder Big-Endian) könnte meine Version sogar "binärkompatibel" sein, dann könntest du das einfach rüberkopieren. Insbesondere habe ich auch eine Funktion implementiert, die das dezimal ein- und ausgeben kann, welche (nach kurzem Überfliegen) glaube ich bei dir fehlt. |
Zum Zahlenformat: Die Zahlen liegen Little Endian im Speicher, d.h. Index 0 liefert das Least Significant Digit (Ich kürz mal absichtlich nicht ab ).
Zum Konvertieren nach Dezimal. Das hat die BigNum_Lib mit drin, jedoch ist es dort, da es mit DivMod implementiert ist, sehr lahm. Wenn Du da was schnelleres hast, würd ich mich freuen.
Allesquarks hat folgendes geschrieben: | Ansonsten kann ich nur sagen Respekt: Ich bin bis heute noch nicht dazu gekommen mit den Grundrechenarten über Taylorreihen die komplexeren Funktionen zu implementieren. Mich würde aber brennend interessieren, was deine Wurzelfunktionen überhaupt zurückgeben (wenn ich das richtig gesehen habe sind das doch auch ganze Zahlen). |
Jup. Das ist der ganzzahlige Anteil, der ABGERUNDETEN eigentlichen Wurzel. D.h. Wurzel von 2 gibt er 1 zurück, bei Wurzel 3 gibt er auch 1 und bei Wurzel 4 gibt er 2 zurück. Ist über Tangenten-Verfahren\Regula Falsi implementiert.
Die Implementierung der trigonometrischen Funktionen wie Sin und Cos ist mit den Taylor-Reihen ein Krampf (ach wenn es geht). Man sollte damit aber nicht ernsthaft arbeiten; grad wenn man sehr große Winkel brauch, da man allein durch die BErechnung von Pi (was man für die Quadranten-Beziehungen benötigt) sagenhafte Ungenauigkeiten reinbekommt.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Allesquarks
Beiträge: 510
Win XP Prof
Delphi 7 E
|
Verfasst: Di 03.06.08 16:33
Hm bin halt kein Informatiker. Das zeigt sich auch daran, dass ich eine bigint-Multiplikation geschrieben habe und irgendwann ich glaube von Horst H aufgeschnappt habe, dass es eben auch n*log n Laufzeiten gibt.
Ich weiß jetzt nicht genau, wie das beim Sinus etc. ist, welche Algorithmen da besser sind als die Taylorreihen (für Anregungen wäre ich dankbar), allerdings fand ich es bei den Taylors immer gut mit dem Restglied, da ich immer nach einer definerten Genauigkeit aufhören wollte.
Planst du noch eine Implementierung von Fließkommazahlen? Falls ja würde es mich interessieren, wie du das angehen würdest, dass man ja bei irrationalen Zahlen irgendwann abbrechen muss.
Wegen meiner to dezimal Routine:
TBigint=binäre große Zahl
TCustomganzzahl=array of byte (Ziffernfolge mit Basis zwischen 0 und 255)
Meine biginttostring (TBigint to string) baut sich sukzessive die Zweierpotenzen im Zehnersystem (TCustomganzzahl) und addiert diese anhand der durch die binäre Zahl vorgegebenen Bitmaske. Ich benutze also die spezielle Funktion mul2 sowie Addition von Bignums (bei mir TCustomganzzahl) im Nichtbinärsystem.
Das ganze sind bei mir Klassen weshalb für jede Zahl dieser "Rainbowtable" ein Construktor aufgerufen wird. Ist aber nur zur besseren Übersichtlichkeit. Würde genausogut prozedural funktionieren.
|
|
Motzi
Beiträge: 2931
XP Prof, Vista Business
D6, D2k5-D2k7 je Prof
|
Verfasst: Di 03.06.08 19:02
Allesquarks hat folgendes geschrieben: | Wie Motzi schon sagte braucht man sich gar nicht auf 31 Bit beschränken, da die Überläufe im asm ja eh in flags kommen. Allerdings macht es bei Bigints wohl keinen Sinn alle dword signed zu halten, weshalb er wohl eher das carry flag meinte. Da braucht man dann gar keine conditional moves, sondern einfach adc (add with carry), wenn man darauf achtet, das Flag in der Schleife nicht zu verändern. |
Stimmt, ich meinte eigentlich das carry flag.. ADC hab ich komplett vergessen, damit geht es natürlich noch einfacher und effizienter.. wo gibts denn deinen Code? Würd gern mal einen Blick darauf werfen...
_________________ gringo pussy cats - eef i see you i will pull your tail out by eets roots!
|
|
Allesquarks
Beiträge: 510
Win XP Prof
Delphi 7 E
|
Verfasst: Di 03.06.08 19:49
Ich hab mal probiert das prozedural auszukoppeln und in Open-Source Units gepostet unter Bigints (soviel steht da von mir auch nicht drin sollte schnell zu finden sein). Besser ist es aber eine neuere Version aus dem Source von meinem Taschenrechner RAFX zu entnehmen. Die entsprechenden Units sind rmath, TBigintzahlimpl, TBigfloatzahlimpl, TCustomganzzahlimpl und TCustomfloatzahlimpl. Sollte nicht so schwer zu finden sein da drin, da das meiste bisher nur aus den Bodys besteht. Der Quelltext insbesondere das asm sollten also auffallen.
|
|
|