Content deleted Content added
m →Peasant or binary multiplication: Template parameters |
→Karatsuba multiplication: linkify Anatoly Karatsuba |
||
Line 314:
===Karatsuba multiplication===
{{Main|Karatsuba algorithm}}
For systems that need to multiply numbers in the range of several thousand digits, such as [[computer algebra system]]s and [[bignum]] libraries, long multiplication is too slow. These systems may employ '''Karatsuba multiplication''', which was discovered in 1960 (published in 1962). The heart of [[Anatoly Karatsuba|Karatsuba]]'s method lies in the observation that two-digit multiplication can be done with only three rather than the four multiplications classically required. This is an example of what is now called a ''[[divide and conquer algorithm]]''. Suppose we want to multiply two 2-digit base-''m'' numbers: ''x''<sub>1</sub>'' m + x''<sub>2</sub> and ''y''<sub>1</sub>'' m + y''<sub>2</sub>:
# compute ''x''<sub>1</sub> · ''y''<sub>1</sub>, call the result ''F''
| |||