Наименьший общий делитель

[Witaliy]

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

[Stilet]

под длинную арифметику

НАсколько длинную?

[maladoy]

function nod(x,y:integer):integer; 
var r:integer;
begin repeat
r:=x mod y; x:=y; y:=r;
until y=0; nod:=x;end;

[Serge_Bliznykov]

r:=x mod y;

сейчас плохо думается с утра , но, предполагаю,
что используя алгоритм, предложенный maladoy, можно операцию целочисленного деления заменить на вычитание x - y до тех пор, пока x>y
т.е. данный оператор можно заменить на:

r:=x;
while r>y do r := r - y;

[Witaliy]

НАсколько длинную?

До 2550 знаков

Да, действительно, было бы хорошо без деления...

сейчас плохо думается с утра , но, предполагаю,
что используя алгоритм, предложенный maladoy, можно операцию целочисленного деления заменить на вычитание x - y до тех пор, пока x>y
т.е. данный оператор можно заменить на:
Код:

r:=x;
while r>y do r := r - y;

Это весь код? Или ещё что-то надо?

[Serge_Bliznykov]

это только замена ОДНОГО оператора (который r:=x mod y)
полностью код будет выглядеть так (только типы свои подставите. ну и операцию вычитания - вызов своей "длинной" функции:

function nod(x,y:integer):integer; 
var r:integer;
begin 
  repeat
     r:=x;
     while r>y do r := r - y;  
     x:=y; y:=r;
  until y=0; 
  nod:=x;
end;

p.s. за эффективность данного кусочка я ответственность не несу...

[Witaliy]

Что-то она зависает и без длинной арифметики...

[-HunteR-]

Наименьший целый общий делитель для всех чисел - 1

[maladoy]

Нод-наибольший общий делитель.

[Stilet]

Нод-наибольший общий делитель.

Если бы автор правильно называл свои темы то и вопросов бы таких не возникало. Иначе как реагировать на непонятные три буквы в названии? Мож имеется ввиду работа с всем извесным антивирем...