Delphi - база знаний

         

Работа с очень большими числами


Работа с очень большими числами



Это модуль для работы с очень большими числами без потери точности. Модуль даёт возможность манипулирования с 10000 и более значащими цифрами в числах. В модуле реализованы сложение, вычитание, умножение, деление, возведение в целую степень и факториал. Все функции в качестве аргументов принимают длинные строки и результат выдают тоже в виде строки.

Автор модуля Vit ()


Просьба связаться со мной, если кто хочет доработать модуль и расширить функциональность.



unit UMathServices;


{Автор Vit}

interface


Type TProgress = procedure(Done:real);

{Собственно экспортные функции}
Function ulFact(First:String):string;
Function ulSum(First, Second :string):string;
Function ulSub(First, Second :string):string;
Function ulMPL(First, Second :string):string;
Function ulPower(First, Second :string):string;
function UlDiv(First, Second:String; Precision:integer):String;   {Precision - не истинная точность а количество знаков учитываемых после запятой сверх тех которые значимы. Все знаки уже существующие в делимом и делителе в любом случае учитываются}

{Call back function for long operations}
var OnProgress: TProgress;

implementation

Uses SysUtils;

type TMathArray=array of integer;

Type TNumber=record
               int, frac:TMathArray;
               sign:boolean;
             end;

var   n1, n2:TNumber;



Procedure Str2Number(s:stringvar n:TNumber);
  var i, j, l:integer;
begin
  if s='' then
    begin
      setlength(n.int , 0);
      setlength(n.frac , 0);
      exit;
    end;
  l:=length(s);
  if s[1]='-' then
    begin
      s:=copy(s,2,l);
      l:=l-1;
      n.sign:=false;
    end
  else
    n.sign:=true;
  j:=pos('.', s);
  if j>0 then
    begin
      setlength(n.int , j-1);
      for i:=1 to j-1 do n.int[i-1]:=strtoint(s[j-i]);
      setlength(n.frac , l-j);
      for i:=1 to l-j do n.frac[i-1]:=strtoint(s[l-i+1]);
    end
  else
    begin
     setlength(n.int,l);
     for i:=1 to l do n.int[i-1]:=strtoint(s[l-i+1]);
     setlength(n.frac,0);
    end;
end;

Function Num2Array(Var n:TNumber; var a:TMathArray):integer;
  var i:integer;
begin
  result:=length(n.frac);
  setlength(a,length(n.int)+result);
  for i:=0 to length(a)-1 do if i<result then a[i]:=n.frac[i] else a[i]:=n.int[i-result];
end;

Procedure MultiplyArray(var a1, a2, a:TMathArray);
  var i, j:integer;
      b:boolean;
begin
{checking for zero, 1}
  for i:=length(a2)-1 downto 0 do
    begin
      for j:=length(a1)-1 downto 0 do
        begin
          a[j+i]:=a[j+i]+(a2[i]*a1[j]);
        end;
    end;
  repeat
    b:=true;
    for i:=0 to length(a)-1 do
      if a[i]>9 then
        begin
          b:=false;
          try
            a[i+1]:=a[i+1]+1;
          except
            setlength(a, length(a)+1);
            a[i+1]:=a[i+1]+1;
          end;
          a[i]:=a[i]-10;
        end;
  until b;
end;


Procedure Array2Num(Var n:TNumber; var a:TMathArray; frac:integer; sign:boolean);
  var i:integer;
begin
  setlength(n.frac,frac);
  setlength(n.int,length(a)-frac);
  for i:=0 to length(a)-1 do
    begin
      if i<frac then n.frac[i]:=a[i] else n.int[i-frac]:=a[i];
    end;
  n.sign:=sign;
end;

Function Number2Str(var n:TNumber):string;
  var i:integer;
      s:string;
