ubigintsv2.pas

Delphi的大数运算演示 pudn上大多是VC的 所以传个Delphi的

    Sign := signout;
    remain.Sign := signout;
    remain.Trim;
    Trim;
    // only change signs if not zero...
    //      sign := signout;
    //      remain.sign := signout;
  end
  else
  begin
    remain.Assign(self);
    AssignZero;
  end;
end;

{**************** Compare ************}
function TInteger.Compare(i2: TInteger): integer;
  {Compare - to Tinteger}
  {return +1 if self>i2, 0 if self=i2 and -1 if self<i2)}
begin
{
  // check for bad signs
  if ((self.IsZero) and (self.Sign <> 0)) or
     ((self.iszero=false) and (self.sign = 0)) or
     ((i2.IsZero) and (i2.Sign <> 0)) or
     ((i2.iszero=false) and (i2.Sign = 0)) then
       showmessage('bad sign in Compare i2');
}

  //  if (sign < 0) and (i2.sign > 0) then
  if Sign < i2.Sign then
    Result := -1
  //  else if (sign > 0) and (i2.sign < 0) then
  else if Sign > i2.Sign then
    Result := +1
  else if (self.Sign = 0) and (i2.Sign = 0) then
    Result := 0
  else
  begin
    {same sign} Result := AbsCompare(i2);
    if (Sign < 0) then
      Result := -Result; {inputs were negative, largest abs value is smallest}
  end;
end;

{****************** Compare (Int64) *********}
function TInteger.Compare(i2: int64): integer;
  {Compare - to int64}
  {return +1 if self>i2, 0 if self=i2 and -1 if self<i2)}
begin
  icomp3.Assign(i2);
{
  //  check for bad signs...
  if ((self.IsZero) and (self.Sign <> 0)) or
     ((self.iszero=false) and (self.sign = 0)) or
     ((icomp3.IsZero) and (icomp3.Sign <> 0)) or
     ((icomp3.iszero=false) and (icomp3.Sign = 0)) then
       showmessage('bad sign in compare int64');
}

  //  if (sign < 0) and (icomp3.sign > 0) then
  if Sign < icomp3.Sign then
    Result := -1
  //  else if (sign > 0) and (icomp3.sign < 0) then
  else if Sign > icomp3.Sign then
    Result := +1
  else if (self.Sign = 0) and (icomp3.Sign = 0) then
    Result := 0
  else
  begin
    {same sign} Result := AbsCompare(icomp3);
    if Sign < 0 then
      Result := -Result;
  end;
end;

{************* CompareZero *************}
function TInteger.CompareZero: integer;
begin
{
// check for bad signs...
  if ((iszero) and (sign <> 0)) or
     ((iszero=false) and (sign=0)) then
    showmessage('Bad Sign in CompareZero');
}
  Result := Sign;
  //  if iszero then
  //    result := 0
  //  else if sign = 1 then
  //    Result := 1
  //  else if sign = -1 then
  //    Result := -1
  //  else Result := 0;
end;

{************* AbsCompare *************}
function TInteger.AbsCompare(i2: Tinteger): integer;
  {compare absolute values ingoring signs - to Tinteger}
var
  i: integer;
begin

{
  // check for bad signs
  if ((self.IsZero) and (self.Sign <> 0)) or
     ((self.iszero=false) and (self.sign = 0)) or
     ((i2.IsZero) and (i2.Sign <> 0)) or
     ((i2.iszero=false) and (i2.Sign = 0)) then
       showmessage('bad sign in ABSCompare(i2)');
}

  Result := 0;
  //  if self.iszero and i2.iszero then
  if (self.Sign = 0) and (i2.Sign = 0) then
    Result := 0
  else if length(fDigits) > length(i2.fDigits) then
    Result := +1
  else if length(fDigits) < length(i2.fDigits) then
    Result := -1
  else {equal length}
    for i := high(fDigits) downto 0 do
    begin
      if fDigits[i] > i2.fDigits[i] then
      begin
        Result := +1;
        break;
      end
      else if fDigits[i] < i2.fDigits[i] then
      begin
        Result := -1;
        break;
      end;
    end;
end;

{************* AbsCompare *************}
function TInteger.AbsCompare(I2: int64): integer;
  {compare absolute values ingoring signs - to Tinteger}
var
  i3: Tinteger;
begin
  i3 := tinteger.Create;
  i3.Assign(i2);
  Result := AbsCompare(i3);
  i3.Free;
end;


{*********** Factorial *******}
procedure TInteger.Factorial;
{Compute factorial - number must be less than max integer value}
var
  n: int64;
  i: integer;
begin
  n := 0;
  if (Compare(high(integer)) >= 0) or (Sign < 0) then
    exit;
  //  if compare(0) = 0 then
  if CompareZero = 0 then
  begin  {0! =1 by definition}
    AssignOne;
    exit;
  end;
  for i := high(fDigits) downto 0 do
  begin
    n := n * Base + fDigits[i];
  end;
  Dec(n);
  while n > 1 do
  begin
    Mult(n);
    Dec(n);
    {provide a chance to cancel long running ops}
    //   if (n mod 64) =0
    if (n and $4f) = $4f then
      application.ProcessMessages;
  end;
end;

{************** ConvertToDecimalStirng ********}
function TInteger.ConvertToDecimalStringold(commas: boolean): string;
var
  i:     integer;
  n, nn: int64;
  c:     byte;
  Count: int64;
  b:     integer;
begin
  Result := '';
  b      := GetBasePower;
  if length(fDigits) = 0 then
    AssignZero;
  Count := 0;  {digit count used to put commas in proper place}
  for i := 0 to high(fDigits) do
  begin
    n := fDigits[i];
    repeat
      // start update by Charles Doumar
      nn := n div 10;
      c  := n - nn * 10;
      n  := nn;
      // end
      //              c:=n mod 10;
      //              n:=n div 10;
      Inc(Count);
      Result := char(Ord('0') + c) + Result;
      if commas and (Count mod 3 = 0) then
        Result := ThousandSeparator + Result;
    until (Count mod b = 0) or ((i = high(fDigits)) and (n = 0));
  end;

  if Result[1] = ',' then
    Delete(Result, 1, 1); {might have put in one comma too many}
  if Result = '' then
    Result := '0'
  else if Sign < 0 then
    Result := '-' + Result;
  if Result = '-0' then
    Result := '0';
end;


(*
{************** ConvertToDecimalStirng ********}
function TInteger.ConvertToDecimalString(commas: boolean): string;
var
  i, j, NumCommas, CurPos, StopPos, b, DigCount, NewPos, Top: integer;
  n, nn, last: int64;
  c: byte;

begin
  if length(fDigits) = 0 then
    AssignZero;
  Top    := high(self.Digits);
  Last   := fDigits[Top];
  if Last = 0 then
  begin
    Result := '0';
    exit;
  end;
  Result := '';
  b      := GetBasePower;
  DigCount := Top * b + 1 + trunc(Math.log10(Last));
  Dec(Top);
  if Sign > 0 then
  begin
    CurPos := DigCount;
    SetLength(Result, CurPos);
    StopPos := 0;
  end
  else
  begin
    CurPos := DigCount + 1;
    SetLength(Result, CurPos);
    Result[1] := '-';
    StopPos   := 1;
  end;
  for i := 0 to Top do
  begin
    n := fDigits[i];
    for j := 1 to b do
    begin
      nn := n div 10;
      c  := n - nn * 10;
      n  := nn;
      Result[CurPos] := char($30 + c);
      Dec(CurPos);
    end;
  end;
  repeat
    nn   := Last div 10;
    c    := Last - nn * 10;
    Last := nn;
    Result[CurPos] := char($30 + c);
    Dec(CurPos);
  until CurPos <= StopPos;

  if Commas = True then
  begin
    CurPos    := Length(Result);
    NumCommas := (DigCount - 1) div 3;
    if NumCommas > 0 then
    begin
      NewPos := CurPos + NumCommas;
      SetLength(Result, NewPos);
      for i := 1 to NumCommas do
      begin
        Result[NewPos]     := Result[CurPos];
        Result[NewPos - 1] := Result[CurPos - 1];
        Result[NewPos - 2] := Result[CurPos - 2];
        Result[NewPos - 3] := ThousandSeparator;
        Dec(NewPos, 4);
        Dec(CurPos, 3);
      end;
    end;
  end;
end;
*)

