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

А почему тогда не в Алгоритмах?
Перенести?

Действительно.....

Ты реализацию своей длинной арифметики покажи, и заодно скажи, с числами какого порядка будешь работать. Тогда можно будет говорить о чем-то в смысле скорости...

Тебе, может, и не надо, а вот для того, чтоб как можно эффективнее вычислять НОД, ее надо знать нам...

числа <= 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.

Вот и весь код

Ты знаешь, у меня есть реализация длинной арифметики, которая вот такую программу:

uses vlint1;

function GCD (A: TLong; B: TLong): TLong;
begin
  while (a <> 0) and (b <> 0) do
    if a >= b then a := a mod b
    else b := b mod a;
  GCD := a + b;
end;

var
  a, b: tlong;
  s: ansistring;
  i: integer;

begin
  writeln('start');
  a := '3459687349586734095673495679304769348576934076';
  b := '3985793475394875757584';
  a := a * a * a;
  a := a * a * a;
  a := a * a * a;
  a := a * a * a;

  s := a;
  writeln(s);
  writeln('GCD = ' + ansistring(GCD(a, b)));
end.

выполняет меньше, чем за четверть секунды. А числа там очень немаленькие, вот лог работы программы (здесь видно, что из себя представляет число A):


Так что проблема - не в алгоритме вычисления НОД, а как раз в реализации длинных чисел...

Мжете показать реализация длинной арифметики? очень прошу....

А в твоей программе сразу же видно, где теряется производительность: вместо того, чтобы копировать огромные массивы данных в стек при вызове div_mod (это касается всех функций, но наиболее часто у тебя вызывается именно div_mod), просто передай константную ссылку:

procedure div_mod(const a,b : long;var rest: long); { <--- вот так }

, тогда данные будут неизменны, но копироваться постоянно весь массив из 2551 элемента не будет, в процедуру будет передаваться только 4-х байтовый адрес массива... Представляешь, насколько это быстрее?

Добавлено через 2 мин.
P.S. Могу, но это на FPC, если тебя устраивает этот язык - покажу... На Турбо-Паскале работать не будет...

Да, спасибо

Добавлено через 1 мин.
Тоисть под Free Pascal?
да, покажыте пожалуйста.

Добавлено через 7 мин.
Смотрите, я исправил, но пересатало роботать...

Добавлено через 8 мин.
Какия я не ввожу числа всегда выводит второе из них....

Вот тут выложил: Перегрузка операций , в самом низу поста...

Какие именно числа ты вводишь?

Да не важно, любые
например 55 5
выводит 5
45
7
выводыт 7

для любых второе число выводит
очень прошу, покажыте мне готовую процедуру зделаную с моеей. Бо я не очень знаю что изменить и как...
спасибо.

Твоя программа при попытке вычислить НОД чисел 3459687349586734095673495679304769348576934076 и 3985793475394875757584 вообще вылетает с переполнением стека. Ты ее что, не проверял со всеми возможными ключами?

Вот, я присоединил переделанную программу, которая не вылетает, считает НОД-ы, но как я тебе и говорил, здесь все зависит от реализации длинной арифметики. У тебя она не очень удачная, поэтому считается медленно. Можно чуть-чуть ускорить, конечно (например, сдвигать с использованием Move, а не циклами, обнулять не в цикле, а через FillChar), но резкого увеличения скорости все-же не будет... Надо переписывать программу полностью...

Скажыте еще пожалуйста, каую длинню арифметику лутше использовать? Такого вида как у меня, или такую с 1000 системой счисления??

Добавлено через 3 мин.
Ещё вопрос, знаете ли вы какой-то алгоритм для НОД без использования деления?..
Спасибо

Чем больше основание системы счисления - тем короче циклы, и меньше времени нужно для обработки данных. Для примера: реализация Окулова (почти та, что лежит у нас в FAQ-е. Почти - потому что работает с типом TLong, а не PLong, так проще отслеживать возможные проблемы) отрабатывает почти в 20 раз быстрее твоей на том самом примере, который я приводил в посте №12 (на TP7). А ведь там - основание СС = всего 10000. А если взять массив LongInt-ов и основание = 1 млрд., представляешь, насколько меньше "цифр" будет в такой СС? Чем больше будут числа X и Y, тем больше выигрыш во времени...

Да что ты привязался к делению? Ну, замени взятие остатка вычитанием, легче тебе от этого станет? Сейчас программы выполняются за секунды, будут выполняться за часы, это все, чего ты добьешься.