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

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

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

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

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

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

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

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

Задано 4 матрицы. Провести сложение, умножение, умножение на число - C++
Задано 4 матрицы A,B,C,D размером 4х4.Вычеслить такие матрицы: F,G,T. G=3/4 A+B F=B*(2D) T=c/5

Класс Квадратная матрица. Методы: умножение на матрицу, умножение на константу, вывод элементов матрицы на дисплей - C++
Задание: Класс «Квадратная матрица». Методы: умножение на матрицу, умножение на константу, вывод элементов матрицы на дисплей. Нужно...

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
abit
264 / 262 / 33
Регистрация: 03.02.2013
Сообщений: 730
16.04.2013, 03:01 #2
в памяти всплывает сразу три метода...
один вопрос... вам нужно перемножать большие числа, два приблизительно одинаковых по разрядности или просто небольшие, но быстро?

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

Добавлено через 3 минуты
нужно перемножать два числа порядка 1500 бит
0
abit
264 / 262 / 33
Регистрация: 03.02.2013
Сообщений: 730
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
0
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
16.04.2013, 04:05  [ТС] #5
Я сделал в столбик по 32 бита. А можно я выложу тут алгоритм (который я вскоре напишу), а Вы посмотрите что в нем не так?
0
AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 533
16.04.2013, 11:04 #6
Карацуба и Фурье
Удачи.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.04.2013, 11:04
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
16.04.2013, 11:04
Ответ Создать тему
Опции темы

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