{************** ConvertToDecimalStirng ********}
function TInteger.ConvertToDecimalString(commas: boolean): string;
var
  i, j, NumCommas, CurPos, StopPos, b, DigCount, NewPos, Top: integer;
  n, nn, last: int64;
  c: byte;

begin
  if length(fDigits) = 0 then
    AssignZero;
  if IsZero then
  begin
    Result := '0';
    exit;
  end;
  Result := '';
  b      := GetBasePower;
  Top    := high(self.Digits);
  Last   := fDigits[Top];
  DigCount := Top * b + 1 + trunc(Math.log10(Last));
  Dec(Top);
  if Sign > 0 then
  begin
    CurPos := DigCount;
    SetLength(Result, CurPos);
    StopPos := 0;
  end
  else
  begin
    CurPos := DigCount + 1;
    SetLength(Result, CurPos);
    Result[1] := '-';
    StopPos   := 1;
  end;
  for i := 0 to Top do
  begin
    n := fDigits[i];
    for j := 1 to b do
    begin
      nn := n div 10;
      c  := n - nn * 10;
      n  := nn;
      Result[CurPos] := char($30 + c);
      Dec(CurPos);
    end;
  end;
  repeat
    nn   := Last div 10;
    c    := Last - nn * 10;
    Last := nn;
    Result[CurPos] := char($30 + c);
    Dec(CurPos);
  until CurPos <= StopPos;

  if Commas = True then
  begin
    CurPos    := Length(Result);
    NumCommas := (DigCount - 1) div 3;
    if NumCommas > 0 then
    begin
      NewPos := CurPos + NumCommas;
      SetLength(Result, NewPos);
      for i := 1 to NumCommas do
      begin
        Result[NewPos]     := Result[CurPos];
        Result[NewPos - 1] := Result[CurPos - 1];
        Result[NewPos - 2] := Result[CurPos - 2];
        Result[NewPos - 3] := ThousandSeparator;
        Dec(NewPos, 4);
        Dec(CurPos, 3);
      end;
    end;
  end;
end;


{********* ConvertToInt64 **********}
function TInteger.ConvertToInt64(var n: int64): boolean;
var
  i: integer;
  savesign: integer;
begin
  Result   := False;
  savesign := Sign;
  Sign     := +1;
  if (self.Compare(9223372036854775806) < 1) then
  begin
    n := 0;
    for i := high(fDigits) downto 0 do
      n := Base * n + fDigits[i];
    if savesign < 0 then
      n := -n;
    Result := True;
  end;
  Sign := savesign;
end;

{********* Pow **************}
procedure Tinteger.Pow(const exponent: int64);
{raise self to the "exponent" power}
var
  i2: tinteger;
  n:  int64;
  s:  integer;
begin
  n := exponent;
  if (n <= 0) then
  begin
    if n = 0 then
      AssignOne
    else
      AssignZero;
    exit;
  end;
  s := Sign;
  if ((s < 0) and not (odd(n))) then
    s := 1;
  Sign := 1;
  i2 := TInteger.Create;
  i2.AssignOne;
  if (n >= 1) then
    if n = 1 then
      i2.Assign(self)
    else
    begin
      repeat
        //        if (n mod 2)=1 then i2.mult(self);
        if (n and $1) = 1 then
          i2.Mult(self);
        //        n:=n div 2;
        //        mult(self);
        n := N shr 1;
        Square;
      until (n = 1);
      i2.Mult(self);
    end;
  Assign(i2);
  Sign := s;
  i2.Free;
