Быстрое умножение длинных чисел. |
Быстрое умножение длинных чисел. |
klem4 |
6.03.2011 10:14
Сообщение
#1
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Всем привет. Может кто-то подсказать описание хорошего алгоритма умножения длиннных чисел ? Желательно с примерами работы алгоритма. Необходимо за время ~ 1c. перемножить несколько сотен длинных чисел (100-6000 знаков) на 3-4-х значные числа. Простой столбик в этом время не укладывается
-------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Гость |
8.03.2011 11:21
Сообщение
#2
|
Гость |
> for (int i = a_size - 1; i >= 0; i-- )
{ int value = bonus + a[i] * n; if ( value >= 10 ) { bonus = (int)(value / 10); value %= 10; } else > 10 То есть отнование системы счисления - 10? Это плохо. Самое быстрое - основанием брать 2^32. И в процессоре есть готовая операция, которая сразу получает (a+b) mod 2^32 и (a+b) div 2^32. Правда, компилятор Борланда, например, никак не заставить это применить, насчёт компиляторов от Микрософта и Интела не знаю. Если тебе надо, чтобы ещё и быстро выводилось, то пойди на компромисс - в качестве основния возьми 1000000000. Считаться будет медленнее, чем с 2^32, но в 9 раз быстрее, чем с 10. И, опять же, перемножить два 32-разрядных числа и поделить 64-разрядный результат на 1000000000 - это очень просто записывается на асме (тупо mul, div подряд, промежуточный 64-разрядный результат хранится в 2х регистрах, edx и eax), но невозможно заставить компилятор Борланда сделать это по-простому. |
Текстовая версия | 30.05.2024 18:12 |