tags:

views:

259

answers:

2

Tail recursive method to multiple 2 numbers

public static int Multiply2(int x, int y)
{
    return MulTail(x, y, x);
}

public static int MulTail(int x, int y, int result)
{
    if (y == 0 || x == 0)
        return 0;
    if (y == 1)
        return result;

    return MulTail(x, y - 1, result+x);

}

Changed the implementation to accommodate negative numbers

public static int Multiply2(int x, int y)
        {
            if ((y < 0 && x > 0) || (x < 0 && y < 0))
            {
                y = y - y - y;
                x = x - x - x;
            }


            return MulTail(x, y, x);
        }

        public static int MulTail(int x, int y, int result)
        {
            if (y == 0 || x == 0)
                return 0;
            if (y == 1)
                return result;

            return MulTail(x, y - 1, result+x);

        }
A: 

You could improve it by moving the zero-check into Multiply2, so it's only checked once.

Or you could just use your language's built-in multiply operation :P

It also looks like you'll hit an infinite loop for negative values of y, so if y is negative and x is positive, you could swap the signs; if they are both negative, make them both positive.

Mark Rushakoff
+1  A: 

A method for multiplication using only addition, subtraction, and doubling is called Ancient Egyptian Multiplication. This method is more efficient than what you've proposed and can be formulated into a tail-recursive implementation.

Greg Hewgill
Requires division by two, which I assumed we didn't have.
wrang-wrang