Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.73
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
#1

Быстрое умножение - C++

16.04.2013, 02:42. Просмотров 2051. Ответов 5
Метки нет (Все метки)

Нужно написать алгоритм для быстрого умножения 2-ух 32-битных чисел. Кто подскажет быстрый алгоритм? (как в openssl, только я там разобраться не могу)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.04.2013, 02:42     Быстрое умножение
Посмотрите здесь:

Быстрое умножение длинных чисел. C++
Быстрое деление 2х длинных C++
Быстрое заполнение массива C++
Быстрое преобразование числа C++
Быстрое изучение С++ C++
Быстрое шифрование C++
Класс Квадратная матрица. Методы: умножение на матрицу, умножение на константу, вывод элементов матрицы на дисплей C++
C++ Задано 4 матрицы. Провести сложение, умножение, умножение на число
C++ Необходимо написать быстрое рекурсивное умножение многочленов (полиномов). Не преобразование Фурье
C++ Быстрое возведение в степень
C++ Быстрое возведение в степень
Быстрое заполнение памяти C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
16.04.2013, 03:01     Быстрое умножение #2
в памяти всплывает сразу три метода...
один вопрос... вам нужно перемножать большие числа, два приблизительно одинаковых по разрядности или просто небольшие, но быстро?

в общем для быстрого перемножения двух чисел 2^32 хватит разобрать инструкции FPU или СUDA... быстрее сделать не выйдет... если разрядность всё же выше 32-бит - достаточно разобрать два алгоритма - Карацубы и Фюрера... остальное - дело реализации
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
16.04.2013, 03:12  [ТС]     Быстрое умножение #3
для быстрого перемножения двух чисел 2^32 хватит разобрать инструкции FPU или СUDA
Можно ссылки или на пальцах, как это реализовывать? Никогда с таким не сталкивался...

Добавлено через 3 минуты
нужно перемножать два числа порядка 1500 бит
abit
260 / 259 / 33
Регистрация: 03.02.2013
Сообщений: 709
16.04.2013, 03:32     Быстрое умножение #4
Можно ссылки или на пальцах, как это реализовывать? Никогда с таким не сталкивался...
Вы знаете, там всё зависит от конкретики... исходно всё строилось на основе быстродействующих счётчиков, которые принимали флаги переносов, сейчас это конечно куда сложнее ) всё сводится к конкретной постановке задачи -> пре-подготовки чисел для удобного перемножения(наглядный пример быстрое преобразование фурье), самому перемножению и пост-обработке результата... в общем виде это невозможно описать.

если так хотите вникнуть в суть начните с корня - http://urls.by/3l3
но проще будет - если вы сформулируете точнее что и как перемножать, потому что в общем случае эту задачу в С/C++ не решить, только в языках типа haskell возможно благодаря полноценной бетта-редукции

Добавлено через 3 минуты
нужно перемножать два числа порядка 1500 бит
???
а начинали с 2^32) это только 32 бита...
в общем Карацуба и Фюрер ждут вас ) -
http://urls.by/3l5
http://urls.by/3l6
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
16.04.2013, 04:05  [ТС]     Быстрое умножение #5
Я сделал в столбик по 32 бита. А можно я выложу тут алгоритм (который я вскоре напишу), а Вы посмотрите что в нем не так?
AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 533
16.04.2013, 11:04     Быстрое умножение #6
Карацуба и Фурье
Удачи.
Yandex
Объявления
16.04.2013, 11:04     Быстрое умножение
Ответ Создать тему
Опции темы

Текущее время: 20:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru