1

Тема: Алгоритм Карацубы

Я реализовал алгоритм Карацубы и хотел сдать задачу, где нужно просто умножать большие числа:
http://www.spoj.pl/problems/MUL/cstart=10
Но неожиданно для себя получил ТЛЕ. Сделал оптимизацию для обычного умножения, чтобы не брать каждый раз остаток,  а в конце один раз пересчитывать и переносить по разрядам. Это увеличило скорость где-то в 2 раза, но этого всё ещё не достаточно. Обычное умножение делаю, если длина числа меньше 70, я уже много перепробовал, это приблизительно самая оптимальная константа для этих ограничений. Числа, конечно же, храню по основанию 10^9. Лично я думаю, что я либо сильно накосячил где-то(не знаю где), либо много времени тратится на выделение памяти при рекурсивных вызовах, так как там передаётся 2 массива по 3000 инт64 и ещё 7 массивов локальных.
У кого-то были такие проблемы с этим алгоритмом?Если да, то посоветуйте, пожалуйста, как его оптимизировать. И вообще эффективен ли он на практике?

2

Re: Алгоритм Карацубы

Я возненавидел алгоритм Карацубы после того, как на втором раунде Facebook Hacker Cup первая задача отработала за 6:20 при таймлимите в 6 минут. Фурье тогда проходил на ура. Теперь по возможности пишу только Фурье.

3

Re: Алгоритм Карацубы

Жаль...