Content deleted Content added
(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.) |
→Basic step: updating a link to point to the right place in the target article |
||
Line 35:
===Basic step===
The basic principle of Karatsuba's algorithm is [[Divide-and-conquer algorithm|divide-and-conquer]], using a formula that allows one to compute the product of two large numbers <math>x</math> and <math>y</math> using three multiplications of smaller numbers, each with about half as many digits as <math>x</math> or <math>y</math>, plus some additions and digit shifts. This basic step is, in fact, a generalization of [[Multiplication algorithm#Complex
Let <math>x</math> and <math>y</math> be represented as <math>n</math>-digit strings in some base <math>B</math>. For any positive integer <math>m</math> less than <math>n</math>, one can write the two given numbers as
| |||