[ASM] How to write a formula for instruction count

[Isaac Dontje Lindell]

Right up front: this is for my computer science class, so don't directly give me the answer. Guide me. :p

We're working in assembly right now, and are using a simulated machine that has a much simpler instruction set than a real instruction set. The current project has us writing 3 different programs that do the same thing in different ways: given an exponent and a base, calculate the appropriate result. The first program is just a simple loop, multiplying the base by itself exponent number of times.

The second one uses this formula (in Java because it's fairly readable):

public static double power(double b, int e) {
        double power = 1;
        while (e > 0) {
            if ((e % 2) == 0) {
                b = b * b;
                e = e / 2;
            } else {
                power = power * b;
                e = e - 1;
            }
        }
        return power;
    }

I'm trying to find a formula for the number of instructions run for any given exponent. For the first program, coming up with the formula was fairly straightforward. But this one has added complexity, in that if the number is divisible by 2, it divides the exponent by two. I can't for the life of me figure out how to come up with the formula. The simulated machine tells me exactly how many instructions are run each time, but I need a formula to predict that.

Here's the assembly code I've written. It works, and it's been checked by my prof.

;;performs exponation given a base and a non-negative integer exponent

allocate-registers base, exponent       ;;inputs
allocate-registers one, two	                 ;;constants
allocate-registers expMod2                 ;;temporary register
allocate-registers exponate, done, if   ;;labels
allocate-registers output                    ;;holds the result


	read base
	read exponent
	li one 1
	li two 2	
	li exponate exponateL
	li done doneL
	li if ifL
	li output 1

exponateL:
	jeqz exponent done         ;;while exponent is greater than one do this loop
	rem expMod2 exponent two
	jeqz expMod2 if            ;;if exponent%2 == 0, jump to ifL
	mul output output base
	sub exponent exponent one
	j exponate


doneL:
	write output
	halt


ifL:
	mul base base base
	div exponent exponent two
	j exponate

The lines that have a colon at the end (doneL, etc) are line labels and aren't counted as instructions. Also, the register allocations do not count. jeqz is a conditional jump, will jump to the label given by the second argument if the content of the first argument (a register) is zero.

j is an unconditional jump.

li loads the second argument into the register specified by the first argument.

add, sub, mul, div are standard operations. rem is remainder.

Can you help me?

[Lant]

  Quote

in that if the number is divisible by 2, it divides the exponent by two

Then I would guess that the complexity would involve log₂.

[LiveAndFight]

The only thing I could think off would be to wrap each asm instruction into a "function" (called via a jmp) so you can manually increment your counter based on how many instructions it takes to do whatever takes you need it to do. It will be hard coded and slow but thats the only thing I can think of.