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

Определение. Алгоритм быстрого умножения длинных чисел: рекурсивно сводит умножение n-значных чисел к трём умножениям (n/2)-значных вместо четырёх, давая сложность O(n^log₂3) ≈ O(n^1.585) вместо наивного O(n²).