Форум на Исходниках.RU

как найти остаток от деления огромных чисел?

NetVir — Mon, 12 Nov 2007 02:32:31 +0000

NetVir: Мда, AndrЮshkA, ежели нет желания использовать матпакеты и сторонние библиотеки по работе с бигинтами, а так же, если при операции a^b(mod c) ты используешь числа a,b,c в пределах Longword'a, то вот тебе красивый алгоритм, который и сам использовал в далеком прошлом http://algolist.manual.ru/maths/count_fast/fast_exp.php

как найти остаток от деления огромных чисел?

Dethlord — Sun, 11 Nov 2007 16:50:53 +0000

Dethlord: Народ че вы выдувываете-Я ЖЕ ПОСЧИТАЛ
А данные храню в STRING можно туда запихнуть очень длинную строку(длинное число)

Добавлено 11.11.07, 16:52

Цитата AndrЮshkA @ 11.11.07, 16:10

Dethlord, а с громадными числами это будет работать?

да
глупый вопрос после моего ответа (255^1300)/(1432)

как найти остаток от деления огромных чисел?

Rose — Sun, 11 Nov 2007 16:30:38 +0000

Rose:

Цитата

Dethlord, а с громадными числами это будет работать?

Проблема громадных целых чисел в том, что их нужно как-то хранить. 8 байт, предоставляемыми Int64 явно недостаточно. Extended - тоже не подходит но не столько из-за размера (10 байт), сколько из-за специфики формата чисел с плавающей точкой. Вот, недавно обсуждалось:
чего я не дочитал в ф-ции Trunc ?
Да и из-за размера тоже, сами подумайте, как число из >100000 ДЕСЯТИЧНЫХ знаков поместится в 80 ДВОИЧНЫХ знаках? :)
Для хранения таких чисел нужно заводить свой тип, а за основу брать, например, динамичесский массив, - размер можно менять динамически, получим столько двоичных знаков, сколько захотим. Именно так в FGInt и реализовано.

как найти остаток от деления огромных чисел?

AndrЮshkA — Sun, 11 Nov 2007 16:10:05 +0000

AndrЮshkA:

Цитата Rose @ 11.11.07, 15:56

А это для чего? Не для RSA часом?

Если я правильно угадал, то используйте лучше библиотеку FGInt, Extended для хранения больших целых явно не подходит...
http://www.submanifold.be/triade/GInt/gint.html

да, для RSA, так и придется использовать GInt

Добавлено 11.11.07, 16:19
Dethlord, а с громадными числами это будет работать?

