(Algorithm) Find n'th Fibonacci nuber with complexity O(log(n)) and in O(1) space

Question: We have given number n. And it is asked that we have to find n'th Fibonacci number. However, we have two conditions.

1) Complexity should be O(log(n))

2)We should compute this in O(1) space

Resource: http://www.careercup.com/page?pid=algorithm-interview-questions

Question Owner: zr.roman

ANSWER

I think, maybe, Term which is "O(1) space" may confuse your mind.

"O(1) space" means you should use same memory for all kind of n's.

Let's try to catch the "regularity" from examples:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

You may think that you can store all Fibonacci numbers, and use binary search algorithm.

However this way is useless, because Fibonacci sequence is infinite. There always be greater Fibonacci number for your last number stored.

I will use formula to compute this by rounding with the help of golden ratio. You can find more about this in this link.

This computing is in O(1) space and has complexity O(1) too. If you have any extra solution pls contact me.