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

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

Восстановить пароль Регистрация
 
Gelon
0 / 0 / 0
Регистрация: 04.10.2009
Сообщений: 6
28.04.2011, 03:27     A * B = C Варианты реализации #1
Имеем три числа A В С. Числа большие (допустим 1024 бита, не существенно). Нужно выполнить умножения A * B = С. Разрядность результата в этом случае вдвое больше - 2048 бит. Старшие 1024 биты записываем в С, младшие нас не интересуют. (умножение с фиксированной длиной мантиссы без сохранения порядка)

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

Желаемая разрядность операндов - 64 бита, longint
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Евгений М.
1033 / 974 / 53
Регистрация: 28.02.2010
Сообщений: 2,817
Завершенные тесты: 2
28.04.2011, 04:22     A * B = C Варианты реализации #2
Слышал об этом
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
28.04.2011, 04:24     A * B = C Варианты реализации #3
1. Гуглим "Быстрое преобразование Фурье"
2. ???????
3. PROFIT
Gelon
0 / 0 / 0
Регистрация: 04.10.2009
Сообщений: 6
16.05.2011, 00:45  [ТС]     A * B = C Варианты реализации #4
Спасибо Евгений М. silent_1991 за советы. Насколько понимаю, silent_1991 предлагает метод Шёнхаге - Штрассена, в котором используется преобразование Фурье, но выигрыш при его использовании наблюдается только если разрядность больше, чем 2 ^ 2 ^ 15 - 2 ^ 2 ^ 17, а при меньшей - хорошо работает предложенный Евгений М. метод Карацубы, хотя не до конца понятно, возможно ли его использование для нахождения не полного, а частичного решения (старшей части результата) ?

На счет X ^ 2 в википедии говорится:
Отметим, что представленный выше первый способ умножения можно трактовать как алгоритм вычисления с точностью до n знаков функции y = x^2 в некоторой точке x = x1.
Но это, насколько понимаю, только для квадрата ....
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
16.05.2011, 01:24     A * B = C Варианты реализации #5
Gelon, БПФ и так выигрыш даёт, просто на не слишком длинных числах он фактически совпадает с выигрышем от Карацубы, поэтому в конечном итоге разницы нет.
Yandex
Объявления
16.05.2011, 01:24     A * B = C Варианты реализации
Ответ Создать тему
Опции темы

Текущее время: 03:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru