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

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

Войти
Регистрация
Восстановить пароль
 
Gelon
0 / 0 / 0
Регистрация: 04.10.2009
Сообщений: 6
#1

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

28.04.2011, 03:27. Просмотров 719. Ответов 4
Метки нет (Все метки)

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

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

Желаемая разрядность операндов - 64 бита, longint
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.04.2011, 03:27     A * B = C Варианты реализации
Посмотрите здесь:
Различные варианты реализации сценариев приложения C++
Отделение интерфейса от реализации класса: компиляция кода реализации C++
C++ Варианты заданий:
C++ есть ли варианты?
Варианты сортировок C++
варианты развитися с++ C++
C++ Itoa варианты
Варианты перевода из 10 СС в 2-ую C++
Варианты использования c++ C++
C++ Варианты обхода графа
C++ Варианты ответов (тест)
Варианты организации файлового В/В в C++ C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Евгений М.
1035 / 976 / 54
Регистрация: 28.02.2010
Сообщений: 2,823
Завершенные тесты: 2
28.04.2011, 04:22     A * B = C Варианты реализации #2
Слышал об этом
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 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
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
16.05.2011, 01:24     A * B = C Варианты реализации #5
Gelon, БПФ и так выигрыш даёт, просто на не слишком длинных числах он фактически совпадает с выигрышем от Карацубы, поэтому в конечном итоге разницы нет.
Yandex
Объявления
16.05.2011, 01:24     A * B = C Варианты реализации
Ответ Создать тему
Опции темы

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