Unten findestes Du die longint Implementation aus meinem
MPArith. Selbstverständlich ist auch
eine MP-Version dabei, allerdings nicht für Bignum, dafür allerdings mit Binäralgorithmus nach Shallit/Sorenson.
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: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61:
| function jacobi32(a,b: longint): longint; var j,m8: integer; t: longint; begin
jacobi32 := 0; if (b<3) or (b and 1 = 0) then begin {$ifdef MPC_HaltOnError} {$ifdef MPC_UseExceptions} raise MPXRange.Create('jacobi32: b<3 or even'); {$else} RunError(MP_RTE_RANGE); {$endif} {$else} set_mp_error(MP_RANGE); exit; {$endif} end;
j := 1;
if a<0 then begin if b and 3 = 3 then j := -j; a := -a; end;
if a>=b then a := a mod b;
while a<>0 do begin while a and 3 = 0 do a := a shr 2; if a and 1 = 0 then begin a := a shr 1; m8 := b and 7; if (m8=3) or (m8=5) then j:=-j; end; if a=1 then begin jacobi32 := j; exit; end; if (a and b and 3) = 3 then j := -j; t := b; b := a; a := t mod a; end; if b=1 then jacobi32 := j; end; |