Очень быстрый алгоритм умножения длинных чисел, куда копать? Здравствуйте.
Требуется очень быстро и много раз умножать очень длинное число, пример:
длинное число (более двух миллионов цифр у числа) умножать на случайное число в ограниченном диапазоне 2^8. (кол-во операций более 40 миллионов).
Погуглив данную инфу, я пока нашел алгоритмы:
Быстрое умножение: метод Карацубы
Быстрое умножение: метод Тоома-Кука
Быстрое умножение: метод Шснхаге-Штрассена
Дискретное преобразование Фурье
Алгоритм быстрого преобразования Фурье
Алгоритм Шёнхаге-Штрассена умножения целых чисел
Но, к сожалению, более детально в них не разбирался.
Так же я смотрел в сторону вычисления на GPU на Cuda, но, к сожалению, я думаю, что мне не подойдет данная технология, т.к. я не знаю и не нашел пока на сколько быстро работает умножение на длинных числах.
Уточните, пожалуйста, куда копать по данной теме?
Или может кто-то подкинет формулу или реализацию на каком-нибудь ЯП данный алгоритм.
Очень быстрый алгоритм умножения длинных чисел, куда копать? Здравствуйте.
Требуется очень быстро и много раз умножать очень длинное число, пример:
длинное число (более двух миллионов цифр у числа) умножать на случайное число в ограниченном диапазоне 2^8. (кол-во операций более 40 миллионов).
Погуглив данную инфу, я пока нашел алгоритмы:
Быстрое умножение: метод Карацубы
Быстрое умножение: метод Тоома-Кука
Быстрое умножение: метод Шснхаге-Штрассена
Дискретное преобразование Фурье
Алгоритм быстрого преобразования Фурье
Алгоритм Шёнхаге-Штрассена умножения целых чисел
Но, к сожалению, более детально в них не разбирался.
Так же я смотрел в сторону вычисления на GPU на Cuda, но, к сожалению, я думаю, что мне не подойдет данная технология, т.к. я не знаю и не нашел пока на сколько быстро работает умножение на длинных числах.
Уточните, пожалуйста, куда копать по данной теме?
Или может кто-то подкинет формулу или реализацию на каком-нибудь ЯП данный алгоритм.
Требуется очень быстро и много раз умножать очень длинное число, пример:
длинное число (более двух миллионов цифр у числа) умножать на случайное число в ограниченном диапазоне 2^8. (кол-во операций более 40 миллионов).
Погуглив данную инфу, я пока нашел алгоритмы:
Быстрое умножение: метод Карацубы
Быстрое умножение: метод Тоома-Кука
Быстрое умножение: метод Шснхаге-Штрассена
Дискретное преобразование Фурье
Алгоритм быстрого преобразования Фурье
Алгоритм Шёнхаге-Штрассена умножения целых чисел
Но, к сожалению, более детально в них не разбирался.
Так же я смотрел в сторону вычисления на GPU на Cuda, но, к сожалению, я думаю, что мне не подойдет данная технология, т.к. я не знаю и не нашел пока на сколько быстро работает умножение на длинных числах.
Уточните, пожалуйста, куда копать по данной теме?
Или может кто-то подкинет формулу или реализацию на каком-нибудь ЯП данный алгоритм.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для умножения очень длинных чисел существует несколько оптимизированных алгоритмов, которые могут помочь вам ускорить процесс.
Метод Карацубы, метод Тоома-Кука, метод Шёнхаге-Штрассена и дискретное преобразование Фурье - все это хорошие варианты для умножения длинных чисел. Каждый из них имеет свои особенности и может быть оптимальным в зависимости от вашего конкретного случая.
Если вы хотите использовать CUDA для ускорения процесса, вам стоит провести тестирование и сравнить производительность умножения длинных чисел на GPU с производительностью алгоритмов на CPU.
Также, вы можете попробовать поискать библиотеки или реализации этих алгоритмов на вашем любимом языке программирования. Например, в языке Python есть библиотека gmpy2, которая предоставляет эффективные методы для работы с длинной арифметикой.
Исследуйте каждый из алгоритмов более детально, проведите тестирование и выберите оптимальный вариант для ваших задач. Удачи вам!