Fibonacci Optimization

The Reducing Power Consumption module discusses why it is important to keep power in mind when programming embedded devices. We have yet to consider this while programming the previous labs. Writing efficient code is the first step in improving power consumption, next we can disable all parts of the board that aren't currently being used.

Take the following piece of code:

long fibo(int n) 
{
  if (n < 2)
   return n;
  else 
   return fibo(n-1) + fibo(n-2);
}

The original program is very inefficient and wastes memory in several of the ways described in the inefficient Memory Conservation module. Modify the code to eliminate the memory waste and improve the speed of the program. Note that there is a tradeoff between speed and memory (though at first the program is simply gratuitously wasteful). What is the nature of the tradeoff? Assuming the one addition takes one cycle to complete, how long would it take the original code to complete fibo(50)? How long would it take your new, improved version? Assume that you are only considering the addition operations.

Low Power Modes

Modify your project so that the processor remains in one of the low power modes whenever it is not doing any calculations. Wake up from the low power mode using a timer interrupt (change the timer settings so that there is a substantial time period between interrupts) and have your program compute fibo(50). You may want to make the program compute fibo(50) more than once so that the MSP is in the ISR performing an intensive task for longer and thus make it easier to read the current consumption value. Output the result to the standard out display. What is the result? (Hint: 12,586,269,025) Make sure the result is correct number. As soon as the calculation is done, return to low power mode. Perform the same process to calculate the current consumption during the use of your Fibonacci function. You should have measured three current consumption values: 1) in the low power mode, 2) while processing fibo(50), and 3) while processing the 50th Fibonacci number using your function.