Power of number algorithm

Another example for recursive call is calculating the power of a number. The recursion requires that formal params,local variables and return address are stored onto the stack for each recursive call. However,  having in mind that RAM is a limited resources in AVR devices it is conceivable why recursive algorithms are not widely accepted in avr assembly programming. There is a need for optimization or twisting the stack frame build up requirement. The following rules will be used in building a recursive avr algorithm

•  Stack frame limit - calculate the maximum stack size in accordance with input params. RAM is a limited resource so beware how deep the rabbit hole may go. Depending on AVR device you may have different stack frame’s size.
• Save in stack frame only the minimum amount of data, use global data whenever possible. This reduce code usage and stack frame size.
• CPU saves the return address on each recursive call so apart from this, frame build up and maintenance is our code responsibility.

Two methods of finding the power of a number are presented. Both assume unsigned byte size input - word size output.

Naive solution

The most straightforward solution to the problem would be to implement  x²=x.x.x.x...x , multiplying x  n times with itself. Following implementation does not even use local stack frame variables. All calculations are done over global ones.

Optimized solution

Suppose we want to compute xⁿ, where x is a real number and n is any integer. It's easy if n is 0, since x⁰=1 no matter what x is. That's a good base condition case. Only positive numbers are considered so when you multiply powers of x, you add the exponents: x^a+x^b=x^a+b for any base x and any exponents a and b. Therefore, if n is positive and even, then xⁿ=x^n/2.x^n/2. If we were to compute y=x^n/2 recursively, then we could compute xⁿ=y.y . What if n is positive and odd? Then xⁿ=x^n-1.x and and n-1 either is 0 or is positive and even. We just saw how to compute powers of x when the exponent either is 0 or is positive and even. Therefore, we could compute x^n-1 recursively , and then use this result to compute xⁿ=x^n-1.x

What about when n is negative? Then xⁿ=1/x^-n , and the exponent −n is positive. So we can compute x^-n recursively and take its reciprocal.

Putting these observations together, we get the following recursive algorithm for computing xⁿ.

• The base case is when n=0,and x⁰=1.
•  If n is positive and even, recursively compute y=x^n/2 and then xⁿ=y.y. Notice that you can get away with making just one recursive call in this case, computing x^n/2 just once, and then you multiply the result of this recursive call by itself.
•  If n is positive and odd, recursively compute x^n-1, so that the exponent either is 0 or is positive and even. Then, xⁿ=x^n-1.x.
•  If n is negative, recursively compute x^-n, so that the exponent becomes positive. Then, xⁿ=1/x^-n.

The following acorn kernel task is based  on positive numbers only. Default task stack is 20 and each stack frame keeps 1 byte and return call of 2 bytes. There is however an internal call to multiply function in each frame after 1 byte is popped off the stack. So total stack frame usage is 4 bytes. Calculating 8⁵ will require (5/2+1)*4=12. The default task stack size is less than 20 bytes so NO increase of the variable TASK_STACK_DEPTH in kernel.inc is required.