A * B = C Варианты реализации

@Gelon · Регистрация: 04.10.2009

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

Имеем три числа A В С. Числа большие (допустим 1024 бита, не существенно). Нужно выполнить умножения A * B = С. Разрядность результата в этом случае вдвое больше - 2048 бит. Старшие 1024 биты записываем в С, младшие нас не интересуют. (умножение с фиксированной длиной мантиссы без сохранения порядка)

Предложите алгоритм для реализации такого вычисления, по крайней мере более эффективный, чем умножения в столбик

Желаемая разрядность операндов - 64 бита, longint

Евгений М. · 28.04.2011, 04:22

Слышал об этом

silent_1991 · 28.04.2011, 04:24

1. Гуглим "Быстрое преобразование Фурье"
2. ???????
3. PROFIT

@Gelon · 16.05.2011, 00:45 **[ТС]**

Спасибо Евгений М. silent_1991 за советы. Насколько понимаю, silent_1991 предлагает метод Шёнхаге - Штрассена, в котором используется преобразование Фурье, но выигрыш при его использовании наблюдается только если разрядность больше, чем 2 ^ 2 ^ 15 - 2 ^ 2 ^ 17, а при меньшей - хорошо работает предложенный Евгений М. метод Карацубы, хотя не до конца понятно, возможно ли его использование для нахождения не полного, а частичного решения (старшей части результата) ?

На счет X ^ 2 в википедии говорится:
Отметим, что представленный выше первый способ умножения можно трактовать как алгоритм вычисления с точностью до n знаков функции y = x^2 в некоторой точке x = x1.
Но это, насколько понимаю, только для квадрата ....

silent_1991 · 16.05.2011, 01:24

Gelon, БПФ и так выигрыш даёт, просто на не слишком длинных числах он фактически совпадает с выигрышем от Карацубы, поэтому в конечном итоге разницы нет.

Новые блоги и статьи Все статьи Все блоги /
Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025

@Gelon 0 / 0 / 0 Регистрация: 04.10.2009 Сообщений: 6

	A * B = C Варианты реализации 28.04.2011, 03:27. Показов 1285. Ответов 4 Метки нет (Все метки) Имеем три числа A В С. Числа большие (допустим 1024 бита, не существенно). Нужно выполнить умножения A * B = С. Разрядность результата в этом случае вдвое больше - 2048 бит. Старшие 1024 биты записываем в С, младшие нас не интересуют. (умножение с фиксированной длиной мантиссы без сохранения порядка) Предложите алгоритм для реализации такого вычисления, по крайней мере более эффективный, чем умножения в столбик Желаемая разрядность операндов - 64 бита, longint 0

Евгений М. 1080 / 1007 / 107 Регистрация: 28.02.2010 Сообщений: 2,889
	28.04.2011, 04:22
	Слышал об этом 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	28.04.2011, 04:24
	1. Гуглим "Быстрое преобразование Фурье" 2. ??????? 3. PROFIT 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	16.05.2011, 01:24
	Gelon, БПФ и так выигрыш даёт, просто на не слишком длинных числах он фактически совпадает с выигрышем от Карацубы, поэтому в конечном итоге разницы нет. 0