3
$\begingroup$

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

  1. Since the method is being called three times, the complexity is going to be $3C(n/2) + n/2$.

My questions

  1. What do they mean by hi-lo order bits?

  2. How can I use a recurrence relation on this if I don't know how each recursion works?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Ok, that makes sense now. Another question: is my complexity assumption correct? $\endgroup$
    – Julio Garcia
    Sep 30, 2013 at 0:28
  • $\begingroup$ Well, $n/2$ has no meaning, since you don't know how much each operation actually costs - instead, you want $O(n)$. Other than that, it looks fine. $\endgroup$
    – Yuval Filmus
    Sep 30, 2013 at 0:43
  • $\begingroup$ I saw the complexity on the page you provided. How can I do recurrence on it with c and d in the way? $\endgroup$
    – Julio Garcia
    Sep 30, 2013 at 0:47
  • $\begingroup$ Take $f(n) = cn + d$ and use $f(n) = \Theta(n)$. $\endgroup$
    – Yuval Filmus
    Sep 30, 2013 at 5:44
  • 1
    $\begingroup$ You should understand what $\Theta(n)$ means. That's more important than what you professor used, and could help you answer your own question. $\endgroup$
    – Yuval Filmus
    Oct 1, 2013 at 6:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.