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

@vlad_light · Регистрация: 24.09.2012

Студворк — интернет-сервис помощи студентам

Нужно написать алгоритм для быстрого умножения 2-ух 32-битных чисел. Кто подскажет быстрый алгоритм? (как в openssl, только я там разобраться не могу

)

@abit · 16.04.2013, 03:01

в памяти всплывает сразу три метода...
один вопрос... вам нужно перемножать большие числа, два приблизительно одинаковых по разрядности или просто небольшие, но быстро?

в общем для быстрого перемножения двух чисел 2^32 хватит разобрать инструкции FPU или СUDA... быстрее сделать не выйдет... если разрядность всё же выше 32-бит - достаточно разобрать два алгоритма - Карацубы и Фюрера... остальное - дело реализации

@vlad_light · 16.04.2013, 03:12 **[ТС]**

для быстрого перемножения двух чисел 2^32 хватит разобрать инструкции FPU или СUDA

Можно ссылки или на пальцах, как это реализовывать? Никогда с таким не сталкивался...

Добавлено через 3 минуты
нужно перемножать два числа порядка 1500 бит

@abit · 16.04.2013, 03:32

Можно ссылки или на пальцах, как это реализовывать? Никогда с таким не сталкивался...

Вы знаете, там всё зависит от конкретики... исходно всё строилось на основе быстродействующих счётчиков, которые принимали флаги переносов, сейчас это конечно куда сложнее ) всё сводится к конкретной постановке задачи -> пре-подготовки чисел для удобного перемножения(наглядный пример быстрое преобразование фурье), самому перемножению и пост-обработке результата... в общем виде это невозможно описать.

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

Добавлено через 3 минуты

нужно перемножать два числа порядка 1500 бит

???
а начинали с 2^32) это только 32 бита...
в общем Карацуба и Фюрер ждут вас ) -
http://urls.by/3l5
http://urls.by/3l6

@vlad_light · 16.04.2013, 04:05 **[ТС]**

Я сделал в столбик по 32 бита. А можно я выложу тут алгоритм (который я вскоре напишу), а Вы посмотрите что в нем не так?

@AnyOne697 · 16.04.2013, 11:04

Карацуба и Фурье
Удачи.

Новые блоги и статьи Все статьи Все блоги /
Перемещение выделенных строк ТЧ из одного документа в другой Maks 30.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .

@vlad_light 5 / 5 / 1 Регистрация: 24.09.2012 Сообщений: 178

	Быстрое умножение 16.04.2013, 02:42. Показов 8229. Ответов 5 Метки нет (Все метки) Нужно написать алгоритм для быстрого умножения 2-ух 32-битных чисел. Кто подскажет быстрый алгоритм? (как в openssl, только я там разобраться не могу) 0

@abit 870 / 529 / 149 Регистрация: 03.02.2013 Сообщений: 1,858
	16.04.2013, 03:01
	в памяти всплывает сразу три метода... один вопрос... вам нужно перемножать большие числа, два приблизительно одинаковых по разрядности или просто небольшие, но быстро? в общем для быстрого перемножения двух чисел 2^32 хватит разобрать инструкции FPU или СUDA... быстрее сделать не выйдет... если разрядность всё же выше 32-бит - достаточно разобрать два алгоритма - Карацубы и Фюрера... остальное - дело реализации 1

@vlad_light 5 / 5 / 1 Регистрация: 24.09.2012 Сообщений: 178
	16.04.2013, 04:05 [ТС]
	Я сделал в столбик по 32 бита. А можно я выложу тут алгоритм (который я вскоре напишу), а Вы посмотрите что в нем не так? 0

@AnyOne697 134 / 106 / 10 Регистрация: 22.05.2010 Сообщений: 533
	16.04.2013, 11:04
	Карацуба и Фурье Удачи. 0