科技回声

12 条评论

OskarS超过 8 年前

It's interesting to note that if you add a modulus to the calculation (i.e. if you calculate F(n) mod M), you can calculate ridiculously large values using the matrix/doubling method. You can, for instance, calculate the last 10 digits of the Googolth Fibonacci number instantly (since you only need O(log n) multiplications, it's just a few hundred for 10^100 ). Doing it the "naive" dynamic programming way, it would take you far longer than the age of the universe.It's a neat illustration of asymptotic running times.

评论 #12873452 未加载

rawnlq超过 8 年前

The fast exponentiation algorithm actually generalizes:<a href="http://kukuruku.co/hub/algorithms/automatic-algorithms-optimization-via-fast-matrix-exponentiation.html" rel="nofollow">http://kukuruku.co/hub/algorithms/automatic-algorithms-optim...</a>

评论 #12873873 未加载

adilparvez超过 8 年前

There is a log time way to do this, use Binet's formula (<a href="https://en.m.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression" rel="nofollow">https://en.m.wikipedia.org/wiki/Fibonacci_number#Closed-form...</a>), but do the arithmetic in the field Q[√5].Edit: Someone's implementation: <a href="http://ideone.com/NWQe38" rel="nofollow">http://ideone.com/NWQe38</a>Edit: constant time -> log time

评论 #12872227 未加载

jheriko超过 8 年前

for really big numbers there are the generalisations of karatsuba and toom-cook for higher numbers of splits, and beyond that there are the FFT multiplication methods which i believe are the fastest general case methods for very large numbers.also the laddering scheme used for the 'exponentiation' can be in different forms, the left-to-right or right-to-left form or even a Montgomery ladder...i seemed to recall there is a 'fastest known' method for generating fibonacci or lucas numbers... but google is not helping me.pretty sure i had seen it in this book: <a href="https://www.amazon.co.uk/Prime-Numbers-Computational-Carl-Pomerance/dp/0387252827" rel="nofollow">https://www.amazon.co.uk/Prime-Numbers-Computational-Carl-Po...</a> i'll have to check when i have access to it next. :)

jerven超过 8 年前

The BigInteger implementation in java uses better multiplication algorithms in Java 1.8 then in the version of 1.6 tested [1], switching to toom-cook[2] for even larger numbers. So that in practice Fibonacci in java becomes an benchmark of allocation rate.[1]: <a href="http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132/java/math/BigInteger.java?av=f#1464" rel="nofollow">http://grepcode.com/file/repository.grepcode.com/java/root/j...</a>[2]:<a href="https://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication" rel="nofollow">https://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplicati...</a>

brudgers超过 8 年前

For anyone interested in Fibonacci numbers: Fibonacci Quarterly has been published for more than fifty years.<a href="http://www.fq.math.ca/" rel="nofollow">http://www.fq.math.ca/</a>

kitanata超过 8 年前

Isn't there a constant time implementation using the Golden Mean? What is the advantage of these algorithms over the constant time one? (i.e. Binet's formula)

评论 #12872396 未加载

评论 #12872468 未加载

评论 #12872223 未加载

评论 #12872661 未加载

评论 #12872301 未加载

jmstfv超过 8 年前

So, seems like matrix exponentiation is faster than computing eigenvalues / eigenvectors in practice? Take a look: <a href="http://mathoverflow.net/questions/62904/complexity-of-eigenvalue-decomposition" rel="nofollow">http://mathoverflow.net/questions/62904/complexity-of-eigenv...</a>

chaitanyav超过 8 年前

Product of Lucas Numbers Algorithm - "A fast algorithm for computing large Fibonacci numbers" -<a href="https://pdfs.semanticscholar.org/9652/9e1fedb0a372b825215c7b471a99088f4515.pdf" rel="nofollow">https://pdfs.semanticscholar.org/9652/9e1fedb0a372b825215c7b...</a>

评论 #12875922 未加载

评论 #12876704 未加载

gandolfinmyhead超过 8 年前

fast doubling for fibonacci is mentioned in sicp. Cheers for sicp

nayuki超过 8 年前

Previous discussion: <a href="https://news.ycombinator.com/item?id=9315346" rel="nofollow">https://news.ycombinator.com/item?id=9315346</a>

mrcactu5超过 8 年前

the continued fraction of (1+√5)/2 is [1;1,1,1,1,1,1,...] it goes on forever.there are more advanced formulas in this article of Curtis McMullen <a href="http://www.math.harvard.edu/~ctm/papers/home/text/papers/cf/cf.pdf" rel="nofollow">http://www.math.harvard.edu/~ctm/papers/home/text/papers/cf/...</a>

12 条评论

OskarS超过 8 年前

评论 #12873452 未加载

rawnlq超过 8 年前

评论 #12873873 未加载

adilparvez超过 8 年前

评论 #12872227 未加载

jheriko超过 8 年前

jerven超过 8 年前

brudgers超过 8 年前

For anyone interested in Fibonacci numbers: Fibonacci Quarterly has been published for more than fifty years.<a href="http://www.fq.math.ca/" rel="nofollow">http://www.fq.math.ca/</a>

kitanata超过 8 年前

Isn't there a constant time implementation using the Golden Mean? What is the advantage of these algorithms over the constant time one? (i.e. Binet's formula)

评论 #12872396 未加载

评论 #12872468 未加载

评论 #12872223 未加载

评论 #12872661 未加载

评论 #12872301 未加载

jmstfv超过 8 年前

chaitanyav超过 8 年前

评论 #12875922 未加载

评论 #12876704 未加载

gandolfinmyhead超过 8 年前

fast doubling for fibonacci is mentioned in sicp. Cheers for sicp

nayuki超过 8 年前

Previous discussion: <a href="https://news.ycombinator.com/item?id=9315346" rel="nofollow">https://news.ycombinator.com/item?id=9315346</a>

mrcactu5超过 8 年前

Fast Fibonacci Algorithms (2015)

12 条评论

Fast Fibonacci Algorithms (2015)

12 条评论