begin
  result:='';
  for i:=0 to high(n.int) do result:=inttostr(n.int[i])+result;
  if length(n.frac)<>0 then
    begin
      for i:=0 to high(n.frac) do s:=inttostr(n.frac[i])+s;
      result:=result+'.'+s;
    end;
  while (length(result)>1) and (result[1]='0') do delete(result,1,1);
  if pos('.', result)>0 then while (length(result)>1) and (result[length(result)]='0') do delete(result,length(result),1);
  if not n.sign then result:='-'+result;
  setlength(n.int,0);
  setlength(n.frac,0);
end;

Procedure DisposeNumber(var n:TNumber);
begin
  setlength(n.int,0);
  setlength(n.frac,0);
end;


Function ulFact(First:String):string;
  var n1, n2:TNumber;
      i:integer;
      a, a1, a2:TMathArray;
      max:integer;
begin
  Str2Number('1', n1);
  Str2Number('1', n2);
  Num2Array(n1, a1);
  Num2Array(n2, a2);
  max:=strtoint(First);
  for i:=1 to strtoint(First) do
    begin
      if Assigned(OnProgress) then OnProgress((i/max)*100);
      setlength(a,length(a1)+length(a2)+1);
      MultiplyArray(a1, a2, a);
      setlength(a1,0);
      setlength(a2,0);
      a1:=a;
      Str2Number(inttostr(i), n2);
      Num2Array(n2, a2);
    end;
  Array2Num(n1, a1, 0, true);
  result:=Number2Str(n1);
  DisposeNumber(n1);
end;

Function ulPower(First, Second :string):string;
  var i, j, c:integer;
      a, a1, a2:TMathArray;
  var n1:TNumber;
      max:integer;
begin
  j:=strtoint(Second);
  if j=0 then
    begin
      result:='1';
      exit;
    end
  else
    if j=1 then
      begin
        result:=First;
        exit;
      end;


  max:=j-1;
  Str2Number(First, n1);
  c:=Num2Array(n1, a1);
  setlength(a,0);
  setlength(a2,0);
  a2:=a1;
  for i:=1 to j-1 do
    begin
      if Assigned(OnProgress) then OnProgress((i/max)*100);
      setlength(a,0);
      setlength(a,length(a1)+length(a2)+1);
      MultiplyArray(a1, a2, a);
      setlength(a2,0);
      a2:=a;
    end;
  setlength(a1,0);
  setlength(a2,0);
  c:=c*j;
  if n1.sign then
    Array2Num(n1, a, c, true)
  else
    if odd(j) then Array2Num(n1, a, c, false) else Array2Num(n1, a, c, true);
  setlength(a,0);
  result:=Number2Str(n1);
  DisposeNumber(n1);
end;




Procedure MultiplyNumbers(var n1, n2 :TNumber);
  var i:integer;
      a, a1, a2:TMathArray;
begin
  i:=Num2Array(n1, a1)+Num2Array(n2, a2);
  setlength(a,length(a1)+length(a2)+1);
  MultiplyArray(a1, a2, a);
  setlength(a1,0);
  setlength(a2,0);
  Array2Num(n1, a, i, n1.sign=n2.sign);
  DisposeNumber(n2);
  setlength(a,0);
end;


Function ulMPL(First, Second :string):string;
  var n1, n2:TNumber;
begin
  Str2Number(First, n1);
  Str2Number(Second, n2);
  MultiplyNumbers(n1, n2);
  result:=Number2Str(n1);
  DisposeNumber(n1);
end;


Procedure AlignNumbers(var n1, n2:TNumber);
  var i1, i2, i:integer;
begin
  i1:=length(n1.int);
  i2:=length(n2.int);
  if i1>i2 then setlength(n2.int, i1);
  if i2>i1 then setlength(n1.int, i2);

  i1:=length(n1.frac);
  i2:=length(n2.frac);

  if i1>i2 then
    begin
      setlength(n2.frac, i1);
      for i:=i1-1 downto 0 do
        begin
          if i-(i1-i2)>0 then n2.frac[i]:=n2.frac[i-(i1-i2)] else n2.frac[i]:=0;
        end;
    end;
  if i2>i1 then
    begin
      setlength(n1.frac, i2);
      for i:=i2-1 downto 0 do
        begin
          if i-(i2-i1)>0 then n1.frac[i]:=n1.frac[i-(i2-i1)] else n1.frac[i]:=0;
        end;
    end;
