 |
eXeL@B —› Программирование —› BigInt |
| Посл.ответ | Сообщение |
|
|
Создано: 17 апреля 2009 19:43 · Поправил: Isaev · Личное сообщение · #1 Нужен быстрый алго умножения (в частности возведения в квадрат) больших целых чисел (примерно 15мб знаков) Python считает, но оооочень долго! Он даже складывает таких 2 числа около пары суток, сложение я написал на дельфи делает за секунду (грубо говоря и то большую часть времени скидывает ответ в файл), про умножение на pythone можно забыть... (2 числа в 2 раза меньше умножались у меня 52 часа, а при росте разрядов похоже експ-зависимость  ) т.ч. думаю при умножении тоже будет приятный выигрыш
Делал кто-нибудь что-то подобное? либа BigInt тоже медленная... по крайней мере складывает моя прога намного быстрее, чем из неё ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh  |
|
|
Создано: 17 апреля 2009 20:24 · Личное сообщение · #2  я бы вот что сделал , я бы написал макрос замера времени выполнения твоего выполнения данных команд , далее написал бы версию твоего процессора и выложил бы числа которые учавствовали в вычисленнии , так понимаю прога на делфе , поэтому макросами не замеришь =) , но какнить иначе замерь. А потом уже можно будет судить что быстрее выполнится. На асме если грамотно построить вычисление будет всяк быстрее ...чем на Делфе 
----- RE In Progress [!] Coding Hazard [!] Stay Clear of this Cube |
|
|
Создано: 17 апреля 2009 21:35 · Личное сообщение · #3 mak пишет: На асме если грамотно построить вычисление будет всяк быстрее ...чем на Делфе я не про асм писал, а про питон мне в общем не надо секунду делить на 2, мне и так устраивает... я вообще-то про умножение спрашивал 
----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh |
|
|
Создано: 17 апреля 2009 22:39 · Личное сообщение · #4 Isaev а не подойдет? По моему работает довольно шустро ----- iNTERNATiONAL CoDE CReW |
|
|
Создано: 18 апреля 2009 00:50 · Личное сообщение · #5 Spirit а если все цифры в виде строк, каждую перекодировать? у него представление числа в виде массива Number : Array Of LongWord; только на перекодировку куча времени уйдёт... или там встроенные средства конвертации есть и я их проглядел??? ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh |
|
|
Создано: 18 апреля 2009 01:00 · Личное сообщение · #6 А MAPLE с этим не справится? Я как-то давно экспериментировал с числами размером в пару тройку страниц. |
|
|
Создано: 18 апреля 2009 01:13 · Личное сообщение · #7 Мой кальк 15...50 знаков считает быстро Точнее считает Crypto++
|
|
|
Создано: 18 апреля 2009 01:23 · Личное сообщение · #8 s0larian пишет: Мой кальк 15...50 знаков считает быстро Челу вообще-то нужно не 15 знаков а 15 мегабайт знаков
----- Никогда не делай то, что возможно. Стремись сделать то что невозможно впринципе! |
|
|
Создано: 18 апреля 2009 01:24 · Поправил: Isaev · Личное сообщение · #9 s0larian пробовал, там ограничение до 30000 вроде (я думал ты сам писал ради интереса... )
с 15..50 знаков и у питона нет проблемм, а 15млн как-то долгова-то Кстати Crypto++ жив, в отличии от остальных... приятно, надо попробовать ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh |
|
|
Создано: 20 апреля 2009 09:58 · Личное сообщение · #10 Реализация длинки есть в java и c#, можешь попробовать на них реализовать, подсчёт факториалов всех чисел из [1;100] занял секунды полторы на яве (из них половину запускалась вм). |
|
|
Создано: 23 мая 2009 01:29 · Поправил: multiarc · Личное сообщение · #11 ... e-maxx.ru/algo/binary_pow comp-science.narod.ru/DL-AR/stepen.html [offtop] ЗЫ: учитесь юзать гугль)) [/offtop] |
|
|
Создано: 23 мая 2009 23:00 · Личное сообщение · #12 А для возведения матриц в степень есть решения? Имею ввиду НЕ тривиальный алгоритм умножения матриц. ----- Я медленно снимаю с неё UPX... *FF_User* |
|
|
Создано: 23 мая 2009 23:46 · Личное сообщение · #13 AlexZ, z0mbie.daemonlab.org/rsa.html со строк "Теперь рассмотрим вопрос о возведении большого числа в степень:". ----- Shalom ebanats! |
|
|
Создано: 19 августа 2009 23:16 · Личное сообщение · #14 Попробуй, например, реализовать метод Шёнхаге-Штрассена (если, конечно, он не используется уже в либе BigInt либо смотри работы последних лет - этуи другие материалы ежегодного симпозиума по теории вычислений (Proceedings of annual ACM symposium on Theory of computing (STOC)), в частности, вот эту на основе доклада на прошлогоднем STOC |
|
eXeL@B —› Программирование —› BigInt |
Для печати