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).

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.

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

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.

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.

The definition of convex hull in this article is not the same as the standard terminology. I urge the author to use the standard terminologies(which is on the wikipedia page linked in the first paragraph.)

I made a benchmark that shows that in practice:

docs.google.com/spreadsheets/d/1mDIuAUrI6lzZxDf2HEqHbaYjddfK0hijd_r9qBOOEoQ

*cap obvious flies away*

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:

gist.github.com/ClashTheBunny/762a497d920a24aada69

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

Then you can do:

I know it essentially does the same thing, IMHO it's a little cleaner code thou ;)

The power function is also not O(1) in n. You would get the same runtime O(log(n)) with a clever implementation.

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?

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.

Also, is the full code available somewhere (e.g. Github)? It would be nice to see! Thanks for the informative post!