Очень быстрый алгоритм умножения длинных чисел, куда копать?

Здравствуйте.

Требуется очень быстро и много раз умножать очень длинное число, пример:
длинное число (более двух миллионов цифр у числа) умножать на случайное число в ограниченном диапазоне 2^8. (кол-во операций более 40 миллионов).

Погуглив данную инфу, я пока нашел алгоритмы:
Быстрое умножение: метод Карацубы
Быстрое умножение: метод Тоома-Кука
Быстрое умножение: метод Шснхаге-Штрассена
Дискретное преобразование Фурье
Алгоритм быстрого преобразования Фурье
Алгоритм Шёнхаге-Штрассена умножения целых чисел

Но, к сожалению, более детально в них не разбирался.
Так же я смотрел в сторону вычисления на GPU на Cuda, но, к сожалению, я думаю, что мне не подойдет данная технология, т.к. я не знаю и не нашел пока на сколько быстро работает умножение на длинных числах.

Уточните, пожалуйста, куда копать по данной теме?
Или может кто-то подкинет формулу или реализацию на каком-нибудь ЯП данный алгоритм.
  • Вопрос задан
  • 681 просмотр
Решения вопроса 2
@tumbler
бекенд-разработчик на python
Зря в сторону CUDA не копаете, умножение и сложение - это конёк GPU.
Банально, переводим супер длинное число в массив, умножаем массив на 1-байтовое число, учитываем сдвиги. Даже ядра свои писать не надо, всё нужное в библиотеке cublas есть. Результат по скорости очень удивит.
Ответ написан
wataru
@wataru
При умножении на маленькое число всякие хитрые алгоритмы типа преобразования Фурье или Карацубы лаже медленнее тупого умножения в лоб: Просто проходитесь по большому числу от младших разрядов к старшим, умножете на маленький множитель, прибавляете перенос. Потом берете остаток от деления на базу (если множитель маленький, то быстрее будет просто вычесть несколько раз в цикле вместо модуля), а результат целочисленного деления записываете в перенос.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@AndrBell
работаю
При умножении числа из кучи миллионнных разрядов важными окажутся только первые старшие.
Остальные младше - погрешность.
Чем правее, тем бесполезнее их вклад в результат - шум вычислительный!
Какая точность при умножении?
Разве не достаточно следовать этому правилу?

Умножим, к примеру, число, состоящее из следующих цифр:
100000000000000 и еще любые (шум), всего миллион цифр:
например:
100000000000000.....0000000000000000
ИЛИ любое другое число , с разницей в цифрах справа, например:
100000000000000.....9999999999999999
Умножим любое из них например на 5, результат умножения на 5 будет:
500000000000000.....шуммммммммммм

Быстро?
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
ИНКАРТ Санкт-Петербург
от 40 000 руб.
Poteha Labs Москва
от 120 000 до 200 000 руб.
21 марта 2019, в 00:19
5000 руб./за проект
20 марта 2019, в 20:02
1000 руб./за проект