Нужен алгоритм работы с огромными числами (до 200 десятичных зна)

← →
AngelOKES © (2005-03-04 13:29) [0]

Нужен алгоритм работы с огромными числами (до 200 десятичных зна).
То есть их сложение, вычитание, деление и умножение.
Также проверка на простое число.

← →
Digitman © (2005-03-04 13:30) [1]

ты там чего, звезды на небосеклоне что ль посчитать возбудился ?)

← →
AngelOKES © (2005-03-04 13:32) [2]

Нет мне нужно оперировать большими простыми числами и чтоб они были не менее 100 десятичных знаков.
Это нужно для реализации шифра RSA.

← →
Плохиш © (2005-03-04 13:33) [3]

Никлас Вирт ешё в своей первой книге по паскалю такой алгоритм приводил.

← →
AngelOKES © (2005-03-04 13:35) [4]

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

← →
Digitman © (2005-03-04 13:38) [5]

> AngelOKES © (04.03.05 13:29)

у тебя проблема-то в чем ? вот это не оч понятно ..

← →
AngelOKES © (2005-03-04 13:42) [6]

Проблема вот в чем:

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999*9999999999999999999 999999999999999999999999999999999999999999999999999999999999999999999999999999999

И получить результат
Конечно я утрирую такое число мне не нужно, но примерно такое же большое.

← →
Eraser © (2005-03-04 13:46) [7]

А тип Extended не подходит?
3.6 x 10^-4951 .. 1.1 x 10^4932

← →
begin...end © (2005-03-04 13:52) [8]

> AngelOKES

Думаю, есть смысл посмотреть в сторону того, как в Delphi реализована работа с типом Int64 (64-битное целое). Например, сложение: там в регистре вначале складываются младшие 32 бита слагаемых, а потом с учётом переноса складываются старшие. Можно сделать по аналогии. Однако вопрос довольно сложный, и... не думаю, что его просто решить, пользуясь только форумом :-)

← →
AngelOKES © (2005-03-04 14:05) [9]

Да побольшому счету даже если сделать 128-разрядное число, то мне все равно не хватит.
Я думаю сделать алгоритм по строкам.
То есть записать два числа в строки и складывать или умножать как по столбику.
Правда получиться наверное медленно.
например: "123"+"456"
Сначало складывать 3+6=9
Потом 2+5, Потом 1+4 и так далее
Далее каждое число обратно записывать в строку
и получиться "579".
Не знаю правда, никто не сталкивался с такой проблемой?

← →
AngelOKES © (2005-03-04 14:07) [10]

Тип Extended не подходит так как у меня целые числа.

← →
TUser © (2005-03-04 14:10) [11]

Сложение и вычитание реализуются как в школе учили. Примерно так

var P: integer;
I: integer;
begin
P:=0; result:=0;
for I:=length downto 1 do begin
K:=StrToInt(S1[i])+StrToInt(S2[i])+P;
if K > 9 then begin
P:=K-9; K:=0;
end;
result:=inttostr(K)+result;
end;
end;

В этот код добавь
1. Строки м.б. разной длины
2. м.б. минусы и DecimalSeparator
3. Проверить корректность чисел
4. Лучше писать не StrToInt + IntToStr, а записать в массив результаты сложения символов

Произведение можно тоже так, как учат в школе. Этой займет n^2 времени. Но есть более эффективный алгоритм (n^1.6, кажется). Он основан на том, что любое число можно представить в виде суммы двух частей (по разрядам)
N1 = A*10^k+B, N2=C*10^k+D,
N1*N2 = AC*10^(2k)+((A+B)*(C+D)-AC-BD)*10^k+BD, т.е. надо перемножить 3 числа половинного размера.

Вообще, надо сказать, что лучше задать этот вопрос на alogolist.manual.ru - там тебе больше расскажут. Кроме того, есть там статья про длинную арифметику. А кроме того, есть много реализаций RSA с открытым кодом, в т.ч. на Delphi - можно подсмотреть там.

← →
AngelOKES © (2005-03-04 14:27) [12]

Сайт alogolist.manual.ru не доступен.
Но все-равно всем спасибо.
Буду складывать строки, авось будет не совсем тормозной программой.

← →
Ozone © (2005-03-04 14:40) [13]

AngelOKES © (04.03.05 14:27) [12]

Строки, ИМХО, складывать - последнее дело.
Существует "куча" алгоритмов хранения и опрерирования БОЛЬШИМИ числами. У меня на работе есть даже дока по одному из вариантов.
А еще помню, делали подоное ч/з БПФ на 3-м курсе, но сейчас точного алгоритма не помню, а врать не хочу.

