You can find the nth fibonacci number in O(log2(n)*log2(n)) computations. Apply recursively :: x(n) = x(n-(k+1))x(k) + x(n-k)x(k+1) where k = pow(2,floor(log2(n))); For example x(12) = x(3)*x(8) + x(4)*x(9) I initially precompute pairs like [x(2),x(3)], [x(4),x(5)], [x(8),x(9)], [x(16),x(17)] and store them in vector. Size of 2 vectors should be floor(log2(n)) here's how the pairs are computed: start of with a=1,b=0 iteratively in a loop: x(i*2) = a^2 + b^2 x(i*2 + 1) = 2ab - b^2 ex: in 5 loops I get x(32) and x(33) i.e. 10 multiplications to compute 33rd and 32nd fibonacci numbers. i=1; x(2) = 1, x(3) = 2 i=2; x(4) = 3, x(5) = 5 i=3; x(8) = 21, x(9) = 34 i=4; x(16) = 987 x(17) = 1597 i=5; x(32)= 2178309 x(33) = 3524578 I've described the algorithm and code on www. optionsbender .com . in the algorithms section