PureBoard

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