Если надо, то отправиь мне запрос на мыло admin3@rf.es-nso.ru - завтра с утра скину.

← →
Anatoly Podgoretsky © (2005-03-04 14:54) [14]

AngelOKES © (04.03.05 13:35) [4]
А Интернет у тебя есть?
Там можно найти и алгоритмы и книги Вирта.

← →
Slym © (2005-03-05 06:29) [15]

Смотри OpenSSL или елу похожие пакеты...
Можно попробовать TBCD (Binary Coded Decimal), но это жуткий тормоз... И для больших чисел там исходник нужно изменить немного (там ограничение на 64 байта если не ошибаюсь)...
есть сторонние пакеты (FGInt) В яндексе набери FGInt и радуйся...
FGInt быстрее TBCD в разы... А если FGInt переписать/оптимизировать!!!
Я добился практически 2х кратного прироста скорости
Кстати есть компоненты типа LockBox (на Torry) там RSA,DSA всякие уже реализованы и соответственно там есть модуль для работы с большими числами, но тоже тормозной (там работа побайтно!!! и это на заре 64битных (8 байт) процессоров)

А в строчку как в школе забей... И не слушай школьников что мол в строчку круто.

← →
Ozone © (2005-03-05 08:57) [16]

http://test-mbit.narod.ru/LONG.pdf

← →
Defunct © (2005-03-05 09:18) [17]

Насколько я помню в JCL(aka Jedi) есть большие числа.

[17] на MMX

while <не вышли за границу множителя> do
begin
заполняешь все 8 байт MM1 очередной порцией (4 бита) множителя (MOVQ MM1, [..]).

while <не вышли за границу множимого> do
begin
загоняешь в MM2 регистр очередную порцию (32 бита) множимого (MOVQ MM2, [..]) (разбить на тетрады).
PMUL MM2, MM1 - сохраняешь (64 бита) промежуточного рез-тата.
end;
end;

Складываешь все промежуточные результаты PADD MM1, MM2

← →
palva1 (2005-03-05 09:57) [20]

Алгоритмы все простые за исключением деления.
Посмотрите старую дискуссию, http://www.relib.com/forums/topic.asp?id=781902
которая началась с вычисления квадратного корня. Видимо человеку это понадобилось при разложения большого числа на простые множители.
А дальше зашел разговор о делении больших чисел. там приведена полезная ссылка на главу из книги Шеня.
http://www.3ka.mipt.ru/vlib/books/Programming/ComputerScience/shen/allsrs/math/gl1.html
сейчас я проверял, ссылка работает. Правда в алгоритме нужно уметь делить большое число на два. Предполагается двоичное представление, когда число легко сдвинуть на один бит. Если у вас десятичное представление, то вспомните, как делят числа на арифмометре "Феликс". Если надо, я могу напомнить.

Книгу Шеня, кстати, рекомендую. Там все алгоритмы на паскале.

Да, недавно вышла хорошая книга Вельшенбаха
http://www.3st.ru/description.asp?id=91
там подробно разжевываются алгоритмы длинной арифметики. Книга у меня есть. Могу прислать что-нибудь из сидирома. А может его и в интернете можно найти.

← →
Юрий К (2005-03-05 16:24) [22]

Поищи по словам "Miracl library", может быть и то, что нужно.
Свободно для некоммерческого использования.

MIRACL is a highly efficient and portable Multiprecision Integer and Rational
Arithmetic C/C++ Library. Full source code is provided. Its main area of
application is in the implementation of Public Key Cryptography systems and
protocols. Many example programs are provide.

Готовые компоненты для RSA(и не только) в Delphi - LockBox v.2
Есть исходники
http://torry.net/vcl/security/strong/tplockbox.zip
P.S. Спасибо Vand777 за ссылочку

На олимпиадах попадались такие задачи - решались заведением массива, каждый элемент которого представлял часть числа с основанием (к примеру) 1 000. Удобно заполнять (с конца строки, представляющей число - по 3 знака в элементы массива, начиная с последнего) и считать. Те же вычисления в столбик, как в строках:
345675х657543
(345)(675)
х (657)(543)
----------
(187) (335+366) (525)
+ 226 (665+443) (475)
==========================
(226+1)(295+1) (176) (525)
==========================
(227)(296)(176)(525)

Нужен алгоритм работы с огромными числами (до 200 десятичных зна) Найти похожие ветки