Zahlen gehört haben, habe ich die vorgestellte Methode von Karatsuba
nach PureBasic übersetzt und mit der normalen Schulmethode verglichen.
Hier also der leider gering kommentierte Code: (getestet mit PB V4.01 Linux)
Code: Alles auswählen
EnableExplicit
Structure bignum
*v
n.l
EndStructure
Procedure Convert2bignum_10(a.s, *bn.bignum = 0) ;funktioniert nur mit base = 10
Protected *c.character, *cx.long, *alloc = *bn
If *bn = 0
*bn = AllocateMemory(SizeOf(bignum))
If *bn = 0 : ProcedureReturn #False : EndIf
EndIf
a = Trim(a)
*bn\n = Len(a)
*bn\v = AllocateMemory(*bn\n * SizeOf(long))
If *bn\v = 0
If Not *alloc : FreeMemory(*bn) : EndIf
ProcedureReturn #False
EndIf
*c = @a
*cx = *bn\v + (*bn\n - 1) * SizeOf(long)
While *c\c
*cx\l = *c\c - '0'
*c + SizeOf(character)
*cx - SizeOf(long)
Wend
ProcedureReturn *bn
EndProcedure
Procedure.s Convert2Str_10(*bn.bignum) ;funktioniert nur mit base = 10
Protected a.s = Space(*bn\n), *cx.long, *c.character, t.l = #False, n.l = *bn\n
*c = @a
*cx = *bn\v + (*bn\n - 1) * SizeOf(long)
While n
*c\c = *cx\l + '0'
If t Or *cx\l Or n = 1
*c + SizeOf(character)
t = #True
EndIf
n - 1
*cx - SizeOf(long)
Wend
*c\c = 0
ProcedureReturn a
EndProcedure
Global base.l = 10
Procedure CreateBignum(n.l, *bn.bignum = 0) ;Erstellt eine Bignum oder ändert ihre Größe
Protected *bnt = *bn
If Not *bn
*bn = AllocateMemory(SizeOf(bignum))
If *bn = 0 : ProcedureReturn #False : EndIf
EndIf
If Not *bn\v
*bn\n = n
*bn\v = AllocateMemory(n * SizeOf(long))
If *bn\v = 0
If Not *bnt : FreeMemory(*bn) : EndIf
ProcedureReturn #False
EndIf
Else
*bn\n = n
*bnt = ReAllocateMemory(*bn\v, n * SizeOf(long))
If Not *bnt : ProcedureReturn #False : EndIf
*bn\v = *bnt
EndIf
ProcedureReturn *bn
EndProcedure
;Beispiel:
; - Sum(111, 33, 2) = 111 + 3300 = 1411
Procedure Sum(*a.bignum, *b.bignum, shift.l = 0) ;Summiert *a und *b und speichert das Ergebnis in *a, na muss >= nb + shift sein, sonst falsches Ergebnis
Protected *ca.long, *cb.long, carry.l, na.l, nb.l
*ca = *a\v + shift * SizeOf(long)
*cb = *b\v
carry = 0
na = *a\n - shift
nb = *b\n
While na
*ca\l + carry
If nb > 0 : *ca\l + *cb\l : EndIf
carry = *ca\l / base
*ca\l % base
*ca + SizeOf(long) : *cb + SizeOf(long)
na - 1
nb - 1
Wend
If carry
*a\n + 1
*a\v = ReAllocateMemory(*a\v, *a\n * SizeOf(long))
If Not *a\v : Debug "Out of memory" : End : EndIf
PokeL(*a\v + (*a\n - 1) * SizeOf(long), carry)
EndIf
ProcedureReturn carry
EndProcedure
Procedure Diff(*a.bignum, *b.bignum) ;Subtrahiert *b von *a und speichert das Ergebnis in *a, *a muss >= *b sein
Protected *ca.long, *cb.long, carry.l, na.l, nb.l, t.l
*ca = *a\v
*cb = *b\v
carry = 0
na = *a\n
nb = *b\n
While na
If nb > 0 : carry + *cb\l : EndIf
If *ca\l - carry => 0
*ca\l - carry
carry = 0
Else
*ca\l - carry + base
carry = 1
EndIf
na - 1 : nb - 1
*ca + SizeOf(long) : *cb + SizeOf(long)
Wend
EndProcedure
Procedure MulSchool(*a.bignum, *b.bignum, *s.bignum = 0) ;multipliziert *a mit *b nach der Schulmethode und speichert Ergebnis in *s
Protected *ca.long, s.bignum, n.l = *a\n + *b\n, *cb.long, t.bignum, na.l, nb.l, *ct.long, carry.l, *st = *s
If *s = 0 : *s = CreateBignum(n)
ElseIf *s\n < n : *s = CreateBignum(n, *s) : EndIf
If *s = 0 : ProcedureReturn #False : EndIf
t\v = AllocateMemory(n * SizeOf(long))
If t\v = 0
If Not *st : FreeMemory(*s) : EndIf
FreeMemory(*s\v)
ProcedureReturn #False
EndIf
t\n = n
*cb = *b\v
nb = 0
While nb < *b\n
*ca = *a\v : na = *a\n
*ct = t\v + nb * SizeOf(long)
carry = 0
While na
*ct\l = *ca\l * *cb\l + carry
carry = *ct\l / base
*ct\l % base
*ct + SizeOf(long)
*ca + SizeOf(long)
na - 1
Wend
*ct\l = carry
Sum(*s, t)
PokeL(t\v + nb * SizeOf(long), 0)
nb + 1
*cb + SizeOf(long)
Wend
FreeMemory(t\v)
ProcedureReturn *s
EndProcedure
; Beispiele:
; - a = 123456
; Copy(a, b, 3) ==> b = 123
; - a = 123456
; Copy(a, b, -3) ==> b = 456
Procedure Copy(*s.bignum, *d.bignum, shift.l = 0) ;kopiert *s in *d (*d muss allokiert sein)
Protected *cd.long, nd.l, *cs.long, ns.l
If *s\n <= shift Or *s\n + shift <= 0
If Not *d\v
*d\v = AllocateMemory(SizeOf(long))
If Not *d\v : ProcedureReturn #False : EndIf
*d\n = 1
EndIf
nd = *d\n
*cd = *d\v
While nd
*cd\l = 0
*cd + SizeOf(long) : nd - 1
Wend
ElseIf shift < 0
shift = -shift
If *s\n < shift : shift = *s\n : EndIf
If Not *d\v
*d\v = AllocateMemory(shift * SizeOf(long))
If Not *d\v : ProcedureReturn #False : EndIf
*d\n = shift
EndIf
*cd = *d\v
*cs = *s\v
While shift
*cd\l = *cs\l
*cd + SizeOf(long) : *cs + SizeOf(long)
shift - 1
Wend
Else
If Not *d\v
*d\n = *s\n - shift
*d\v = AllocateMemory(*d\n * SizeOf(long))
If Not *d\v : ProcedureReturn #False : EndIf
EndIf
*cs = *s\v + shift * SizeOf(long)
*cd = *d\v
nd = *d\n : ns = *s\n - shift
While nd
If ns > 0
*cd\l = *cs\l
Else
*cd\l = 0
EndIf
*cd + SizeOf(long) : *cs + SizeOf(long)
nd - 1 : ns - 1
Wend
EndIf
ProcedureReturn #True
EndProcedure
Procedure Mul(*a.bignum, *b.bignum, *s.bignum = 0) ;Multipliert *a und *b nach Karatsuba und speichert Ergebnis in *s oder gibt *s zurück
Protected ah.bignum, bh.bignum, al.bignum, bl.bignum, p1.bignum, p3.bignum, n.l, n2.l
n = *a\n : If *b\n > n : n = *b\n : EndIf ;n = Max(*b\n, *a\n)
If n <= 3 ;Bei weniger als 4 Stellen nutze die Schulmethode
If *s = 0 : *s = CreateBignum(2 * n)
ElseIf *s\n < 2 * n : CreateBignum(2 * n, *s) : EndIf
MulSchool(*a, *b, *s)
ProcedureReturn *s
EndIf
n2 = n / 2
If n & 1 : n2 + 1 : EndIf ;Wenn n ungerade war, dann addiere zu n2 eins
CreateBignum(n, p1) ;Reserviert Speicher für Zwischenergebnisse
CreateBignum(n, p3)
If *s = 0 : *s = CreateBignum(2 * n) ;Reserviert Speicher für Zwischen- und Endergebnis
ElseIf *s\n < 2 * n : CreateBignum(2 * n, *s) : EndIf
Copy(*a, ah, n2) ;Nimmt obere und untere Hälfte von *a und *b und speichert sie in ah, al, bh, bl
Copy(*a, al, -n2)
Copy(*b, bh, n2)
Copy(*b, bl, -n2)
Mul(ah, bh, p1) ;p1 = ah * bh
Mul(al, bl, *s) ;*s = al * bl
Sum(al, ah) ;al = al + ah
Sum(bl, bh) ;bl = bl + bh
Mul(al, bl, p3) ;p3 = al * bl
Diff(p3, p1) ;p3 = p3 - p1
Diff(p3, *s) ;p3 = p3 - *s
Sum(*s, p3, n2) ;*s = *s + p3 * base^n2
Sum(*s, p1, 2 * n2) ;*s = *s + p1 * base^(2 * n2)
ProcedureReturn *s
EndProcedure
Define.bignum a, b, r1, r2
Define s1.s, s2.s, n.l, time1.l, max.l, time2.l, s.s
max = 10000 ;10000: Mul()->1920, MulSchool()->7016
s = "" : For n = 1 To max : s + Str(Random(9)) : Next : Convert2bignum_10(s, a)
s = "" : For n = 1 To max : s + Str(Random(9)) : Next : Convert2bignum_10(s, b)
;Convert2bignum_10("84232332233", a)
;Convert2bignum_10("1532664392", b)
time1 = ElapsedMilliseconds() ;Multipliziert nach Karatsuba
Mul(a, b, r1)
time1 = ElapsedMilliseconds() - time1
time2 = ElapsedMilliseconds() ;Multipliziert nach Schulmethode
MulSchool(a, b, r2)
time2 = ElapsedMilliseconds() - time2
s1 = Convert2Str_10(r1)
s2 = Convert2Str_10(r2)
If OpenWindow(0, 0, 0, 400, 80, "Ergebnis", #PB_Window_ScreenCentered)
If CreateGadgetList(WindowID(0))
TextGadget(0, 0, 0, 400, 20, "Zeit (Karatsuba): " + Str(time1) + " ms")
StringGadget(1, 0, 20, 400, 20, s1)
TextGadget(2, 0, 40, 400, 20, "Zeit (Schulmethode): " + Str(time2) + " ms")
StringGadget(3, 0, 60, 400, 20, s2)
Repeat : Until WaitWindowEvent() = #PB_Event_CloseWindow
EndIf
CloseWindow(0)
EndIf