Content deleted Content added
Tag: Reverted |
Grapesurgeon (talk | contribs) integer specify in lead |
||
| (One intermediate revision by one other user not shown) | |||
Line 12:
}}
[[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 cyan denotes left shift. (A), (B) and (C) show recursion with z=10 to obtain intermediate values.]]
The '''Karatsuba algorithm''' is a fast [[multiplication algorithm]] for [[Integer|integers]]. It was discovered by [[Anatoly Karatsuba]] in 1960 and published in 1962.<ref name="kara1962">
{{cite journal
| author = A. Karatsuba and Yu. Ofman
Line 83:
===Example===
To compute the product of 12345 and 6789, where ''B'' = 10, choose ''m'' = 3. We use ''m'' right shifts for decomposing the input operands using the resulting base (''B''<sup>''m''</sup> = ''1000''), as:
: 12345 = '''12''' · ''1000'' + '''345'''
: 6789 = '''6''' · ''1000'' + '''789'''
| |||