C/C++ - программа перемножения длинных чисел на С++

[Lyanni]

Помогите написать программу реализующую алгоритмы (умножение «столбиком», метод Карацубы, БПФ) перемножения длинных чисел в зависимости от параметров исходных данных (чисел) на С++

Если можно, с пояснениями

[lxa85]

Lyanni, как обычно, с вас черновики решения, с нас поправки и наводящие вопросы.

БПФ - быстрое преобразование Фурье? С

Википедией

сверялись?

умножение столбиком - это как должно выглядеть?

[Lyanni]

Алгоритмумножения «в столбик» длинных чисел С = А*В длины n цифр

1) C := 0; (достаточно обнулить n младших цифр)

2) для i = 0 … n-1 выполнить шаги 3-8;

3) d :=0;

4) для j = 0 … n-1 выполнить шаги 3-5;

5) T :=Ci+j + Ai*Bi +d;

6) Ci+j : = LODIGIT(T);

7) d := HIDIGIT(T);

8) Ci+n := d;

9) конец.



БПф - быстрое преобразование фурье

Тогда функция для перемножения двух многочленов будет выглядеть следующим образом:

void multiply (const vector & a, const vector & b, vector & res) {

vector fa (a.begin(), a.end()), fb (b.begin(), b.end());

size_t n = 1;

while (n < max (a.size(), b.size())) n

[Hilaly]

например так:



Код: