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

[Witaliy]

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

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

[Lapp]

реализации самой длинной арифметики ненадо, только алгоритм НОД.

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

[Witaliy]

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

[volvo]

Мне нужно алгоритм нахождения НОД под длинную арифметику, тоисть что-бы был как можно быстрее

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

Мне реализации самой длинной арифметики ненадо, только алгоритм НОД.

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

[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.

Вот и весь код

[volvo]

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

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):

start
45918229978319020152259918460842947265802494231550782629695037928896009819672482

17742925879526110592144644120976424590872295015209824488903480263799072403066547

57044414290774821833767600144709902149476223247677355027908900670908237855251645

51188291262166270142784027339617652407242099624599262460884080230024463755052614

44216364261940520362299940240355135795907773161981200713888650706723252511675927

95402052155270987059091189255605432963992873441556131604818465198240888528053723

85048440809597402863724733934260447769410375552066128763718361921647860553398640

20003684560438653203774454912642936850462329801841981707317257457788803246157326

58580097987002995972980222090569414508083971873105369675264785473151080948807499

40017015154075631025576081862662838420014904101107455192905228583994079691562564

92360462202617249567687929066551487292623691354144698135285034574645955261282179

62419061688240920206596822677995385602379524829116726663756897249641247369928863

58076092492158694039343526419379317576040114602368372836109865353321592476486409

52970452774628411450010490980486335848373580495781643371647810548760206223194039

85129132578783130295948242377635261209597555558117029107121266304359601236003741

03465550358958809513675758265202241729780692905945220031286050531127990455244429

89771052267348368123601656839083557012846933968109255059796020382392298380890879

25595606470152436048609807000632491034500307076179893433068020784581749402794725

65582251499288815249277437092762923284237884236765384017879570500149524363691304

97999598589300027773627988976291226458625653839588782052883385968537198604015123

59341049623777882702166785270503705434881730565509823025004006560002619940418520

35069139524723208376814291276340661089643521944431768482707216189758292649666539

05260313008062155893975441614853862492716850581190434905621236622875795400882778

24887868392361418089129950905624999424878963371907261669736421086188751924990424

28021499341905203216663533231385504415649671992217129770924347893876202853595492

66741907626615221867222356645327278454334585315607432284278916511690831138089735

27527239606109577044999251196246760359684177280662149146220466855184083900753911

21677817942369343939213183552315188776709550427803712144540925833002829309794542

95991644498142336088428971744957572148603162448164662410716063781897592766960545

86265656156010931446565268862527133458805415097231907438274639460197957028040582

12367997032113451389755053824696943646767044714196782395018481666759297088253799

32812802974270448895413397379034842453898820582268841530474384851430213801692416

65577058126895000617955465754925363244746096212433650278405021938389178178545433

12100297771944265520567978743809468833235231156627212150249732593783759972652540

35369622965832619314106819021730262082123861812250222213229041774076026435284602

51616662801210846151504499389610552520630027547751372331183837676497804671893614

50967184418692008401302380026438561313047824357350556475511807287335039643456037

12662481950430313045597869265142201146845246574080914396548541323026213142293074

07996192726615990085653469837348989874480349695047327267241735120778028963894493

28656172359275391650516444706179357881420771559714827359591142360963341274949476

03905670673058879360115881184922135333046113925217336003548930224079950889243094

17135305512626029897344218683748251997144581328654310208019132048733671849327069

27570494125099405693083901016396481930607329316926940695134074901895472210694500

97362265628840007910916323299242707835498473728934004446809691300316585660722597

60512769450252451403126471237952519606608019831535180785442584765040733758398503

21477717446221005852946036755909892666430771826326073676557706451572790066750510

466072576
GCD = 48

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

[Witaliy]

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

[volvo]

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

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

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

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

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

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

[Witaliy]

Да, спасибо

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

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

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

[volvo]

Тоисть под Free Pascal?
да, покажыте пожалуйста.

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

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

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

[Witaliy]

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

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

[volvo]

покажыте мне готовую процедуру зделаную с моеей

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

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

[Witaliy]

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

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

[volvo]

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

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

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

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