IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> НОД под длинную арифметику
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

Репутация: -  0  +


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

Сообщение отредактировано: Witaliy -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Witaliy @ 25.03.2009 12:31) *
реализации самой длинной арифметики ненадо, только алгоритм НОД.
А почему тогда не в Алгоритмах? blink.gif
Перенести?


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

Репутация: -  0  +


Действительно..... smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






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

Цитата
Мне реализации самой длинной арифметики ненадо, только алгоритм НОД.
Тебе, может, и не надо, а вот для того, чтоб как можно эффективнее вычислять НОД, ее надо знать нам...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

Репутация: -  0  +


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



Вот и весь код
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Ты знаешь, у меня есть реализация длинной арифметики, которая вот такую программу:
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


Так что проблема - не в алгоритме вычисления НОД, а как раз в реализации длинных чисел...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

Репутация: -  0  +


Мжете показать реализация длинной арифметики? очень прошу....
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






А в твоей программе сразу же видно, где теряется производительность: вместо того, чтобы копировать огромные массивы данных в стек при вызове div_mod (это касается всех функций, но наиболее часто у тебя вызывается именно div_mod), просто передай константную ссылку:
procedure div_mod(const a,b : long;var rest: long); { <--- вот так }
, тогда данные будут неизменны, но копироваться постоянно весь массив из 2551 элемента не будет, в процедуру будет передаваться только 4-х байтовый адрес массива... Представляешь, насколько это быстрее?

Добавлено через 2 мин.
P.S.
Цитата
Мжете показать реализация длинной арифметики?
Могу, но это на FPC, если тебя устраивает этот язык - покажу... На Турбо-Паскале работать не будет...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

Репутация: -  0  +


Да, спасибо smile.gif

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

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

Добавлено через 8 мин.
Какия я не ввожу числа всегда выводит второе из них....
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






Цитата(Witaliy @ 25.03.2009 12:50) *
Тоисть под Free Pascal?
да, покажыте пожалуйста.
Вот тут выложил: Перегрузка операций , в самом низу поста...

Цитата
Какия я не ввожу числа всегда выводит второе из них....
Какие именно числа ты вводишь?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

Репутация: -  0  +


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

для любых второе число выводит
очень прошу, покажыте мне готовую процедуру зделаную с моеей. Бо я не очень знаю что изменить и как...
спасибо.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






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

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


Прикрепленные файлы
Прикрепленный файл  LA.PAS ( 4.21 килобайт ) Кол-во скачиваний: 222
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Новичок
*

Группа: Пользователи
Сообщений: 43
Пол: Мужской
Реальное имя: Witaliy

Репутация: -  0  +


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

Добавлено через 3 мин.
Ещё вопрос, знаете ли вы какой-то алгоритм для НОД без использования деления?..
Спасибо
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Гость






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

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

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 14:06
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name