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

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

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

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

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

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

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

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

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

Войти через центр авторизации
Похожие вопросы
АО «НИИМЭ» Зеленоград
от 100 000 до 170 000 руб.
Удобные решения Екатеринбург
от 100 000 руб.
08 дек. 2019, в 06:49
3000 руб./за проект
08 дек. 2019, в 05:56
2000 руб./за проект
19 нояб. 2019, в 07:57
150000 руб./за проект