1
$\begingroup$

I am not sure if I can post these kinds of questions on this site, but I was wondering if you could help me with a question that's been bothering me.

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. Can you please help me?

Thank you for your time.

Question:

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^lg3)

$\endgroup$
3
  • 1
    $\begingroup$ This is the Karatsuba algorithm for integer multiplication. Thematically your Question might be better suited for the Theoretical Computer Science site, but I see related Questions posed at crypto.SE and math.SE. See specifically this Question. $\endgroup$ – hardmath Sep 30 '13 at 5:46
  • 1
    $\begingroup$ That said, you should explain what you've tried so far to solve this problem, and narrow it down from simply repeating what looks like a course exercise to the specific issue which you need help with. Just putting homework out and hoping for someone to do it for you will provoke feelings of resentment. $\endgroup$ – hardmath Sep 30 '13 at 6:09
  • 1
    $\begingroup$ @hardmath: I'd recommend Computer Science Stack Exchange instead of Theoretical Computer Science, because Karatsuba is a topic that could be covered at the undergraduate level. (For instance, MIT covers it in their first undergraduate course on algorithms.) For recurrence relations, Cormen, Leiserson, Rivest and Stein (also known as CLRS) is one classic reference. $\endgroup$ – Geoff Oxberry Sep 30 '13 at 17:35

Browse other questions tagged or ask your own question.