end;


Function SubInteger(a1,a2:TMathArray):integer;
  var i:integer;
      b:boolean;
begin
  result:=0;
  if length(a1)=0 then exit;
  for i:=0 to length(a1)-1 do a1[i]:=a1[i]-a2[i];
  repeat
    b:=true;
    for i:=0 to length(a1)-1 do
      if a1[i]<0 then
        begin
          b:=false;
          if i=length(a1)-1 then
            begin
              result:=-1;
              a1[i]:=a1[i]+10;
              b:=true;
            end
          else
            begin
              a1[i+1]:=a1[i+1]-1;
              a1[i]:=a1[i]+10;
            end;
        end;
  until b;
end;

Procedure AssignNumber(out n1:TNumber; const n2:TNumber);
  var i:integer;
begin
  Setlength(n1.int, length(n2.int));
  for i:=0 to length(n2.int)-1 do n1.int[i]:=n2.int[i];
  Setlength(n1.frac, length(n2.frac));
  for i:=0 to length(n2.frac)-1 do n1.frac[i]:=n2.frac[i];
  n1.sign:=n2.sign;
end;

Procedure SubNumber(var n1, n2 : TNumber);
  var i:integer;
      n:TNumber;
begin
  AlignNumbers(n1, n2);
  i:=subInteger(n1.frac, n2.frac);
  n1.int[0]:=n1.int[0]+i;
  DisposeNumber(n);
  AssignNumber(n, n1);
  i:=subInteger(n1.int, n2.int);
  if i<0 then
    begin
      subInteger(n2.int, n.int);
      AssignNumber(n1, n2);
    end
  else
    begin
      DisposeNumber(n2);
    end;
end;

Function SumInteger(a1,a2:TMathArray):integer;
  var i:integer;
      b:boolean;
begin
  result:=0;
  if length(a1)=0 then exit;
  for i:=0 to length(a1)-1 do a1[i]:=a1[i]+a2[i];
  repeat
    b:=true;
    for i:=0 to length(a1)-1 do
      if a1[i]>9 then
        begin
          b:=false;
          if i=length(a1)-1 then
            begin
              result:=1;
              a1[i]:=a1[i]-10;
              b:=true;
            end
          else
            begin
              a1[i+1]:=a1[i+1]+1;
              a1[i]:=a1[i]-10;
            end;
        end;
  until b;
end;

Procedure SumNumber(var n1, n2:TNumber);
  var i:integer;
begin
  AlignNumbers(n1, n2);
  i:=sumInteger(n1.frac, n2.frac);
  n1.int[0]:=n1.int[0]+i;
  i:=sumInteger(n1.int, n2.int);
  if i>0 then
    begin
      setlength(n1.int, length(n1.int)+1);
      n1.int[length(n1.int)-1]:=i;
    end;
  DisposeNumber(n2);
end;

Procedure SumNumbers(var n1, n2:TNumber);
begin
  if n1.sign and n2.sign then
    begin
      SumNumber(n1, n2);
      n1.sign:=true;
    end
  else
    if (not n1.sign) and (not n2.sign) then
      begin
        SumNumber(n1, n2);
        n1.sign:=False;
      end
    else
      if (not n1.sign) and n2.sign then
        begin
          SubNumber(n2, n1);
          AssignNumber(n1, n2);
        end
      else
        begin
          SubNumber(n1, n2);
        end;
end;

Function ulSum(First, Second :string):string;
begin
  Str2Number(First, n1);
  Str2Number(Second, n2);
  SumNumbers(n1, n2);
  result:=Number2Str(n1);
  DisposeNumber(n1);
end;

Function ulSub(First, Second :string):string;
begin
  Str2Number(First, n1);
  Str2Number(Second, n2);
  n2.sign:=not n2.sign;
  SumNumbers(n1, n2);
  result:=Number2Str(n1);
  DisposeNumber(n1);
end;









