Помогите разобраться с этим алгоритмом. В гугл просьба не слать, был не помог. Только формулы... Примеров нет. Задача такова, что есть очень большое число порядка 2 тыс разрядов. Надо перемножать на другое число. Для решения этой задачи я выбрал алгортм Быстрого преобразования Фурье. К примеру надо перемножить вектор А - 6 разрядов(обозначим m) и вектор B - 5 разрядов(обозначим n). Для начала надо посчитать коэфициенты С. Сколько будит их? (max(m,n))  ?

Что за бред?

многие, казалось бы, далёкие области математики иногда соприкасаются в неожиданных местах ;)

умножение длинных чисел, если мне не изменяет память, сводится к свёртке, а БПФ может помочь вычислить её быстрее

Добавлено @ 10:37

тут нужно учесть, что БПФ рассчитано на работу с векторами, длина которых - степень двойки
(есть, правда, модификации, где вектор делится не на два, а на большее количество подпоследовательностей, но там, по-моему, всё менее оптимально и сложно)
так что сначала, думаю, нужно округлить оба вектора до степени двойки вверх
(для длинных чисел это делается вполне естественным образом - дополнение нулями)

Это сообщение отредактировал(а) maxim1000 - 29.4.2008, 10:37

Размер C будет равен max(N,M), округленному вверх до степени двойки, и ещё умножить на 2.
Если, конечно, реализация алгоритма именно такова, что приводит размеры к степеням двойки (а другая реализация, как уже было сказано, менее популярна).

И что будет быстрее, чем просто в столбик?

Да. На кывте говорится о такой оценке:



Это сообщение отредактировал(а) Mayk - 30.4.2008, 05:22

В Кормене описывается алгоритм умножения с использованием БПФ с асимптотикой N log N (авторы алгоритма там не приводятся, возможно, что алгоритм "народный"  ).

Кстати, у меня на сайте есть (http://maximal.hocomua.ru/fft_multiply.htm) описание этого алгоритма, (собсно перепечатанное из Кормена  ) и работающий код. Так что желающие могут потестировать и сравнить скорость. Скажу, что например умножение двух 100-тысячных чисел он выполняет примерно за секунду (чего ни столбиком, ни, я думаю, даже Карацубой не добиться).

Это сообщение отредактировал(а) maxdiver - 30.4.2008, 08:53

для достаточно длинных чисел (точного или даже приблизительного порога не знаю - надо на практике смотреть)
БПФ всё-таки значительно сложнее свёртки в смысле структуры алгоритма и разнообразных вычислений
и для маленьких длин, скорее всего, будет неэффективно
но вот с ростом длины рост сложности у него меньше

Так там смысл в том, что каждый разряд числа считается за элемент вектора, и таким образом два длинных числа превращаются в два многомерных вектора, которые потом надо свернуть?

да


кстати, нашёл один pdf-ник по этой теме:
http://edu.krasu.ru/file.php/6/articles/LONG.pdf

maxim1000, этот pdf был взят с сайта algolist. Собственно говоря, оттуда я и узнал об этом алгоритме, но т.к. в математике я слабовато, то решил создать тему, чтоб задавать вопросы. Хочу сам написать реализацию, хотя в том же pdf она уже и приведена.
Кстати о скорости выполнения она равна Log N и судя по графику, приведенному в том же pdf, алгоритм оптимально использовать при длине числа -  от 100 до 120 и от 180 разрядов. 
Ну а сейчас спатки, завтра начнем разбираться далее


Это сообщение отредактировал(а) T0ohtik - 30.4.2008, 22:00

Что-то я не пойму. В чем заключается этот алгоритм. Наши числа хранятся в массиве А и В - т.е. получается, они представлены как многочлен.  Далее мы находим коэффициенты свертки, с. Которые равны сумме произведений всех элементов, индексы которых в сумме равно i. И эти коэффициенты будут произведением числа А на В. Правильно? Или я в чем - то ошибся.

да, только там есть ещё один нюанс:
после свёртки некоторые коэффициенты могут оказаться больше максимальной цифры
например 5*100+12*10+3 для десятичной
так что нужно будет пробежаться и поперекидывать лишние части в старшие разряды:
(5+1)*100+2*10+3

Т.е. другими словами алгоритм умножения десятичных чиел заключается в следующем:
1. выбираем максимальную длину из 2х векторов А и В. Количество коэффициентов свертки С у нас будит равно длине максимального вектора.
2. Дополняем меньший из векторов 0 до размеров большего из векторов.
3. Производим свертку векторов. 
4. После свертки проверяем вектор и в случаи переполнения делаем переносы.

Это и все? Не ясен момент с округлением  векторов до степени двойки вверх. Зачем? Обязательно?

БПФ, как его обычно строят, состоит в том, чтобы:
1. разбить последовательность на две подпоследовательности одинаковой длины
2. посчитать спектры для них
3. посчитать спектр полной последовательности из двух спектров подпоследовательностей
одинаковость длин подпоследовательностей означает, что длина исходной последовательности должна быть чётной, на каждом уровне длины отличаются в два раза
т.к. на самом низком уровне у нас последовательности из одного элемента, то длина исходной должна быть степенью двойки

Добавлено @ 19:25
в принципе, если на каком-то шаге у нас получилась последовательность нечётной длины, то можно посчитать спектр обычным способом - суммой произведений
т.е. если у нас длина 2*2*2*2*3, может, и можно обойтись без дополнения до степени двойки
но вот если 2*2*12345, удар по производительности может быть большой
а реализовывать отличение первых случаев от вторых, ИМХО, не будет стоить выгод

Это сообщение отредактировал(а) maxim1000 - 2.5.2008, 19:25