 You should write an article — «Response to the Nth Fibonacci Number in O(log N)»! IT would be interesting to read. Thinking about it, I realized that even the implementation described here isn't really O(log n). Here's why: it's rather easy to prove that the nth term of the Fibonacci sequence has O(n) digits. So, even if you are performing only O(log n) multiplications, each multiplication is actually O(n), so the algorithm is actually O(n log n).

I made a benchmark that shows that in practice: ``````
def mul(A, B):
return (A*B + A*B, A*B + A*B,
A*B + A*B, A*B + A*B)

def fib(n):
if n==1: return (1, 1, 1, 0)
A = fib(n>>1)
A = mul(A, A)
if n&1: A = mul(A, fib(1))
return A
``````

*cap obvious flies away* Freya, our project is not for promoting your own products. You should read the Rules page. If you want to let people know about your product, share the technical side of it. Community will reward you for that. Otherwise your publications will be downvoted and automatically be moved to Trash hub. Where are technical details? Cheap promotion! Why do you memoize the matrix method and not the iterative method? When I memoize the iterative method, I end up with about constant time for each of the steps:
Around 1000 gives Iterative: 0.054137468338 Matrix: 1.92105817795

This all stays in memory for my machine.

You can find the improved fork of your code here: If you do the matrix power more cunningly, you don't need to memoize anything. Just use this:

``````
def mat_pow(m, e):
if e == 1:
return m
else:
m2 = mat_pow(m, e/2)
if (e % 1) == 0:
return m2 * m2
else:
return m2 * m2 * m
`````` Also, you should memoize the matrix multiplication, that's a heavy step, and one for repeated invocations would save a ton of time. Bottom of def get_number renders as the Registered Trademark unicode instead of ®.

You can be a little more concise with the code by modifying how __memo is set up.

``````def __init__(self):
self.__memo = {0:0,1:1}``````

Then you can do:
``````
def __get_matrix_power(self, M, p):
"""Matrix exponentiation (it is expected that p that is equal to the power of 2)."""
return self.__memo.get(p,self.non_memoized(M,p))

def non_memoized(self, M,p):
K = self.__get_matrix_power(M, int(p/2))
R = self.__multiply_matrices(K, K)
self.__memo[p] = R
return R
``````

I know it essentially does the same thing, IMHO it's a little cleaner code thou ;) Computing the n-th power of the diagonalized matrix would involve non-integer arithmetic, thus rounding errors. One could argue that the error should not affect the integer part, but I'd say that depends on the size of n.

The power function is also not O(1) in n. You would get the same runtime O(log(n)) with a clever implementation. Just diagonalize the matrix and do it in constant time. Thanks for a detailed feedback, Chao. We are looking into editing the article.

Off-topic: this conversation brought us to an interesting idea. What if we would let our users to edit articles and send diffs to authors, similar to git pull requests? Here are some suggestions. I hope this produces the minimum amount of changes so the definition is equivalent to the standard terminology.

1. Instead of defining «hull», one can just state it as a «a closed curve that encloses all the points». «Hull» by itself isn't used much outside this paragraph, and one can just say «closed curve» instead of «hull» to refer to the hull because there is little ambiguity.
2. One can then define what it means for a closed curve to be convex.
3. Replace all occurrence of «minimal convex hull» with «convex hull». Define the «convex hull of S» as the region bounded by the shortest convex closed curve that contains all the points in S.
4. Finally, one can state that what it means to «find the convex hull». State it as finding the boundary curve of the convex hull(which is the original «minimal convex hull»).

One can prove this definition is equivalent to the convex hull definition for finite set of points on the plane in wikipedia. For sorting, I suggest using the
``my_list.sort(key=keyfunc)``
syntax; see my comment on Reddit for more details.

Also, is the full code available somewhere (e.g. Github)? It would be nice to see! Thanks for the informative post! Hey Chao, thanks for pointing that out. We'll try to edit it. Anything you would like to contribute?     