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

[Witaliy]

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

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

[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

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