Autor |
Beitrag |
wirbeldelphi
Beiträge: 29
|
Verfasst: Di 22.07.08 19:12
Ich hoffe ich darf das als Newbee und als ersten Beitrag hier im Forum..
Feine Sache deine Unit (gratuliere!), aber es sind zwei recht offensichtliche Fehler drin.
Auf der Suche warum ein falsches Ergebnis bei
(12321^3) mod 873 => 297 ooops..
herauskommt ist dann die Ursache schnell klar:
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
| Procedure TSJBigNumber.Power(Exp: TBigNumber); Begin Self.fNumber := BM_Power(Self.fNumber, Exp); End;
Procedure TSJBigNumber.Power(Exp: TSJBigNumber); Begin Self.fNumber := BM_Power(Self.fNumber, Exp.Number); End; |
Du hast dort BM_Multiply anstelle von BM_Power verwendet. Nach der Änderung kommt auch das erwartete Ergebnis:
(12321^3) mod 873 = 397
Moderiert von Narses: Code- durch Delphi-Tags ersetzt
|
|
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: Mi 23.07.08 12:22
_________________ 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.
|
|
wirbeldelphi
Beiträge: 29
|
Verfasst: Mi 23.07.08 15:05
Ich wollte noch schaun, ob der karatsuba Algorithmus zum Multiplizieren fixer ist, aber die Geschwindigkeit ist eigentlich eh kaum messbar, BM_Multiply ist sehr fix.
Vielleicht magst du das noch einfügen als zweite Multiplikation.
Siehe auch de.wikipedia.org/wik...aratsuba-Algorithmus
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: 39: 40: 41: 42: 43:
| Function BM_MultiplyKaratsuba(Num1, Num2: TBigNumber): TBigNumber; Var i, n2, n:Integer; Num1_high, Num1_low, Num2_high, Num2_low:TBigNumber; P1, P2, P3:TBigNumber; Begin if Length(Num1) > Length(Num2) then n2 := Length(Num1) else n2 := Length(Num2); if odd(n2) then inc(n2); if n2 < 9 then begin Result := BM_Multiply(Num1, Num2); exit; end; n := n2 div 2;
SetLength(Num1_low,n); SetLength(Num2_low,n); for i:=0 to n -1 do begin if i < Length(Num1) then Num1_low[i]:=Num1[i] else Num1_low[i] := 0; if i < Length(Num2) then Num2_low[i]:=Num2[i] else Num2_low[i] := 0; end; SetLength(Num1_high,n); SetLength(Num2_high,n); for i:=n to n2 - 1 do begin if i < Length(Num1) then Num1_high[i - n]:=Num1[i] else Num1_high[i - n] := 0; if i < Length(Num2) then Num2_high[i - n]:=Num2[i] else Num2_high[i - n] := 0; end; P1 := BM_MultiplyKaratsuba(Num1_high, Num2_high); P2 := BM_MultiplyKaratsuba(Num1_low, Num2_low); P3 := BM_MultiplyKaratsuba(BM_Add(Num1_high,Num1_low), BM_Add(Num2_high,Num2_low)); SetLength(Result, n2 * 2); FillChar(Result[0],n2 * 2,0); for i:=0 to Length(P1)-1 do Result[i+n2] := P1[i]; Result := BM_Add(Result, P2); P3 := BM_Sub(P3,P1); P3 := BM_Sub(P3,P2); Setlength(P1, n2 * 2); FillChar(P1[0],n2 * 2,0); for i:=0 to Length(P3)-1 do P1[i + n] := P3[i]; Result := BM_Add(Result, P1); BM_Optimize(Result); End; |
Moderiert von Narses: Code- durch Delphi-Tags ersetzt
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Mi 23.07.08 20:17
Ich hab auch noch 2 kleine Sachen:
BMD_BigNumToStr gibt einen Leerstring zurück, wenn die Zahl 0 darstellt. Sollte man evtl. Abfangen
Der Kommentar bei BM_CompareZ stimmt IMHO nicht: sollte eher sein. Zudem wüsste ich ganz gern mal für was Z nur NC eigentlich steht
_________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
|
|
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: Fr 25.07.08 04:33
Martok hat folgendes geschrieben: | Ich hab auch noch 2 kleine Sachen:
BMD_BigNumToStr gibt einen Leerstring zurück, wenn die Zahl 0 darstellt. Sollte man evtl. Abfangen |
Jep, kümmer ich mich drum
Martok hat folgendes geschrieben: | Der Kommentar bei BM_CompareZ stimmt IMHO nicht: sollte eher sein. Zudem wüsste ich ganz gern mal für was Z nur NC eigentlich steht |
Das ist doch aber ganz einfach erklärt:
Z = Zero, NC = Not Carry. Sollte doch aber für jemanden, der schon mal ASM gesehen hat, nahezu offensichtlich sein, grad wenn's weitere Methoden C, NZ auch noch gibt, die zudem noch von Funktionen mit GT, LT, LE, GE, E und NE aufgerufen werden Also Martok, das sieht man doch
_________________ 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.
|
|
n-regen
Beiträge: 202
Erhaltene Danke: 2
|
Verfasst: Fr 01.08.08 12:10
Die folgende Funktion können - bis die Zuweisung in der Komponente implemetiert wird - wahrscheinlich einige brauchen:
Delphi-Quelltext 1: 2: 3: 4:
| function IntToBigNum(Int: Integer):TBigNumber; begin result := BMD_StrToBigNum(inttostr(Int), false); end; |
|
|
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: Fr 01.08.08 13:06
Dafür gibt's ne schnellere Variante; implementier ich aber sobald ich das eh alles hier im Thread einarbeite ...
_________________ 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.
|
|
wirbeldelphi
Beiträge: 29
|
Verfasst: Fr 01.08.08 20:58
Ich bastele grad an einer Unit namens BigNumSigned, die BugNum2 nutzt, aber damit vorzeichenbehaftet rechnet. Also nicht nur positive Zahlen, sondern auch negative.
Bist du interessiert so etwas einzuarbeiten? Bis jetzt habe ich
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:
| Function BM_Add(Num1, Num2: TSignedBigNumber): TSignedBigNumber; Function BM_Sub(Num1, Num2: TSignedBigNumber): TSignedBigNumber; Function BM_Divide(Num1, Num2: TSignedBigNumber): TSignedBigNumber; Function BM_Multiply(Num1, Num2: TSignedBigNumber): TSignedBigNumber; Function BM_Power(Base, Exp: TSignedBigNumber): TSignedBigNumber;
Function BM_Abs(Num: TSignedBigNumber): TSignedBigNumber; Function BM_Div(Num1, Num2: TSignedBigNumber): TSignedBigNumber; Function BM_Mod(Num1, Num2: TSignedBigNumber): TSignedBigNumber; Function BM_Even(Num: TSignedBigNumber):boolean; Function BM_Odd(Num: TSignedBigNumber):boolean;
Function BM_CompareC(Num1, Num2: TSignedBigNumber): Boolean; Function BM_CompareNC(Num1, Num2: TSignedBigNumber): Boolean; Function BM_CompareNZ(Num1, Num2: TSignedBigNumber): Boolean; Function BM_CompareZ(Num1, Num2: TSignedBigNumber): Boolean; Function BM_CompareE(Num1, Num2: TSignedBigNumber): Boolean; Function BM_CompareNE(Num1, Num2: TSignedBigNumber): Boolean; Function BM_CompareL(Num1, Num2: TSignedBigNumber): Boolean; Function BM_CompareLE(Num1, Num2: TSignedBigNumber): Boolean; Function BM_CompareG(Num1, Num2: TSignedBigNumber): Boolean; Function BM_CompareGE(Num1, Num2: TSignedBigNumber): Boolean; Procedure BM_Assign(Var Result: TSignedBigNumber; Const Number: int64); Overload; Procedure BM_Assign(Var Result: TSignedBigNumber; Const Number: TBigNumber); Overload; Procedure BM_Assign(Var Result: TSignedBigNumber; Const Number: TSignedBigNumber); Overload;
Function BMD_StrToSignedBigNum(Str: String; HexInput: Boolean): TSignedBigNumber; Function BMD_SignedBigNumToStr(Num: TSignedBigNumber; HexOutput: Boolean): String;
Function GCD_ext(a, b: TSignedBigNumber; var u,v: TSignedBigNumber): TSignedBigNumber; Function phi(p,q:TBigNumber):TBigNumber; Function NextPrime(Num, Samples:TSignedBigNumber):TSignedBigNumber; Function MillerRabin(Num, NumSamples: TSignedBigNumber):boolean; Function BM_Random(minimum, maximum:TBigNumber):TBigNumber; |
_________________ Ich bin keine Signatur - ich putz hier nur.
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Sa 02.08.08 03:22
BenBE hat folgendes geschrieben: |
Martok hat folgendes geschrieben: | Der Kommentar bei BM_CompareZ stimmt IMHO nicht: sollte eher sein. Zudem wüsste ich ganz gern mal für was Z nur NC eigentlich steht |
Das ist doch aber ganz einfach erklärt:
Z = Zero, NC = Not Carry. Sollte doch aber für jemanden, der schon mal ASM gesehen hat, nahezu offensichtlich sein, grad wenn's weitere Methoden C, NZ auch noch gibt, die zudem noch von Funktionen mit GT, LT, LE, GE, E und NE aufgerufen werden Also Martok, das sieht man doch |
Was mich zu der Frage bringt: warum ist die Version die ich kommentiert hab eine andere als die im Source-Verzeichnis liegt?
Oh, falscher Suchpfad. Verdammt, ich compiliere die ganze Zeit gegen ne falsche Lib
Ein Compare das wie von der Standard-Quicksort-Funktion verlangt -1/0/1/ zurück gibt wäre übrigens mal noch praktisch.
_________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
|
|
Flamefire
Beiträge: 1207
Erhaltene Danke: 31
Win 10
Delphi 2009 Pro, C++ (Visual Studio)
|
Verfasst: So 06.12.09 22:28
So.
Mal von mir ein Update der BigNum2 Unit.
Changes:
-Unterstützung negativer Zahlen
-Implementierung Compare funktion nach Standart (-1;0;1)
-Umwandlung in/von Integer,Int64,Cardinal
Zuletzt bearbeitet von Flamefire am Mo 07.12.09 00:13, insgesamt 1-mal bearbeitet
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Mo 07.12.09 00:06
Da sind aber noch einige Bugs drin, hier ein paar zur Ansicht: BM_modulo(12345,5)=5 und noch schlimmer für TSJBigNumber: modulo(-12345,-5)=-5 und viel schlimmer modulo(-5,-12345)=-12350.
Weiter: a.assign(-12345); a.assign('7'); ergibt -7!
Gruß Gammatester
|
|
Flamefire
Beiträge: 1207
Erhaltene Danke: 31
Win 10
Delphi 2009 Pro, C++ (Visual Studio)
|
Verfasst: Mo 07.12.09 00:14
Ok, schonmal vielen Dank
den Assign-Bug habe ich behoben. War mir nicht aufgefallen, da ich den String nie mehr verwendet hab.
Den Modulo macht BenBE demnächst.
Zuletzt bearbeitet von Flamefire am Mo 07.12.09 16:22, insgesamt 1-mal bearbeitet
|
|
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 07.12.09 00:19
Flamefire hat folgendes geschrieben : | Den Modulo macht BenBE demnächst. |
Ich nehm gerne Patches entgegen, schau's mir aber mal die Tage mit an, ob ich's direkt finde, was er da hat ...
Danke aber schonmal für die Testcases.
Edit: Testcase 1 grad durchdebuggt (ohne den Wrapper):
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9:
| procedure TForm1.Button1Click(Sender: TObject); var B1, B2, BR: TBigNumber; begin B1 := BMD_StrToBigNum('12345', false); B2 := BMD_StrToBigNum('5', false); BR := BM_Modulo(B1, B2); Caption := BMD_BigNumToStr(BR, false); end; |
Liefert das korrekte Ergebnis 0.
Die Vorzeichenbehafteten können nicht an mir liegen, die hat Flamefire gebaut ...
Edit 2: @Flamefire: Bei Modulo muss die Berechnung an BM_Modulo ohne Beachtung der Vorzeichen gereicht werden. Das Ergebnisvorzeichen richtet sich dann nach dem XOR der Eingabe-Vorzeichen, unabhängig von dem, was BM_Modulo liefert (außer halt fSign=0).
_________________ 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 Mo 07.12.09 00:48, insgesamt 2-mal bearbeitet
|
|
Gammatester
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: Mo 07.12.09 00:36
Das mit BM_modulo(12345,5)=5 stimmt nicht (sorry, falsche Variable ausgegeben), BM_modulo arbeitet hier richtig. Die TSJBigNumber.modulo-Fehler bleiben.
Gruß Gammatester
|
|
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 07.12.09 00:56
Jap, wie gesagt das betrifft die letzte Kondition dort in der Funktion, die muss raus. Und ferner muss die Vorzeichenbehandlung noch korrigiert werden.
Zwecks Vorzeichen ist mir in erinnerung:
+ mod + --> +
- mod + --> +
+ mod - --> -
- mod - mod -
(Also Vorzeichen des Divisors).
Vgl. de.wikipedia.org/wiki/Modulo#Beispiel_2 bzw. Implementierung in Computersystemen. Besonders auf die Konvention in der Mathe achten.
_________________ 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.
|
|
Flamefire
Beiträge: 1207
Erhaltene Danke: 31
Win 10
Delphi 2009 Pro, C++ (Visual Studio)
|
Verfasst: Mo 07.12.09 16:21
jo sry. mein ansatz war, die berechnung im restklassen ring...Also alle Module>=0
hab da aber in der eile, fertig zu werden, da was übersehn
Na gut dann halte ich mich an die Konventionen und es kommt dann das Vorzeichen des Divisors raus.
Update im Anhang:
Einloggen, um Attachments anzusehen!
|
|
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 07.12.09 16:44
Ich warte hier noch kurz die Rückmeldung bzgl. Funktionalität ab und würde die aktualisierte Version dann oben im ersten Beitrag (nach etwas Code-Formatter-Kosmetik) veröffentlichen.
_________________ 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.
|
|
Flamefire
Beiträge: 1207
Erhaltene Danke: 31
Win 10
Delphi 2009 Pro, C++ (Visual Studio)
|
Verfasst: Mo 07.12.09 16:51
Die Grundrechenarten (+,-,*,/) sind im Extrem getestet (weißt ja wo )
Ich gehe also davon aus, dass die funktionieren.
Umwandlungen hab ich nochmal überprüft, kann ich zu 99% sagen, dass es ok ist.
Mod, Log, Wurzel habe ich nicht geprüft, da es schon fast zu trivial ist. Es werden lediglich die Vorzeichenkonventionen eingehalten (x^-y=0 per Definition, da es Integer sind außer bei x=1 oder x=0)
Beim Mod hatte ich mich vertan, ok...
Auch GGT und KGV sind ungetestet. Hab mich da aber strikt an Wikipedia gehalten.
Und wegen Formatierung: Bei dir sind 2 Tabs drin. Bei mir nur einer. Und sonst...Da hat glaube jeder seine vorlieben, wo er begin und else usw. platziert. Ich finde es so übersichtlicher, da der Code damit nicht so lang wird.
|
|
spawn89
Beiträge: 82
Erhaltene Danke: 6
Linux
CodeTyphon
|
Verfasst: Mo 07.12.09 17:09
Ein Unit-test wäre aber auch einfach zu schön für das Teil, nicht?
Edit:
Wenn ich zuhause bin könnt ich ja mal meinen drüberlaufen lassen. ^^
|
|
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 07.12.09 17:13
Flamefire hat folgendes geschrieben : | Die Grundrechenarten (+,-,*,/) sind im Extrem getestet (weißt ja wo ) |
Jap.
Flamefire hat folgendes geschrieben : | Ich gehe also davon aus, dass die funktionieren. |
Wie das halt immer so ist ... mit Theorie und Praxis.
Flamefire hat folgendes geschrieben : | Umwandlungen hab ich nochmal überprüft, kann ich zu 99% sagen, dass es ok ist. |
Ich schau dann eh noch mal drüber.
Flamefire hat folgendes geschrieben : | Mod, Log, Wurzel habe ich nicht geprüft, da es schon fast zu trivial ist. Es werden lediglich die Vorzeichenkonventionen eingehalten (x^-y=0 per Definition, da es Integer sind außer bei x=1 oder x=0)
Beim Mod hatte ich mich vertan, ok... |
Ich hoffe, für 0^-1 gibt's ne Exception
Flamefire hat folgendes geschrieben : | Auch GGT und KGV sind ungetestet. Hab mich da aber strikt an Wikipedia gehalten. |
Da sollte man sich auf jeden Fall noch mal die Vorzeichenproblematik angucken. Wobei ich ggT immer positiv, kgV positiv, außer beide negativ vorschlagen würde (sollte man ggf. noch mal Abgleichen mit Wiki oder richtiger Quelle).
Flamefire hat folgendes geschrieben : | Und wegen Formatierung: Bei dir sind 2 Tabs drin. Bei mir nur einer. Und sonst...Da hat glaube jeder seine vorlieben, wo er begin und else usw. platziert. Ich finde es so übersichtlicher, da der Code damit nicht so lang wird. |
Hab nen Source-Formatter, der hat meinen Code-Stil gleich als Konfig drin. Da geht das ganz zügig mit formatieren.
Und gegen zu langen Code gibt's Code Folding
@ spawn89: Reiche mir nen kleines Demo-Projekt als Unit-Test ein, dann füg ich den bei. Ansonsten müsst ich mal meinen Großzahlen-Taschenrechner mit RPN-Parser raussuchen; der war Ausgangspunkt für die Unit.
_________________ 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.
|
|
|