3 ms·
Those have better asymptotics but worse constants.
by jjaredsimpson 8y ago
Those have better asymptotics but worse constants.
- gamegoblin 8y agoSpecifically: It follows that, for sufficiently large n, Karatsuba's algorithm will perform fewer shifts and single-digit additions than longhand multiplication, even though its basic step uses more additions and shifts than the straightforward formula. For small values of n, however, the extra shift and add operations may make it run slower than the longhand method. The point of positive return depends on the computer platform and context. As a rule of thumb, Karatsuba is usually faster when the multiplicands are longer than 320–640 bits. https://en.wikipedia.org/wiki/Karatsuba_algorithm#Efficiency_analysis https://en.wikipedia.org/wiki/Karatsuba_algorithm#Efficiency...