Karatsuba algorithm: Difference between revisions

Revision as of 23:19, 18 August 2023

Revision as of 19:24, 19 August 2023

Line 115:

for some constants ''c'' and ''d''. For this [[recurrence relation]], the [[master theorem (analysis of algorithms)|master theorem for divide-and-conquer recurrences]] gives the [[big O notation|asymptotic]] bound <math>T(n) = \Theta(n^{\log_2 3})\,\!</math>.

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's method is usually faster when the multiplicands are longer than 320–640 bits.<ref>{{Cite web|url=http://www.cburch.com/proj/karat/comment1.html|title=Karatsuba multiplication|website=www.cburch.com}}</ref>

==Implementation==