function  DupChr(const X:Char;Count:Integer):AnsiString;
begin
  if Count>0 then begin
    SetLength(Result,Count);
    if Length(Result)=Count then FillChar(Result[1],Count,X);
  end;
end;

function StrCmp(X,Y:AnsiString):Integer;
var
  I,J:Integer;
begin
  I:=Length(X);
  J:=Length(Y);
  if I=0 then begin
    Result:=J;
    Exit;
  end;
  if J=0 then begin
    Result:=I;
    Exit;
  end;
  if X[1]=#45 then begin
    if Y[1]=#45 then begin
      X:=Copy(X,2,I);
      Y:=Copy(Y,2,J);
    end else begin
      Result:=-1;
      Exit;
    end;
  end else if Y[1]=#45 then begin
    Result:=1;
    Exit;
  end;
  Result:=I-J;
  if Result=0 then Result:=CompareStr(X,Y);
end;



function StrDiv(X,Y:AnsiString):AnsiString;
var
  I,J:Integer;
  S,V:Boolean;
  T1,T2:AnsiString;
  R:string;
  max:integer;

begin
  Result:=#48;
  R:=#48;
  I:=Length(X);
  J:=Length(Y);
  S:=False;
  V:=False;
  if I=0 then Exit;
  if (J=0) OR (Y[1]=#48) then begin
    Result:='';
    R:='';
    Exit;
  end;
  if X[1]=#45 then begin
    Dec(I);
    V:=True;
    X:=Copy(X,2,I);
    if Y[1]=#45 then begin
      Dec(J);
      Y:=Copy(Y,2,J)
    end else S:=True;
  end else if Y[1]=#45 then begin
    Dec(J);
    Y:=Copy(Y,2,J);
    S:=True;
  end;
  Dec(I,J);
  if I<0 then begin
    R:=X;
    Exit;
  end;
  T2:=DupChr(#48,I);
  T1:=Y+T2;
  T2:=#49+T2;
  max:= Length(T1);
  while Length(T1)>=J do begin
    while StrCmp(X,T1)>=0 do begin
      X:=UlSub(X,T1);
      Result:=UlSum(Result,T2);
    end;
    SetLength(T1,Length(T1)-1);
    SetLength(T2,Length(T2)-1);
    if Assigned(OnProgress) then OnProgress(100-(Length(T1)/max)*100);
  end;
  R:=X;
  if S then if Result[1]<>#48 then Result:=#45+Result;
  if V then if R[1]<>#48 then R:=#45+R;
end;

Function Mul10(First:string; Second:integer):string;
  var s:string;
      i, j:integer;
begin
  if pos('.',First)=0 then
    begin
      s:='';
      For i:=0 to Second-1 do s:=s+'0';
      Result:=First+s;
    end
  else
    begin
      s:='';
      j:=length(First)-pos('.',First);
      if (second-j)>0 then For i:=0 to Second-j-1 do s:=s+'0';
      First:=First+s;
      j:=pos('.',First);
      First:=StringReplace(First,'.','',[]);
      insert('.',First,j+second);
      while (length(First)>0) and (First[length(First)]='0') do delete(First,length(First),1);
      while (length(First)>0) and (First[length(First)]='.') do delete(First,length(First),1);
      Result:=First;
    end;
end;

Function Div10(First:string; Second:integer):string;
  var s:string;
      i:integer;
begin
  s:='';
  For i:=0 to Second do s:=s+'0';
  s:=s+First;
  Insert('.', s, length(s)-Second+1);
  while (length(s)>0) and (s[1]='0') do delete(s,1,1);
  if pos('.',s)>0 then
    while (length(s)>0) and (s[length(s)]='0') do delete(s,length(s),1);
  if (length(s)>0) and (s[length(s)]='.') then delete(s,length(s),1);
  Result:=s;
end;

function UlDiv(First, Second:String; Precision:integer):String;
begin
  First:=Mul10(First, Precision);
  result:=Div10(StrDiv(First, Second), Precision);
end;



end.

Взято с Vingrad.ru



Содержание раздела