Очень быстрый алгоритм умножения длинных чисел, куда копать?
Здравствуйте.
Требуется очень быстро и много раз умножать очень длинное число, пример:
длинное число (более двух миллионов цифр у числа) умножать на случайное число в ограниченном диапазоне 2^8. (кол-во операций более 40 миллионов).
Погуглив данную инфу, я пока нашел алгоритмы:
Быстрое умножение: метод Карацубы
Быстрое умножение: метод Тоома-Кука
Быстрое умножение: метод Шснхаге-Штрассена
Дискретное преобразование Фурье
Алгоритм быстрого преобразования Фурье
Алгоритм Шёнхаге-Штрассена умножения целых чисел
Но, к сожалению, более детально в них не разбирался.
Так же я смотрел в сторону вычисления на GPU на Cuda, но, к сожалению, я думаю, что мне не подойдет данная технология, т.к. я не знаю и не нашел пока на сколько быстро работает умножение на длинных числах.
Уточните, пожалуйста, куда копать по данной теме?
Или может кто-то подкинет формулу или реализацию на каком-нибудь ЯП данный алгоритм.
Алексей Тен, Для начало хочется найти на текущий момент наиболее быстрый алгоритм, что бы в дальнейшем при разработке нового алгоритма можно было сравнивать их скорость работы.
Для начало хочется найти на текущий момент наиболее быстрый алгоритм, что бы в дальнейшем при разработке нового алгоритма можно было сравнивать их скорость работы.
DVirt, моё так сказать научное мнение по данной теме состоит в том, что овладение попугаем некоторым словарым запасом не делает его (попугая, не запас) содержательным собеседником.
Сорвём покровы: попугай - это ты. Минимального погружения в тему достаточно, чтобы понять - никаких особых быстрых алгоритмов перемножения длинного числа на короткое не существует. Закрывай лавочку.
Зря в сторону CUDA не копаете, умножение и сложение - это конёк GPU.
Банально, переводим супер длинное число в массив, умножаем массив на 1-байтовое число, учитываем сдвиги. Даже ядра свои писать не надо, всё нужное в библиотеке cublas есть. Результат по скорости очень удивит.
При умножении на маленькое число всякие хитрые алгоритмы типа преобразования Фурье или Карацубы лаже медленнее тупого умножения в лоб: Просто проходитесь по большому числу от младших разрядов к старшим, умножете на маленький множитель, прибавляете перенос. Потом берете остаток от деления на базу (если множитель маленький, то быстрее будет просто вычесть несколько раз в цикле вместо модуля), а результат целочисленного деления записываете в перенос.
При умножении числа из кучи миллионнных разрядов важными окажутся только первые старшие.
Остальные младше - погрешность.
Чем правее, тем бесполезнее их вклад в результат - шум вычислительный!
Какая точность при умножении?
Разве не достаточно следовать этому правилу?
Умножим, к примеру, число, состоящее из следующих цифр: 100000000000000 и еще любые (шум), всего миллион цифр:
например: 100000000000000.....0000000000000000
ИЛИ любое другое число , с разницей в цифрах справа, например: 100000000000000.....9999999999999999
Умножим любое из них например на 5, результат умножения на 5 будет: 500000000000000.....шуммммммммммм
#
Спасибо за замечание. Дык да, если в криптографии, но про автора я подумал, что раз совсем не упоминает для чего ему "умножение", то кто ж его знает, что ему надо. Но он упоминает такие алгоритмы, как Фурье преобразование. В радиотехнике при цифровой обработке сигналов делал оптимизацию умножений/корней на асме в далекие 90ые. И там 100% точность была не нужна. Для криптографии не знаю, приемлим ли Фурье вообще в принципе..
