НОД под длинную арифметику Опции

[Witaliy]

Здравствуйте
Мне нужно алгоритм нахождения НОД под длинную арифметику, тоисть что-бы был как можно быстрее. У меня есть рекурсивный и с использованием mod, но под длинную арифметику ето неефективно.
Мне любой кроме остатка от деляния и рекурсии.
Мне реализации самой длинной арифметики ненадо, только алгоритм НОД.
Спасибо.

Сообщение отредактировано: Witaliy - 25.03.2009 16:39

[Witaliy]

числа <= 10^2550

Добавлено через 2 мин.

program my;
const max = 2550;
type
long  = record
 sign : char;
 len : word;
 number : array[1..max+1] of shortint;
 end;
var a,b,c,r,x,y : long;
    i,n,res : longint;
procedure input(var x : long);
var i : word;
s : char;
begin
if (s>='0') and (s<='9') then begin
read(s);
x.sign := '+';
x.len := 1;
x.number[1] := ord(s)-ord('0');
end;
while not eoln do begin
 read(s);
 if (s>='0') and (s<='9')  then begin
 inc(x.len);
 x.number[x.len] := ord(s)-ord('0');
 end;
 end;
 for i := x.len downto 1 do
  x.number[max-x.len+i] := x.number[i];
 for i := 1 to max-x.len do
  x.number[i] := 0;
 readln;
end;
procedure output(x: long);
var i : word;
begin
for i := max-x.len+1 to max do
 write(x.number[i]);
writeln;
end;

function comp_abs(a,b : long) : shortint;
var i : word;
    res : shortint;
begin
a.number[max+1] := 1; b.number[max+1] := 2;
i := 1;
while (a.number[i] = b.number[i])
 do inc(i);
if i>max then res := 0
else if a.number[i] <b.number[i]
then
res:= -1
else
res := 1;
comp_abs := res;
end;

function compare(a,b : long) : shortint;
begin
if a.sign=b.sign then
 if a.sign='-'
 then compare:=-comp_abs(a,b)
 else
 compare:= comp_abs(a,b)else
if (a.sign='-')
then compare := -1
else
compare := 1;
end;

function longLen(a : long) : word;
var I : word;
begin
 i :=1;
 a.number[max+1] := 1;
 while a.number[i]=0 do inc(i);
 if i <=max then longLen:= max-i+1
 else longLen := 1;
end;

procedure plus_abs(a,b : long; var res : long);
var i : word;
p : byte;
s : shortint;
begin
p := 0;
for i := max downto 1 do
begin
 s := a.number[i]+b.number[i]+p;
 res.number[i] := s mod 10;
 p := s div 10;
end;
res.len := longLen(res);
end;

procedure shift(var a : long;k : word);
var i : word;
begin
for i := 1 to max-k do
 a.number[i] := a.number[i+k];
for i := max-k+1 to max do a.number[i] := 0;
end;

function comp_0(x: long) : boolean;
begin
if (x.number[max-longLen(x)+1] =0) and (x.number[max]=0) then
comp_0 := true
else
comp_0 := false;
end;

procedure minus_abs(a,b : long;var res : long);
 var i: word; z : byte;
begin
z := 0;
for i := max downto 1 do
 begin
 res.number[i] := a.number[i]-b.number[i]-z;
 if res.number[i]<0
 then
 begin inc(res.number[i],10);
 z := 1;
 end
 else
 z := 0;
 end;
 res.len := longLen(res);
end;


procedure div_mod(a,b : long;var rest: long);
var i,p,nd : word;
begin
for i := 1 to max do begin
 rest.number[i] := 0;
end;
begin
 if a.len<b.len then nd := a.len
 else nd := b.len;
 for i := 1 to nd do
  rest.number[max-nd+i]:= a.number[max-a.len+i];
 if a.len>=b.len then
  for p := max-a.len+b.len to max do
   begin
   rest.len := longLen(rest);
   while comp_abs(rest,b)>=0 do
    begin
    minus_abs(rest,b,rest);
   end;
  if p<max then begin
  shift(rest,1);
  rest.number[max] := a.number[p+1];
  end;
 end;
 rest.len := longLen(rest);
end;
end;

procedure _div(a,b : long;var quot,rest: long);
var i,p,nd : word; s : byte;
begin
for i := 1 to max do begin
 quot.number[i] := 0; rest.number[i] := 0;
 end;
if comp_0(b) then
 writeln('division by zero')
else begin
 if a.len<b.len then nd := a.len
 else nd := b.len;
 for i := 1 to nd do
  rest.number[max-nd+i]:= a.number[max-a.len+i];
 if a.len>=b.len then
  for p := max-a.len+b.len to max do
   begin
   s := 0;
   rest.len := longLen(rest);
   while comp_abs(rest,b)>=0 do
    begin
    minus_abs(rest,b,rest);
    inc(s);
   end;
  shift(quot,1);
  quot.number[max] := s;
  if p<max then begin
  shift(rest,1);
  rest.number[max] := a.number[p+1];
  end;
 end;
 quot.len := longlen(quot);
 rest.len := longLen(rest);
end;
if a.sign=b.sign then quot.sign := '+'
else
quot.sign:= '-';
rest.sign := a.sign;
end;
procedure _gcd(a : long;b : long; var c : long);
begin
while (comp_0(a) <> true) and (comp_0(b) <> true)  do begin
 if comp_abs(a,b)>0 then
  div_mod(a,b,a)
 else
  div_mod(b,a,b);
 end;
plus_abs(a,b,c);
end;
begin
input(x);
input(y);
if (longLen(x)>=2550) or (longLen(y)>=2550) then
 writeln(0)
else
begin
_gcd(x,y,a);
output(a);
end;
end.

Вот и весь код