Быстрое умножение длинных чисел. |
Быстрое умножение длинных чисел. |
klem4 |
Сообщение
#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 |
Сообщение
#2
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
> Хотя тут придется реализовывать ф-ю деления большого на большое
Надо только функцию, которая говорит частное и остаток деления a*b на 1000000000 Функция из 3 строчек на асме. Для Д7 это выглядит так:
(Можно и через int64 написать, но это тормозить будет). Ещё можно её модифицировать, чтобы она сразу для a*b+c говорила, только не забудь про случай переноса при сложении. Сообщение отредактировано: TarasBer - -------------------- |
Текстовая версия | 20.04.2024 7:25 |