Content deleted Content added
User:EEng: nevertheless this is a standard example of a Divide-and-conquer algorithm, maybe the best example of a divide-and-conquer that doesn't just split into two subproblems of size n/2. |
(d.e. for D.E.) Of course. But the prior phrasing made it sound like "divide and conquer" was the name of this particular algorithm. (Bonus: Note use of conjunction at start of sentence.) |
||
Line 1:
{{short description|Algorithm for integer multiplication}}
[[File:Karatsuba_multiplication.svg|thumb|300px|Karatsuba multiplication of az+b and cz+d (boxed), and 1234 and 567. Magenta arrows denote multiplication, amber denotes addition, silver denotes subtraction and light cyan denotes left shift. (A), (B) and (C) show recursion used 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">
| |||