end;

(*
procedure Tinteger.ModPow(const i2, m: Tinteger);
{self^I2 modulo m}
var
  ans, rest, two, e: Tinteger;
  hulp: integer;
begin
  if (length(i2.fDigits) = 0) or (length(m.fDigits) = 0) then
    exit;
  rest := Tinteger.Create;
  ans  := tinteger.Create;
  two  := tinteger.Create;
  e    := tinteger.Create;
  ans.AssignOne;
  two.Assign(2);
  e.Assign(i2);
  hulp := e.Compare(1);
  if hulp >= 0 then
    if hulp = 0 then
    begin
      Modulo(m);
      ans.Assign(self);
    end
    else
    begin
      repeat
        e.DivideRem(two, rest);
        if rest.Compare(1) = 0 then
        begin
          ans.Mult(self);
          //here I went wrong(not altogether, amounts to the same)
          ans.Modulo(m);
        end;
        //mult(self);
        Square;
        Modulo(m);
      until (e.Compare(1) = 0);
      ans.Mult(self);
      //here I went wrong I wrote ans.square and that is somethingdifferent
      ans.Modulo(m);
    end;
  Assign(ans);
  rest.Free;
  ans.Free;
  two.Free;
  e.Free;
end;
 *)


//partially rewritten by hk Oct 2005
procedure Tinteger.ModPow(const i2, m: Tinteger);
{self^I2 modulo m}
var
  ans, e, one: Tinteger;
  hulp: integer;
begin
  {if (length(i2.fdigits) = 0) or (length(m.fdigits) = 0) then
    exit;}
  hulp := i2.CompareZero;
  if hulp <= 0 then
    if hulp = 0 then
    begin
      AssignOne;
      exit;
    end
    else
      exit;
  if m.IsZero then
    exit;
  one := tinteger.Create;
  one.AssignOne;
  ans := tinteger.Create;
  e   := tinteger.Create;
  ans.AssignOne;
  e.Assign(i2);
  hulp := e.Compare(one);
  if hulp >= 0 then
    if hulp = 0 then
    begin
      Modulo(m);
      ans.Assign(self);
    end
    else
    begin
      repeat
        if e.IsOdd then
        begin
          ans.Mult(self);
          ans.Modulo(m);
        end;
        e.divide2;
        Square;
        Modulo(m);
      until (e.Compare(one) = 0);
      ans.Mult(self);
      ans.Modulo(m);
    end;
  Assign(ans);
  ans.Free;
  e.Free;
  one.Free;
end;


{square root}
procedure Tinteger.Sqroot;
begin
  NRoot(2);
end;

{****************** GCD ***************}
procedure Tinteger.Gcd(const I2: tinteger);
 {greatest common divisor}
 {revised by Hans Aug 2005 to handle 0 "I2" value }
 {revised by hk Oct 2005: swapping by hashing}
var
  gcdarr:  array[0..1] of tinteger;
  a, b, h: integer;
begin
  gcdarr[0] := tinteger.Create;
  gcdarr[1] := tinteger.Create;
  if AbsCompare(i2) = 1 then
  begin
    gcdarr[0].Assign(self);
    gcdarr[1].Assign(i2);
  end
  else
  begin
    gcdarr[1].Assign(self);
    gcdarr[0].Assign(i2);
  end;
  if gcdarr[1].CompareZero = 0 then
  begin
    AssignZero;
    gcdarr[0].Free;
    gcdarr[1].Free;
    exit;
  end;
  a := 0;
  b := 1;
  repeat
    gcdarr[a].Modulo(gcdarr[b]);
    if gcdarr[a].CompareZero <> 0 then
    begin
      h := a;
      a := b;
      b := h;
    end;
  until gcdarr[a].CompareZero = 0;
  Assign(gcdarr[b]);
  self.AbsoluteValue;