CODEWITHSUNDEEP
algorithmmipsadditionexponent
powervillekittenkins
powervillekittenkins

Reputation: 41

Calculate exponents via addition only

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.

Upvotes: 4

Views: 11808

Answers (6)

D_K
D_K

Reputation: 1420

exponent n to power of k:

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

Upvotes: 0

Nick Johnson
Nick Johnson

Reputation: 101149

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.

Upvotes: 0

Keith Randall
Keith Randall

Reputation: 23265

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

Upvotes: 2

Guffa
Guffa

Reputation: 700382

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)

Upvotes: 0

Brett Allen
Brett Allen

Reputation: 5487

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

Upvotes: 7

dmazzoni
dmazzoni

Reputation: 13236

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.

Upvotes: 7

Related Questions