Тема: Карацуба
Хотелось бы узнать от тех кто писал его что нибудь дельное) ну и конечно же хотелось бы увидеть его на e-maxx в algo))
Re: Карацуба
Мне его реализовывать не приходилось, но вообще суть такова: для перемножения двух чисел длины N обычно требуется N^2 операций.
Если разделить оба числа на две группы цифр по N/2, то, перемножая каждую половинку с каждой и прибавляя их к ответу (соответственно сдвигая), мы тоже можем найти результат, но время работы T(N) будет удовлетворять уравнению:
T(N) = 4 T(N/2) + O(N),
решением которого является T(N) = O(N^2), т.е. это пока плохой алгоритм.
Но Карацуба заметил, что можно не умножать каждую половинку с каждой, а обойтись 3 умножениями и несколькими сложениями/вычитаниями, и асимптотика уже будет удовлетворять уравнению:
T(N) = 3 T(N/2) + O(N),
Если решать это уравнение неформально, то от какого-то N оно будет иметь log_2 N уровней рекурсии, на каждом из которых время будет умножаться на 3, и в итоге получится T(N) = 3 ^ log_2 N = 2 ^ (log_2 3) ^ (log_2 N) = N ^ (log_2 3) = N ^ 1.58...
Т.е. это вроде бы и существенно лучше тривиального алгоритма за квадрат, но и заметно хуже времени O (N log N), которого позволяет добиться алгоритм Шенхаге-Штрассена (дискретное преобразование Фурье). Поэтому как-то у меня никогда не возникало желания реализовывать Карацубу.
В то же время, при наличии в языке встроенных средств длинной арифметики, реализация этого алгоритма довольно проста, так что у него алгоритма есть свой плюс. На C++ же для реализации придётся реализовывать различные низкоуровневые операции длинной арифметики.
Постараюсь добавить этот алгоритм в следующий апдейт algo 
Re: Карацуба
Вспомнил, не так давно в одном из TopCoder SRM'ов как раз нужно было перемножать два длинных числа, и решение Petr'а как раз основывалось на алгоритме Карацубы.
Вот его реализация:
private int[] fastmul(int[] a, int[] b)
{
if (allZero(a) || allZero(b))
{
return new int[a.Length + b.Length];
}
if (a.Length < 103)
{
return slowmul(a, b);
}
else
{
int k = a.Length / 2;
int[] p = new int[k];
int[] q = new int[k];
int[] r = new int[k];
int[] s = new int[k];
Array.Copy(a, 0, p, 0, k);
Array.Copy(a, k, q, 0, k);
Array.Copy(b, 0, r, 0, k);
Array.Copy(b, k, s, 0, k);
int[] pr = fastmul(p, r);
int[] qs = fastmul(q, s);
int[] pplusq = new int[k];
for (int i = 0; i < k; ++i)
pplusq[i] = p[i] + q[i];
int[] rpluss = new int[k];
for (int i = 0; i < k; ++i)
rpluss[i] = r[i] + s[i];
int[] tmp = fastmul(pplusq, rpluss);
for (int i = 0; i < 2 * k; ++i)
tmp[i] -= pr[i] + qs[i];
int[] res = new int[4 * k];
for (int i = 0; i < 2 * k; ++i)
res[i] += pr[i];
for (int i = 0; i < 2 * k; ++i)
res[i + k] += tmp[i];
for (int i = 0; i < 2 * k; ++i)
res[i + 2 * k] += qs[i];
return res;
}
}
private bool allZero(int[] a)
{
for (int i = 0; i < a.Length; ++i)
if (a[i] != 0)
return false;
return true;
}
private int[] slowmul(int[] a, int[] b)
{
int[] c = new int[a.Length + b.Length];
for (int i = 0; i < a.Length; ++i)
if (a[i] != 0)
for (int j = 0; j < b.Length; j += 1)
{
if (b[j] != 0)
c[i + j] += a[i] * b[j];
}
return c;
} Как видно, вполне можно обойтись и без стандартной длинной арифметики и получить при этом довольно короткий код