CODEWITHSUNDEEP
algorithm
xoux
xoux

Reputation: 3494

What is the recurrence equation for this multiplication algorithm?

The multiplication algorithm is for multiplying two radix r numbers:

0 <= x,y < r^n
x = x1 * r^(n/2) + x0
y = y1 * r^(n/2) + y0

where x0 is the half of x that contains the least significant digits, and x1 is the half with the most significant digits, and similarly for y.

So if r = 10 and n = 4, we have that x = 9723 = 97 * 10^2 + 23, where x1 = 97 and x0 = 23.

The multiplication can be done as: 

z = x*y = x1*y1 + (x0*y1 + x1*y0) + x0*y0

So we have now four multiplications of half-sized numbers (we initially had a multiplication of n digit numbers, and now we have four multiplications of n/2 digit numbers).

As I see it the recurrence for this algorithm is: 

T(n) = O(1) + 4*T(n/2)

But apparently it is T(n) = O(n) + 3T(n/2)

Either way, the solution is T(n) = O(n^2), and I can see this, but I am wondering why there is an O(n) term instead of an O(1) term?

Upvotes: 2

Views: 462

Answers (1)

blazs
blazs

Reputation: 4845

You are right, if you'll compute the term x0*y1 + x1*y0 naively, with two products, the time complexity is quadratic. This is because we do four products and the recurrence is, as you suggest, T(n) = O(n) + 4T(n/2), which solves to O(n^2).

However, Karatsuba observed that xy=z2 * r^n + z1 * r^(n/2) + z0, where we let z2=x1*y2, z0=x0*y0, and z1=x0*y1 + x1*y0, and that one can express the last term as z1=(x1+x0)(y1+y0)-z2-z0,which involves only one product. Using this trick, the recurrence does become T(n) = O(n) + 3T(n/2) because we do three products altogether (as opposed to four if don't use the trick).

Because the numbers are of order r^n we will need n digits to represent the numbers (in general, for a fixed r>=2, we need O(log N) digits to represent the number N). To add two numbers of that order, you need to "touch" all the digits. Since there are n digits, you need O(n) (formally I'd say Omega(n), meaning "at least order of n time", but let's leave the details aside) time to compute their sum.

For example, when computing the product N*M, the number of bits n will be max(log N, log M) (assuming the base r>=2 is constant).

The algebraic trick is explained in more detail on the Wiki page for the Karatsuba algorithm.

Upvotes: 1

Related Questions