Помощь - Поиск - Пользователи - Календарь
Полная версия: НОД под длинную арифметику
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Witaliy
Здравствуйте
Мне нужно алгоритм нахождения НОД под длинную арифметику, тоисть что-бы был как можно быстрее. У меня есть рекурсивный и с использованием mod, но под длинную арифметику ето неефективно.
Мне любой кроме остатка от деляния и рекурсии.
Мне реализации самой длинной арифметики ненадо, только алгоритм НОД.
Спасибо.
Lapp
Цитата(Witaliy @ 25.03.2009 12:31) *
реализации самой длинной арифметики ненадо, только алгоритм НОД.
А почему тогда не в Алгоритмах? blink.gif
Перенести?
Witaliy
Действительно..... smile.gif
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
Да, спасибо smile.gif

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

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

Добавлено через 8 мин.
Какия я не ввожу числа всегда выводит второе из них....
volvo
Цитата(Witaliy @ 25.03.2009 12:50) *
Тоисть под 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, тем больше выигрыш во времени...

Цитата
Ещё вопрос, знаете ли вы какой-то алгоритм для НОД без использования деления?..
Да что ты привязался к делению? Ну, замени взятие остатка вычитанием, легче тебе от этого станет? Сейчас программы выполняются за секунды, будут выполняться за часы, это все, чего ты добьешься.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.