Exponentieren und dann Modulo: große Zahlen

[himitsu]

Komisch, jetzt getestet kommt auch 11771, aber letztens war es irgendwas Anderes :gruebel:

Was die größeren Zahlen angeht, dann mißt du wohl entweder Extendet verwenden, allerdings kann man da nur die ersten 18-19 Stellen betrachten, da die Auflösung nicht anderes zuläßt.

Bei 'ner 30-stelligen Zahl wären also durchschnittlich die letzten 11 Stellen fehlerhaft.



Ansonsten hätte ich fast meine eigene BigInt-Imlementation fertig (BigFloat und 'nen dynamisches BigFloat kommen auch irgendwann) ... rechnen geht schon, aber den einen Sonderfall von Low(TBigInt) / MinBigInt muß ich noch prüfen und mit der Überlaufpüfung hab ich noch Probleme ;(


mit 'nem 512 bit-Integer wäre ein Bereich von -2^511 bis 2^511 - 1 stellengenau abgedeckt.
von*-6.703.903.964.971.298.549.787.012.499.102.923.063. 739.682.910.296.196.688.861.780.721.860.882.015.03 6.773.488.400.937.149.083.451.713.845.015.929.093. 243.025.426.876.941.405.973.284.973.216.824.503.04 2.048
bis*+6.703.903.964.971.298.549.787.012.499.102.923 .063.739.682.910.296.196.688.861.780.721.860.882.0 15.036.773.488.400.937.149.083.451.713.845.015.929 .093.243.025.426.876.941.405.973.284.973.216.824.5 03.042.047
+/- 6.703e153
+/- 6.703 * 10^153

[tuxianer]

na ich bräuchte ja nur integer. hast du nen link zu deinem projekt?

[gammatester]

Zitat:

Zitat von tuxianer

na ich bräuchte ja nur integer. hast du nen link zu deinem projekt?

Hier Delphi-Code der fast 64 Bits verarbeitet. Nicht sehr schnell da MulMod bitweise berechnet wird. Aber immer noch schneller als Multipräzision.

Delphi-Quellcode:

{MulMod and ExpMod functions,  (C) W.Ehrhardt 2008}

{---------------------------------------------------------------------------}
function mulmod63(x,y,n: uint64): uint64;
  {-returns x*y mod n, binary mul-mod from Crandall/Pomerance Alg. 9.3.1}
  { Range restriction due to uint64: 0<n<2^63}
var
  m,s: uint64;
begin
  assert(n and (uint64(1) shl 63) = 0);
  assert(n > 0);
  if x>=n then x := x mod n;
  if y>=n then y := y mod n;
  if (x=0) or (y=0) then begin
    mulmod63 := 0;
    exit;
  end;
  m := int64(1) shl 62;
  while m and x = 0 do m := m shr 1;
  s := 0;
  while m<>0 do begin
    s := s+s;
    if s>=n then dec(s,n);
    if x and m <> 0 then begin
      inc(s,y);
      if s>=n then dec(s,n);
    end;
    m := m shr 1;
  end;
  mulmod63 := s;
end;


{---------------------------------------------------------------------------}
function expmod63(a,b,n: uint64): uint64;
  {-returns a^b mod n, uses right-left form binary ladder}
  { Range restriction due to uint64: 0<n<2^63}
var

  c: uint64;
begin
  assert(n and (uint64(1) shl 63) = 0);
  assert(n > 0);
  c := 1;
  while b>0 do begin
    if odd(b) then c := mulmod63(a,c,n);
    a := mulmod63(a,a,n);
    b := b shr 1;
  end;
  expmod63 := c;
end;



{---------------------------------------------------------------------------}
function mulmod62(x,y,n: int64): int64;
  {-returns x*y mod n, binary mul-mod from Crandall/Pomerance Alg. 9.3.1}
  { Range restriction due to int64: 0<n<2^62, x>=0, y>=0}
var
  m,s: int64;
begin
  assert(n and (int64(3) shl 62) = 0);
  assert(n >  0);
  assert(x >= 0);
  assert(y >= 0);
  if x>=n then x := x mod n;
  if y>=n then y := y mod n;
  if (x=0) or (y=0) then begin
    mulmod62 := 0;
    exit;
  end;
  m := int64(1) shl 62;
  while m and x = 0 do m := m shr 1;
  s := 0;
  while m<>0 do begin
    s := s+s;
    if s>=n then dec(s,n);
    if x and m <> 0 then begin
      inc(s,y);
      if s>=n then dec(s,n);
    end;
    m := m shr 1;
  end;
  mulmod62 := s;
end;


{---------------------------------------------------------------------------}
function expmod62(a,b,n: int64): int64;
  {-returns a^b mod n, uses right-left form binary ladder}
  { Range restriction due to int64: 0<n<2^62, a>=0, b>=0}
var
  c: int64;
begin
  assert(n and (int64(3) shl 62) = 0);
  assert(n >  0);
  assert(a >= 0);
  assert(b >= 0);
  c := 1;
  while b>0 do begin
    if odd(b) then c := mulmod62(a,c,n);
    a := mulmod62(a,a,n);
    b := b shr 1;
  end;
  expmod62 := c;
end;

Jenach Delphi Version kann int64 bzw uint64 benutzt werden. Die Bereiche sind dann 0 bis 2^62-1 bzw 0 bis 2^63-1.


Gruß Gammatester

[himitsu]

also Integer geht bei direkter Rechnung nicht ;(

666^4 sprenkt schonmal die Integergrenzen und auch 512 Bit werden gesprengt

falls ich mich jetzt nicht verschätzt hab, dann komm ich auf etwa 10.0000.000 Bits für 666^58613 :gruebel:

vielleicht sollte ich mir doch noch überlegen auch noch 'en dynamischen BigInteger zu erstellen (wenn ich diesen soweit fertig hab :stupid: ), denn so geht es nicht ;(

Delphi-Quellcode:

I := IntPower(666, 58613) mod 81079;

aber über die mod_exp-Funktion geht's :-D

Delphi-Quellcode:

Function mod_exp(Basis, Exponent, Modulo: TBigInt): TBigInt;
  Begin
    Result := 1;
    While Exponent > 0 do Begin
      If Exponent.Data and $1 <> 0 Then
        Result := (Result * Basis) mod Modulo;
      Basis := (Basis * Basis) mod Modulo;
      Exponent := Exponent div 2;
    End;
  End;

oder falls es wem so gefällt

Delphi-Quellcode:

Function mod_exp(Basis, Exponent, Modulo: TBigInt): TBigInt;
  Begin
    Result := 1;
    If not Exponent.isNegative Then
      While not Exponent.isZero do Begin
        If Exponent.Data[0] and $1 <> 0 Then Begin
          Result.Multiply(Basis);
          Result.Modulus(Modulo);
        End;
        Basis.Multiply(Basis);
        Basis.Modulus(Modulo);
        Exponent.bShR(1);
      End;
  End;

Delphi-Quellcode:

Var i: TBigInt;

I := mod_exp(666, 58613, 81079);
S := I.asString;

also meine TBigInt bekommt auch 11771 raus und nicht

Zitat:

Zitat von tuxianer

Bei Größeren Zahlen kommt aber mist raus z.B.

666^58613 mod 81079=-38808

Rauskommen müsste aber: 49371.

so, jetzt muß ich nur noch etwas aufräumen und mir enlich mal 'nen Namen für mein Projekt einfallen lassen :cry:
(UCC paßt nicht mehr, da es einen kompletten Neuanfang darstellt und es sich nicht mehr hauptsächlich um Unicode-Funktionen handelt)

'nen Teil des Projekts hatte ich da mal gepostet
http://www.delphipraxis.net/internal...=879295#879295
nur TBigInt fehlt dort noch, da ich hiermit erst letzte Woche begonnen hab.
(OK, die Grundidee hatte ich schonmal im UCC versucht umzusetzen)

Ach ja, an die Rechenleistung wie vom DECMath werd ich nie rankommen, aber das hab ich auch nich ernsthaft vor ... aber zumindestens 'ne leicht zu nutzend Bibo sollte schon rauskommen :stupid:

ich beeil mich auch ... versuch bis Ende der Woche was Neues hochzuladen :angel:

[JasonDX]

Das ganze sollte auch ohne BigInt funktionieren, zumindest mit 32bit-ints als Input:

Delphi-Quellcode:

function exp_mod(x, n, m: integer): integer;
var
  i: integer;
  p, r: int64;
begin
  i := 1;
  r := 1;
  p := x;
  while (i > 0) and (i < n) do
  begin
    if (i and n > 0) then
      r := (r * p) mod m;
    p := (p * p) mod m;
    i := i shl 1;
  end;
  result := r;
end;

ok, fragt nich mich, was ich grad gedacht hab, iwie hab ich das Problem der Frage verfehlt :duck:

greetz
Mike

[tuxianer]

kannst du bitte mal die Datei uploaden, die ich für den bigint einbinden muss? und wie mach ich das sowas habe ich noch nie gemacht mit delphi. Danke schonmal!

[gammatester]

Zitat:

Zitat von tuxianer

kannst du bitte mal die Datei uploaden, die ich für den bigint einbinden muss? und wie mach ich das sowas habe ich noch nie gemacht mit delphi. Danke schonmal!

Kannst Du vielleicht noch verraten, wenn von 3 potentiellen du Du meinst, und welche Datei?

Gruß Gammatester

[tuxianer]

sorry ich meine himitsu und mir geht es um den bigint

[himitsu]

TBigInt

TBigInt ... Platz 1 ... sollte mir das was su denken geben?

[tuxianer]

also ich habe mir jetzt non vlc heruntergeladen. wiemuss ich jetzt weiter vorgehen? ich möchte nur die fmath verwenden. Ich habe jetzt alles dateien in meinen projektordner kopiert aber wenn ich unter uses fmath hinschreibe kommen fehlermeldungen.