Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

Страницы: 1 2 >
AngelOKES © (2005-03-04 13:29:00)
Нужен алгоритм работы с огромными числами (до 200 десятичных зна).
То есть их сложение, вычитание, деление и умножение.
Также проверка на простое число.

kami (2005-03-07 19:44:00) [1]
На олимпиадах попадались такие задачи - решались заведением массива, каждый элемент которого представлял часть числа с основанием (к примеру) 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)

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

Юрий К (2005-03-05 16:24:00) [3]
Поищи по словам "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.

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

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

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

Defunct (2005-03-05 09:30:00) [6]
[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

Alex Konshin (2005-03-05 09:22:00) [7]
Насколько я помню в JCL(aka Jedi) есть большие числа.

Defunct (2005-03-05 09:18:00) [8]
AngelOKES © (04.03.05 13:29)

умножение в столбик не забыл?

Ozone (2005-03-05 08:57:00) [9]
http://test-mbit.narod.ru/LONG.pdf

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

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

Anatoly Podgoretsky (2005-03-04 14:54:00) [11]
AngelOKES © (04.03.05 13:35) [4]
А Интернет у тебя есть?
Там можно найти и алгоритмы и книги Вирта.

Ozone (2005-03-04 14:40:00) [12]
AngelOKES © (04.03.05 14:27) [12]

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

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

AngelOKES (2005-03-04 14:27:00) [13]
Сайт alogolist.manual.ru не доступен.
Но все-равно всем спасибо.
Буду складывать строки, авось будет не совсем тормозной программой.

TUser (2005-03-04 14:10:00) [14]
Сложение и вычитание реализуются как в школе учили. Примерно так

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:07:00) [15]
Тип Extended не подходит так как у меня целые числа.

AngelOKES (2005-03-04 14:05:00) [16]
Да побольшому счету даже если сделать 128-разрядное число, то мне все равно не хватит.
Я думаю сделать алгоритм по строкам.
То есть записать два числа в строки и складывать или умножать как по столбику.
Правда получиться наверное медленно.
например: '123'+'456'
Сначало складывать 3+6=9
Потом 2+5, Потом 1+4 и так далее
Далее каждое число обратно записывать в строку
и получиться '579'.
Не знаю правда, никто не сталкивался с такой проблемой?

begin...end (2005-03-04 13:52:00) [17]
> AngelOKES

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

Eraser (2005-03-04 13:46:00) [18]
А тип Extended не подходит?
3.6 x 10^-4951 .. 1.1 x 10^4932

AngelOKES (2005-03-04 13:42:00) [19]
Проблема вот в чем:

9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999*9999999999999999999 999999999999999999999999999999999999999999999999999999999999999999999999999999999

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

Digitman (2005-03-04 13:38:00) [20]

> AngelOKES © (04.03.05 13:29)

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

Страницы: 1 2 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »