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

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

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

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

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

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

Быстрое умножение длинных чисел. - C++
В общем вопрос стоит так: где можно найти красивый код на агоритм Карацубы. В часности -...

Необходимо написать быстрое рекурсивное умножение многочленов (полиномов). Не преобразование Фурье - C++
Необходимо написать быстрое рекурсивное умножения многочленов (полиномов). Не преобразование Фурье. Многочлен разбивается на две части (от...

Быстрое изучение С++ - C++
Си знаю, C# знаю. На все про все у меня неделя. Что посоветуете? Заранее благодарен.

Быстрое шифрование - C++
Народ добрый , день , такая задача решил делать курсач на тему криптография , вот первым делом буду использовать шифрование быстрым методом...

Быстрое возведение в степень - C++
Хочу реализовать быстрое возведение в степень, но проблема в том что то число которое возводим в степень записано не в какой нибудь базовой...

Быстрое заполнение массива - C++
Вот у меня сейчас незадача. Не получается найти способ "Заполняю один элемент массива, так чтобы, то что заполнил заполнило следующие 10...

Быстрое деление 2х длинных - C++
Предположим у меня есть вектор a и вектор b. Каждый элемент вектора содержит 9 цифр (основание миллиард). Дак вот вопросец, как поделить a...

Быстрое преобразование числа - C++
Здравствуйте уважаемые программисты! Подскажите пожалуйста как быстрее всего получить из положительного числа единицу, а из отрицательного...

Быстрое нахождение суммы - C++
Дано натуральное число 1<=N<=1000000000; как посчитать сумму чисел от 1 до N менее чем за 1 секунду?) понятно что for (int i = 1; i...

Быстрое заполнение памяти - C++
С помощью memset, можно быстро заполнить массив какими-либо значениями, но по одной штуке. А можно ли заполнить текстуру цветом RGB? То...

Быстрое чтение файла - C++
Здраствуйте. Я пишу программу, которая читает файлы порядка от нескольких килобайтов до максимум 3 Мб. Посоветуйте пожалуйста, какие...

Быстрое возведение в степень - C++
Написать функцию быстрого возведения в степень. Функция принимает в качестве параметров y,x и n и возвращает y^x mod y как результат...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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     Быстрое умножение
Ответ Создать тему
Опции темы

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