Блог Ромки

Сегодня большая часть дня была посвящена изучению свойств умножения.
Было выяснено следующее, существует 3 наиболее распрастраненных алгоритма:

1) Стандартное школьное умножение (O(N^2))
2) Aлгоритм Каратсубы базирующийся на рекурсии (O(N^1.585))
3) Быстрый Алгоритм Фурье (Fast Fourie Transform) (O(N*log(N)))

Чем больше числа, тем более эффективнее нижние алгоритмы. Реализовал второй, но все равно задачка не решается. =) Тратится 15 секунд, а нужно за 3 … В данный момент въезжаю в третий алгоритм.