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;
}

Answer 3

It's very realistic. It's not so many years back that processors didn't have an ALU that could do any advanced operations like multiplication and division.

Multiplication is usually done using shifting and adding. Here's some pseudo-assembly:

; multiply registers a and b

; use c as high b
mov c,#0
; use d as low result
mov d,#0
; use e as high result
mov e,#0
.nextbit:
  ; shift low bit out of a
  shr a
  ; skip if zero
  bcc .noadd
    ; add b to result
    add d,b
    adc e,c
  .noadd:
  ; double b
  shl b
  rcl c
  ; test a
  cmp a,#0
bne .nextbit

(Note that the result of multiplying two byte values is a two byte value.)

Once you have a multiplication, you can just loop to calculate power.

instructions used:

mov x,y = move y into x
shr x = shift right one bit
shl x = shift left one bit
rcl x = rotate left one bit with carry inserted
add x,y = add y to x
adc x,y = add y to x with carry
cmp x,y = compare x to y
bcc = branch on carry clear
bne = branch on not equal
#0 = literal number zero (as opposed to 0, which would be the address zero)

Answer 4

Like Aequitarum's solution, but uses repeated squaring for powers and repeated doubling for multiplies. Should be faster for large x,y:

int multiply(int x, int y) {
  int product = 0;
  int bitmask = 1;

  while (y >= bitmask) {
    if (y & bitmask) product += x;
    x += x;
    bitmask += bitmask;
  }
  return product;
}

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

  while (exponent >= bitmask) {
    if (exponent & bitmask) result = multiply(result, x);
    x = multiply(x, x);
    bitmask += bitmask;
  }
  return result;
}

Answer 5

You may find the Wikipedia article on Multiplication ALU relevant. With addition and bitwise operations (and and or), you can implement multiplication in one step per bit, rather than having to add as many times as the magnitude of the smaller operator.

Answer 6

exponent n to power of k:

exponent(n,k) {
   for(x=1..n)
      x = x + exponent(x,k-1)
}