From ASMBits


The Fibonacci sequence can be defined recursively. The nth Fibonacci number is the sum of the (n-1)th and (n-2)th Fibonacci number. There are two base cases: The 0th and 1st Fibonacci number are both 1.

Write an efficient (possibly non-recursive) function that computes the value of the nth Fibonacci number. In addition, if the nth Fibonacci number will overflow an unsigned integer, return 0 to indicate an overflow.

unsigned int fib(unsigned int n);

The input will not be small enough to run in a reasonable amount of time if implemented using plain recursion. The input test cases are bigger and have a lower runtime limit than fib1.

Expected solution length: Around 15-20 lines.

Sample Input


Sample Output


Write your solution here

Upload a source file...