Question
Please use C not C++
continue
Exercise 1 shows that it is possible to compute xn in O(log N) time. This fact in turn makes it possible to write an implementation of the function Fib (a) that also runs in O(log N) time, which is much faster than the traditional iterative version. To do so, you need to rely on the somewhat surprising fact that the Fibonacci function is closely related to a value called the golden ratio, which has been known since the days of Greek mathematics. The golden ratio, which is usually designated by the Greek letter phi is defined to be the value that satisfies the equation phi 2 - phi - 1 = 0 Because this is a quadratic equation, it actually has two roots. If you apply the quadratic formula, you will discover that these roots are In 1718. the French mathematician Abraham de Moivre discovered that the nth Fibonacci number can be represented in closed form as Moreover, since phi ^n is always very small, the formula can be simplified to rounded to the nearest integer. Use this formula and the RaiseToPower function from exercise 1 to write an implementation of Fib(n) that runs in O(log N) time. Once you have verified empirically that the formula seems to work for the first several terms in the sequence, use mathematical induction to prove that the formula actually computes the nth Fibonacci number.
Explanation / Answer
#include /* Function to calculate x raised to the power y */ int power(int x, unsigned int y) { if( y == 0) return 1; else if (y%2 == 0) return power(x, y/2)*power(x, y/2); else return x*power(x, y/2)*power(x, y/2); } /* Program to test function power */ int main() { int x = 2; unsigned int y = 3; printf("%d", power(x, y)); getchar(); return 0; } Above function can be optimized to O(logn) by calculating power(x, y/2) only once and storing it. /* Function to calculate x raised to the power y in O(logn)*/ int power(int x, unsigned int y) { int temp; if( y == 0) return 1; temp = power(x, y/2); if (y%2 == 0) return temp*temp; else return x*temp*temp; } Time Complexity of optimized solution: O(logn) Let us extend the pow function to work for negative y and float x. /* Extended version of power function that can work for float x and negative y*/ #include float power(float x, int y) { float temp; if( y == 0) return 1; temp = power(x, y/2); if (y%2 == 0) return temp*temp; else { if(y > 0) return x*temp*temp; else return (temp*temp)/x; } } /* Program to test function power */ int main() { float x = 2; int y = -3; printf("%f", power(x, y)); getchar(); return 0; } float Q_rsqrt( float number ) { long i; float x2, y; const float threehalfs = 1.5F; x2 = number * 0.5F; y = number; i = * ( long * ) &y; // evil floating point bit level hacking i = 0x5f3759df - ( i >> 1 ); // what the fuck? y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed #ifndef Q3_VM #ifdef __linux__ assert( !isnan(y) ); // bk010122 - FPE? #endif #endif return y; } float InvSqrt(float x) { float xhalf = 0.5f*x; int i = *(int*)&x; // get bits for floating value i = 0x5f375a86- (i>>1); // gives initial guess y0 x = *(float*)&i; // convert bits back to float x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy return x; }