Karatsuba algorithm: Difference between revisions

Revision as of 12:46, 6 December 2023

Revision as of 12:49, 6 December 2023

Line 11:

(excluding input) if not specified -->

}}

[[File:Karatsuba_multiplication.svg|thumb|300px|Karatsuba multiplication of az+b and cz+d (boxed), and 1234 and 567 with z=100. Magenta arrows denote multiplication, amber denotes addition, silver denotes subtraction and light cyan denotes left shift. (A), (B) and (C) show recursion usedwith z=10 to obtain intermediate values.]]

The '''Karatsuba algorithm''' is a fast [[multiplication algorithm]]. It was discovered by [[Anatoly Karatsuba]] in 1960 and published in 1962.<ref name="kara1962">

{{cite journal