Быстрое умножение длинных чисел. |
Быстрое умножение длинных чисел. |
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";'
|
-TarasBer- |
6.03.2011 12:09
Сообщение
#2
|
Гость |
Надо умножить длинное на короткое?
Алгоритм оптимизировать тут некуда. Если столбик не очень далеко не укладывается, то оптимизируй код: храни все числа в бинарном виде (ну то есть не цифры храни, а блоки по 4 байта от каждого), после каждого умножения запоминай старое значение edx и прибавляй к следующему результату. |
Lapp |
6.03.2011 13:17
Сообщение
#3
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Думаю, кроме столбика все равно ничего нет. Другой вопрос - КАК ты хранишь числа и как организовыван счет. Тут много ресурсов для оптимизации..
-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
klem4 |
8.03.2011 10:03
Сообщение
#4
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Буду рад любым подсказкам, числа храню в массиве (vector), вот пример умножения факториала 1110 на 1111 (получение 1111!)
Время одного умножения слишком большое(для решения моей задачи): $ g++ -o forum forum.cpp && time ./forum real 0m0.021s user 0m0.016s sys 0m0.004s Если нужны пояснения к коду, приведу. Комменты общие сейчас поставлю.
ps редактор подсветки не подружился с первой кавычкой(заменил на ") -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Гость |
8.03.2011 11:21
Сообщение
#5
|
Гость |
> 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), но невозможно заставить компилятор Борланда сделать это по-простому. |
volvo |
8.03.2011 11:35
Сообщение
#6
|
Гость |
Кстати, Андрей, в твоем конкретном случае (при умножении на 1111), ты делаешь 4 раза одну и ту же работу, вот тут:
Цитата for (int i = b_size - 1; i >= 0; i-- ) Цитата И в процессоре есть готовая операция, которая сразу получает (a+b) mod 2^32 и (a+b) div 2^32. Как называется? |
-TarasBer- |
8.03.2011 11:44
Сообщение
#7
|
Гость |
> Как называется?
Там опечатка, не +, а * надо. |
klem4 |
9.03.2011 22:52
Сообщение
#8
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Спасибо за советы, volvo - хорошее замечание, воспользуюсь. Но видимо без перевода в СС с большим основанием никак сильно не ускорить. Хотя тут придется реализовывать ф-ю деления большого на большое, для перевода большого в новую СС, попробую на днях.
Сообщение отредактировано: klem4 - 9.03.2011 22:53 -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
TarasBer |
10.03.2011 11:19
Сообщение
#9
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
> Хотя тут придется реализовывать ф-ю деления большого на большое
Надо только функцию, которая говорит частное и остаток деления a*b на 1000000000 Функция из 3 строчек на асме. Для Д7 это выглядит так:
(Можно и через int64 написать, но это тормозить будет). Ещё можно её модифицировать, чтобы она сразу для a*b+c говорила, только не забудь про случай переноса при сложении. Сообщение отредактировано: TarasBer - 10.03.2011 11:21 -------------------- |
klem4 |
10.03.2011 18:13
Сообщение
#10
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Дык не получится так просто, в cardinal ты число из 5000 цифр не запишешь я думаю.
-------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
-TarasBer- |
10.03.2011 19:06
Сообщение
#11
|
Гость |
Это просто для замены
Код int value = bonus + a[i] * n; if ( value >= 10 ) { bonus = (int)(value / 10); value %= 10; } На Код (value, bonus) = MulDiv(a[i], n); Не надо основание системы счисления менять на 10^500, это для 1000000000. А функция деления длинного на длинное тебе не нужна, ты ж не собрался, надеюсь, основание длинным делать. Число храни как массив cardinal (или u32 или uint32, или что там), каждый элемент от 0 до 999999999. Ну просто чтобы было проще выводить результат. Иначе бы можно было бы тупо взять в качестве основания 2^32 и не париться. Ещё такой момент - то, что результат возвращается на стеке, а не в регистрах, тоже не очень хорошо. Было бы хорошо, если было можно своё соглашение о вызове описать, но я хз, как в С++ с этим. |
klem4 |
14.03.2011 21:50
Сообщение
#12
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Большое спасибо за подсказки, все получилось, использовал хранение в СС с основанием 10^8. Задача собственно заключалась в следующем: дано число, являющееся факториалом N, где 1 <= N <= 2000. Определить надо N.
-------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Текстовая версия | 31.10.2024 15:16 |