и почему мой вариант не прокатывает:(
по идее все правильно

как найти остаток от деления огромных чисел?

Dethlord — Sun, 11 Nov 2007 16:01:08 +0000

Dethlord: Взятие модуля

С этим алгоритмом пришлось изрядно повозиться из-за того, что операция Mod практически нигде не описана. Опять вспоминаем математику:

A mod A=0

A mod 1=0

A mod B=C означает, что существует такое положительное целое число K, что B*K+C=A. C нам надо найти. Что ж, существует очень простой способ: отнимать от A число B до тех пор, пока A>=B. В итоге получим C. Но представьте только, сколько операций вычитания придётся сделать при больших числах!!! Надо как-то оптимизировать вычитание. До сих пор мы не использовали число K. Каким оно может быть? K может быть разложено на произведение чисел. Чем оптимальнее будут выбраны эти числа, тем лучше! Самое лучшее решение, что приходит в голову: выбирать K поразрядно (по степеням 10). Протестируем идею - рассмотрим пару примеров:

1. 1234 mod 7=2

2. 1237 mod 70=44 44 mod 7=2

3. 1237 mod 700=534 534 mod 70=44 44 mod 7=2

Значит, мы можем варьировать значением числа K~B (с определёнными условиями)!

Воплощаем мысль в алгоритм:

1. Откинем все частные случаи и тогда получим, что: A>B

2. Итак, если A>B:

3. Будем умножать B на 10 до тех пор, пока длины чисел A и B не сравняются.

4. Если A=B, то mod=0

5. Если A делим B на 10

6. Поочерёдно умножаем B на i=1,2,3,… пока B не станет больше A

7. Берём предыдущее число (i), на которое было умножено B, и выполняем A=A-B*i

8. Идём на шаг 2

9. Результат=A

Возможно, пример поможет понять алгоритм:

356395 mod 37=C, C=?

A=356395

B=37

A>B – верно

Умножаем B на 10, пока длины не сравняются: B=370000

B>A – с нулями мы переборщили => B=37000 ** умножили на 1000

B*1=37000

B*2=74000

B*3=111000

B*4=148000

B*5=185000

B*6=222000

B*7=259000

B*8=296000

B*9=333000

B*10=37000 B>A – верно

A=A-B*9=356395-333000=23395 ** умножили на 9

A=23395

B=37

A>B – верно

B=37000 – перебор => B=3700 ** умножили на 100

B*1=3700

B*2=7400

B*3=11100

B*4=14800

B*5=18500

B*6=22200

B*7=25900 B>A – верно

A=A-B*6=23395-22200=1195 ** умножили на 6

A=1195

B=37

A>B – верно

B=3700 – перебор => B=370 ** умножили на 10

B*1=370

B*2=740

B*3=1110

B*4=1480 B>A – верно

A=A-B*3=1195-1110=85 ** умножили на 3

A=85

B=37

B=370 – перебор, B=37 ** умножили на 1

B*1=37

B*2=74

B*3=111 B>A – верно

A=A-B*2=85-74=11 ** умножили на 2

A=11

B=70

A C=11

Всего потребовалось: 4 вычитания и 19 сложений (куда пропали умножения, смотрите в исходном коде)

А если бы мы пользовались простыми вычитаниями, то их потребовалось бы: 9632 штуки!!! Кстати, это и есть число K – целая часть от деления A на B, а ведь из приведённого примера мы можем вычленить это число, если обратим внимание на строки, помеченные **: если выпишем вынесенные числа, то получим: 1000 9 100 6 10 3 1 2. А теперь расставим арифметические знаки: 1000*9+100*6+10*3+1*2=9632. Это свойство используется в алгоритме деления!!!

Добавлено 11.11.07, 16:07
а если вам нужно произвести арихм операцию (255^1300)/(1432) то ОТВЕТ:

221968601687332940125473524001319167290690145331700911850517840694228359295951886904985116094947547560094393732587243030884636739478396186644213022368492295652669032674751111423710402265673553683739057056590811557750698070255649386179432599281174635164697046623002194031036924296496405207339746375766234204743513373287380132357946126518892683558694975158993687228337360914916795129194351108101285572771172765471395796980915929204001621236624985029012519860678472532294688844970164121322454811228892727326201193037612120602091397997052064517727252745692840237420848059334701276742531724785505507932540824438253738252427401147011653769174797302468210812442826908646125866468373060082132211971214133447620298308191756877456939971016172596004036990927026947793396002591066398665454215153744453436811038000117260772265216224319917416283053015429970317652166956656269547478486634773879748529341469082904764581937167915822819479862276525418819583867146948523151432608010425673681889351969730996127057659260198868276807118860056734410043771688327361040312328874227770038928179238408306946670975492857491843306398068328669153177225773469898786817688727685953245061725474702724514168553659853170075289886029974297936207176281886796064827168782639380275560792337024230517592779976424275989797172286525018371603046155323988270637301056416310953232882382977457826428750472160824966468344761978721100150180562939610659163799192712653455032436432333411785988606383193300111538613167003183079951935275397677008263753282488869497133670328956201006888010413777370347542594935077918474161930753848235783506597343568176197949607624516495948998543400377771631018065000268251205972220356172710886978703608104011199024605705146105004341385768293728193503991652454540451725876696373589503369513937962783223369506817971462349378638078557013995161500758689230323194454645609907359980770659583707808287148125013346009970885211731523362700455808670849412897881733478454834087345333565098881455030593410941668085529622541321713147698303475054952900340209671830899291674281569265609428708718273385074388187771644685517825932015857206508608781519646351245605760432245812772597097490966910545621841924501371733482011312920147897355779743692035553310991765527714776571387155273625140810201431937098983760304038407108779033652252910113162894593313745096282190619405269661483647206265275191703290841774872729791350991591551589765192769283457753354500201642634244079107417691152725878468783687801042886036311861935589708952442629450952019470403809520180725486907439244820803053467263171054428234558471057132918692907696097390711176427979793939258775772016097420284711258516442187561616238703695779899794372445271032891810928016294739329178545379323338739847180334013216060431222499684732811138973183576766390925560455332042259715311843023622475492264158856198049066576711239479695283411351873054356535612311726466236795098861163762853961191249986651903121344756536158335386538748380525525176301126941407582795604220800045545952608301057503880253989749662893516637136224120032935045518543116468735529850132346396672219555764668976761881041112658307580641528081627,761

:wall: :lool: :tong: :wacko: :)

как найти остаток от деления огромных чисел?

Rose — Sun, 11 Nov 2007 15:56:45 +0000
Rose: А это для чего? Не для RSA часом?

Если я правильно угадал, то используйте лучше библиотеку FGInt, Extended для хранения больших целых явно не подходит...
http://www.submanifold.be/triade/GInt/gint.html

как найти остаток от деления огромных чисел?

AndrЮshkA — Sun, 11 Nov 2007 15:37:42 +0000
AndrЮshkA: winsoft, читай внимательней:)

как найти остаток от деления огромных чисел?

winsoft — Sun, 11 Nov 2007 15:33:32 +0000
winsoft: AndrЮshkA, юзаем оператор mod

как найти остаток от деления огромных чисел?

AndrЮshkA — Sun, 11 Nov 2007 15:27:32 +0000
AndrЮshkA: делал так
a,b,c:extended;

c:=a-b*int(a/b);

вроде по идее должно работать, но выдает 0