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:

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

def mul(A, B):
    return (A[0]*B[0] + A[1]*B[2], A[0]*B[1] + A[1]*B[3], 
            A[2]*B[0] + A[3]*B[2], A[2]*B[1] + A[3]*B[3])
    
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:
gist.github.com/ClashTheBunny/762a497d920a24aada69

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?

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

AVL Lab

BYU CS235 Burton Seamons

Hey, good point, should be ok now ;)

the enqueue function of the regular implement seems wrong.

Great article. I just want to note another typo: it's written equals and hashMap methods, but I suppose you wanted to write about equals and hashCode.