I was WAY off on how high F_n you could go before overflowing unsigned ints. And the C pow function.

Using this simple C, I printf the numbers. To verify accuracy, and where they over flow. FibAdd and FibPow overflow at 45 or 46, FibPowC goes one further and then gives infinity.

Code:

#include <stdio.h>
#include <math.h>
unsigned int FibAdd ( int n ) {
int i;
unsigned int result1 = 0;
unsigned int result2 = 1;
unsigned int temp;
for ( i=0; i < n ; i++ ){
temp = result2;
result2 = result2 + result1;
result1 = temp;
}
printf("\n %u", result2);
return(result2);
}
unsigned int myPow (double base, int exp){
int i;
double result = 1.0;
for ( i=0; i <exp; i++ ) {
result = result * base;
}
return((unsigned int)result);
}
unsigned int FibPow( int n ) {
unsigned int result;
result = (unsigned int)round(0.4472135955 * ( myPow( 1.61803398875, n ) - myPow( -0.61803398875, n ) ));
printf("\n %u", result);
return(result);
}
unsigned int FibPowC( int n ) {
unsigned int result;
result = (unsigned int)round(0.4472135955 * ( pow( 1.61803398875, n ) - pow( -0.61803398875, n ) ));
printf("\n %u", result);
return(result);
}
int main (int argc, const char * argv[]) {
register int i;
//
//Just change the function in here between FibAdd, FibPow, and FibPowC
//FibAdd( i ); or FibPow( i+1 ); or FibPowC( i+1 );
for ( i=0; i<46; i++ ) {
FibPow( i+1 );
}
printf("\n");
return 0;
}

Here are some plots of the data points I've taken. Each n is the degree of Fibonacci(n), and the plots are in seconds. 500 million random F_n's are calculated using each method.

The order is FibAdd, FibPow, FibPowC. It looks like FibPowC will certainly be a better function in the long haul, but has much more function overhead. Over the range of that is relevant using unsigned ints (N<46) FibAdd wins hands down.

FibAdd = 0.83n + 12.31

FibPow = 2.02n + 37

FibPowC = 0.37n + 47.78

EDIT: I'd just like to take a moment and say that my hypothesis of Nadditions being about twice as fast as 2Nmutiplications seems correct, that was I guess was the point of all my nonsense today.