Recursive Multiplication Method

Question

I'm following along with this http://www.cs.berkeley.edu/~vazirani/algorithms/chap1.pdf (bottom of page 24). In the book the author describes Al Khwarizmi multiplication algorithm. Here is my implementation

static int RecMultiply(int x, int y)
{
    if (y == 0)
        return 0;
    int z = RecMultiply(x, y / 2);
    if (y % 2 == 0)
        return 2 * z;
    else
        return x + 2 * z;
}

I've stepped through the code a couple times and I'm just not grokking it. Why does the bottom else add x to 2 * z? It seems to me that z is used both as a running total and as the "right column" number in the algorithm in the book. Can someone break this code down and explain it please?

Answer 1

Since Multiplication is simple repetitive addition, if y is pair, you can divide it by two, and multiply x by two. (so, 2*2 = 2+2. 2*3 = 2+2+2, 2*4 = 2+2+2+2 ....)
If y is odd, you can subtract 1, to get a y that is pair, and you need to add an x, (basically, 1*y).

Here's a breakdown:

RecMultiply(5,5) :
+-  z = RecMultiply(5,2)
|   return 5 + 2 * z (=20 +5 =25)
|
|
+-- RecMultiply(5,2) :
    +-  z = RecMultiply(5,1)
    |   return 2 * z (=10)
    |
    +-- RecMultiply(5,1) :
        +-  z = RecMultiply(5,0)
        |   return 5 + 0
        |
        +---RecMultiply(5,0) :
            return 0

RecMultiply(5,4) :
+-  z = RecMultiply(5,2)
|   return 2 * z (=)
|
+-- RecMultiply(5,2) :
        +-  z = RecMultiply(5,1)
        |   return 2 * z (=10)
        |
        +-- RecMultiply(5,1) :
            +-  z = RecMultiply(5,0)
            |   return 5 + 0
            |
            +---RecMultiply(5,0) :
                return 0

So, basically, after the recursive bit (that takes care of all the pair multiplications), you might need to add another y, which in the first case above, is 5 for the first call).

Note the special case of y=1, which means x*1 which obviously is 5 in our case. Same logic applies.

You might want to look at it like this, if it helps:

static int RecMultiply(int x, int y)
{

    switch (y)
    {
        case 0:
            return 0;
            break;

        case 1:
            return x;
            break;

        default:
            return (y%2 ==0) ? RecMultiply(x, y/2)
                             : x + RecMultiply(x, y/2);
            break;
    } 
}

I think it denotes the +1 (or odd cases) in a more understandable manner.

Answer 2

It is quite simple.

Z is calculated by multiplying x and half of y.

If y was of even parity (if section) return 2*z = 2 * x * y/2 = x * y (which is original request)

If y was of odd parity (else section) return 2*z + x. Why do we add x??? That is because y/2 will be the same for even and following odd number. So Z would be the same. But, with this if section we are detecting if it's odd or even and in case of odd we add x once more to the result.