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

@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

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .

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

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

@abit 870 / 529 / 149 Регистрация: 03.02.2013 Сообщений: 1,847
	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