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

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

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

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

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

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

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

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

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

Войти через центр авторизации
Похожие вопросы