Karatsuba Algorithm
A divide-and-conquer multiplication method that replaces four half-size products with three, yielding roughly O(n^1.585) complexity.
Karatsuba's asymptotic advantage does not guarantee a win for small integers. The reduction to three recursive multiplications introduces extra additions, subtractions, carry handling, and temporary storage.
Crossover Threshold
Big-integer libraries normally switch from schoolbook multiplication to Karatsuba only above an implementation-specific operand size. The threshold depends on CPU microarchitecture, limb width, allocation strategy, and whether higher-level Toom-Cook or FFT-based methods are also available.
Useful benchmarks therefore include temporary allocation and copy behavior, not only operand bit length.
Source
- https://www.mathnet.ru/eng/dan26729