We have started learning about analysis of recursive algorithms and I got the gist of it. However there are some questions, like the one I'm going to post, that confuse me a little.
The exercise
Consider the problem of multiplying two big integers, i.e. integers represented by a large number of bits that cannot be handled directly by the ALU of a single CPU. This type of multiplication has applications in data security where big integers are used in encryption schemes. The elementary-school algorithm for multiplying two n-bit integers has a complexity of . To improve this complexity, let x and y be the two n-bit integers, and use the following algorithm
Recursive-Multiply(x,y) Write x = x1 * 2^(n/2)+x0 //x1 and x0 are high order and low order n/2 bits y = y1 * 2^(n/2)+y0//y1 and y0 are high order and low order n/2 bits Compute x1+x0 and y1+y0 p = Recursive-Multiply (x1+x0,y1+y0) x1y1 = Recursive-Multiply (x1,y1) x0y0 = Recursive-Multiply (x0,y0) Return x1y1*2^n + (p-x1y1-x0y0)*2^(n/2)+x0y0
(a) Explain how the above algorithm works and provides the correct answer.
(b) Write a recurrence relation for the number of basic operations for the above algorithm.
(c) Solve the recurrence relation and show that its complexity is $O(n^{\lg 3})$
My conjecture
- Since the method is being called three times, the complexity is going to be $3C(n/2) + n/2$.
My questions
What do they mean by hi-lo order bits?
How can I use a recurrence relation on this if I don't know how each recursion works?
Asked By : Julio Garcia
Answered By : Yuval Filmus
The idea is to divide each $n$-bit integer into two halves of $n/2$ bits. For example, $10100010$ would be divided into $1010$ and $0010$. Naively, we would need to multiply four such halves, but in fact there is a way to do with only three. (This is similar to matrix multiplication algorithms such as Strassen's.) The algorithm described by the exercise is known as Karatsuba multiplication.
Regarding your other question, once you have reduced the computation of running time to a recurrence relation, you no longer need to understand anything more about the recursion in order to compute the running time - this is the main point of this abstraction.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14685
0 comments:
Post a Comment
Let us know your responses and feedback