On Thu, Feb 22, 2018 at 12:55 PM, Jack Fearnley <j...@alcor.concordia.ca> wrote: > I realize that this thread is about benchmarking and not really about > generating fibonacci numbers, but I hope nobody is using this code to > generate them on a 'production' basis, > > Fibonacci numbers, any linearly recursive sequence for that matter, can > be generated in log time.
To be pedantic, that's not really true; see below. > GP/Pari on my Intel I7 computes fibonacci(100000) in less than 1 ms, > fibonacci(1000000) in 5ms, fibonacci(10000000) in 59 ms and finally > fibonacci(100000000) in 733 ms. I'm not sure exactly what algorithm that's using, but note that the growth of these timings is *not* logarithmic. In fact, it's superlinear. It's true can generate Fibonacci numbers in log(n) iterations using linear algebra. As long as multiplication and addition are assumed to be constant time, then the Fibonacci algorithm is indeed O(log n) time. However, the numbers in the sequence grow on the order of O(phi ** n) which quickly exceeds what you can fit into a 32-bit integer. Therefore bigints are quickly required. The fastest known integer multiplication algorithm is O(n * log n * log log n). The Fibonacci numbers grow at O(phi ** n) and therefore require O(log (phi ** n)) = O(n) bits to represent them. Each iteration therefore requires O(n * log n * log log n) time, and with O(log n) iterations the total time of the algorithm is thus O(n * (log n) ** 2 * log log n). It's still a lot faster than the brute force approach, and aeons faster than the brute-force recursive approach, but it's not strictly logarithmic because that part of the analysis is dwarfed by the cost of the arithmetic involved. -- https://mail.python.org/mailman/listinfo/python-list
