Calculate exponents via addition only

Question

We're writing a very simple program to execute on a processor we've built for a class. It doesn't have the capability to multiply or divide. We do however, had support for addition, subtraction, and, or, and branching for loop control (like branch on equal if you are familiar with MIPS). We were thinking a neat program to run on it would be some sort of x^n program. Of course, those numbers would have to be hardcoded, but given the limitations of our processor, is it realistic?

Is there an addition only calculation for exponents? Thanks.

Answer 1

For small integers, why not?

First, implement multiply using repeated addition. Then, implement pow() using repeated multiplication. It will be slow, but it will work fine.

There is a faster algorithm for exponentiation, called Exponentiation by Squaring. However, given that you don't have a fast multiply, I'm not sure it's worth it - you might want to first work on implementing a fast multiplication algorithm.

Answer 2

In line with dmazzoni's respone in c style syntax:

int mulitply(int x, int y)
{
    int product;

    for (int i = 0; i<y; i++)
       product += x;

    return product;
}

int power(int x, int exponent)
{
    int result = 1;

    for (int i = 0; i < exponent; i++)
        result = multiply(result, x);

    return result;
}