Программа перемножения длинных чисел в C++

[Lyanni]

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

[Dissident]

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

[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) конец.
Алгоритм карацубы заключается в разбиении исходных чисел A и B на две части.
При этом получим
A=A_1*b^k+A_0,B=B_1*b^k+B_0,
где k=max(m,n)/2, m - число цифр по основанию b в числе A, а n - число цифр по основанию b в числе B.
Теперь произведение C=A*B можно вычислить с помощью лишь трех умножений целых чисел длиной k или меньше плюс несколько сдвигов и сложений, используя формулу
C=A*B=(A_1*B_1 )*b^(2*k)+(A_1*B_0+A_0*B_1 )*b^k+(A_0*B_0),
где A_1*B_0+A_0*B_1=(A_1+A_0 )*(B_1*B_0 )-A_1*B_1-A_0*B_0.

[Lyanni]

Алгоритм БПФ для перемножения двух многочленов будет выглядеть следующим образом:
void multiply (const vector<int> & a, const vector<int> & b, vector<int> & res) {
vector<base> fa (a.begin(), a.end()), fb (b.begin(), b.end());
size_t n = 1;
while (n < max (a.size(), b.size())) n <<= 1;
n <<= 1;
fa.resize (n), fb.resize (n);

fft (fa, false), fft (fb, false);
for (size_t i=0; i<n; ++i)
fa[i] *= fb[i];
fft (fa, true);

res.resize (n);
for (size_t i=0; i<n; ++i)
res[i] = int (fa[i].real() + 0.5);
}
функция для перемножения двух длинных чисел практически ничем не отличается от функции для перемножения многочленов. Единственная особенность — что после выполнения умножения чисел как многочлены их следует нормализовать, т.е. выполнить все переносы разрядов:
int carry = 0;
for (size_t i=0; i<n; ++i) {
res[i] += carry;
carry = res[i] / 10;
res[i] %= 10;
}

[Lyanni]

Я без понятия как это скомпоновать....(