Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

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

Желаемая разрядность операндов - 64 бита, longint
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.04.2011, 03:27
Здравствуйте! Я подобрал для вас темы с ответами на вопрос A * B = C Варианты реализации (C++):

Различные варианты реализации сценариев приложения - C++
Здравствуйте, господа! Приглашаю обсудить в этом топике различные варианты реализации сценариев приложения.

Отделение интерфейса от реализации класса: компиляция кода реализации - C++
Доброго времени суток, У меня возникла проблема с отделением интерфейса от реализации класса. Допустим, у меня есть три файла: 1....

варианты развитися с++ - C++
во общем каковы есть варианты для с++? если например один человек писал с форума 1. Легкий: php + MySQL + JavaScript + Apache. На...

Варианты сортировок - C++
Здравствуйте! Вот есть два способа сортировки: #include <iostream> using namespace std; int main () { const int n=20; ...

Варианты использования c++ - C++
Привет всем. Сегодня в училище задали написать калькулятор. Так как я программирую не первый год на c#, проблем с написанием не возникло....

Itoa варианты - C++
НА этапе компиляции ошибка в строке itoa() Выдает что то типа: Ошибка 1 error C4996: 'itoa': The POSIX name for this item is...

4
Евгений М.
1036 / 977 / 54
Регистрация: 28.02.2010
Сообщений: 2,829
Завершенные тесты: 2
28.04.2011, 04:22 #2
Слышал об этом
0
silent_1991
Эксперт С++
4986 / 3043 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
28.04.2011, 04:24 #3
1. Гуглим "Быстрое преобразование Фурье"
2. ???????
3. PROFIT
0
Gelon
0 / 0 / 0
Регистрация: 04.10.2009
Сообщений: 6
16.05.2011, 00:45  [ТС] #4
Спасибо Евгений М. silent_1991 за советы. Насколько понимаю, silent_1991 предлагает метод Шёнхаге - Штрассена, в котором используется преобразование Фурье, но выигрыш при его использовании наблюдается только если разрядность больше, чем 2 ^ 2 ^ 15 - 2 ^ 2 ^ 17, а при меньшей - хорошо работает предложенный Евгений М. метод Карацубы, хотя не до конца понятно, возможно ли его использование для нахождения не полного, а частичного решения (старшей части результата) ?

На счет X ^ 2 в википедии говорится:
Отметим, что представленный выше первый способ умножения можно трактовать как алгоритм вычисления с точностью до n знаков функции y = x^2 в некоторой точке x = x1.
Но это, насколько понимаю, только для квадрата ....
0
silent_1991
Эксперт С++
4986 / 3043 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
16.05.2011, 01:24 #5
Gelon, БПФ и так выигрыш даёт, просто на не слишком длинных числах он фактически совпадает с выигрышем от Карацубы, поэтому в конечном итоге разницы нет.
0
16.05.2011, 01:24
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.05.2011, 01:24
Привет! Вот еще темы с ответами:

Варианты заданий: - C++
1. Написать функцию, которая вычисляет Вариант Задание 1 площадь круга S по его радиусу R (S=R2) 2 площадь треугольника S по...

есть ли варианты? - C++
кажется продумал технологию движка, который собираюсь делать но вот как оформить его так, чтобы можно было работать с плагинами своего...

Варианты перевода из 10 СС в 2-ую - C++
у меня есть такой вариант перевода // lab_work_4.cpp: определяет точку входа для консольного приложения. // #include "stdafx.h" ...

Варианты обхода графа - C++
подскажите пожалуйста сколько путей существует для такого графа, чтобы проходить через каждую Добавлено через 44 секунды или...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

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