3 ms·
You can probably use Gosper's algorithms for computing with continued fractions ( http://perl.plover.com/yak/cftalk/ http://perl.plover.com/yak/cftalk/ ) to gen
by RiderOfGiraffes 17y ago
You can probably use Gosper's algorithms for computing with continued fractions ( http://perl.plover.com/yak/cftalk/ http://perl.plover.com/yak/cftalk/ ) to generate precision as needed. The CF for phi is [1; 1, 1, 1, 1, ...] and basically all you need to do is take the n^th power. You can use that using the log(n) method (http://www.brpreiss.com/books/opus5/html/page54.html http://www.brpreiss.com/books/opus5/html/page54.html (that reference took a surprisingly long time to find - there must be a better one))
I'd be surprised if there isn't a true linear time algorithm for Fibonacci, it's just that it's more subtle than people think.
PS: Finding an optimal sequence of multiples and squares for computing an arbitrary power is still an open question.
- cperciva 17y agoYou can probably use Gosper's algorithms for computing with continued fractions ( http://perl.plover.com/yak/cftalk/ http://perl.plover.com/yak/cftalk/ ) to generate precision as needed. The CF for phi is [1; 1, 1, 1, 1, ...] and basically all you need to do is take the n^th power. I'm trying to figure out if you're intentionally making a sophisticated math joke or not -- and failing. Are you? The precision to which you need to compute phi in order to compute the Nth Fibonacci number by exponentiation is the precision you'd obtain by computing the ratio of the Nth and (N-1)th Fibonacci numbers -- which is exactly how you evaluate the continued fraction for phi. So your suggestion amounts to "compute the Nth Fibonacci number... then do a lot of work to use that value to compute the Nth Fibonacci number". :-)
- eru 17y ago> So your suggestion amounts to "compute the Nth Fibonacci number... then do a lot of work to use that value to compute the Nth Fibonacci number". :-) That might just work in a lazy language.
- cperciva 17y agoIt works in non-lazy languages, too... it just happens to be a waste of cycles. :-)
- jcl 17y agoHow? Giving f(N) in terms of f(N) hardly seems useful, in any language. (It's hard to tell if you're joking without a smiley.)
- eru 17y agoI am too dumb / lazy to think of an example for the fibonaccy numbers at the top of my head. But suppose your problem was giving a list of natural numbers, then giving a circular definition like > naturals = 0 : (map (+1) naturals) actually works in Haskell. (In Haskell a:b means the same as (cons a b) in Lisp. I also added parens to make the definition more readable for non-Haskellers.)
- jcl 17y agoSo, that actually works by establishing a base value and a derivation step... i.e., it defines N(0), then it expresses N(n) in terms of N(n - 1). If you try to do the same thing for Fibonacci numbers, you would need to express F(n) in terms of earlier values, not in terms of F(n). What cperciva is jokingly proposing is the equivalent of: naturals = naturals which is hardly helpful for computing the values. Lazy languages would not help you there.
- jibiki 17y ago> The precision to which you need to compute phi in order to compute the Nth Fibonacci number by exponentiation is the precision you'd obtain by computing the ratio of the Nth and (N-1)th Fibonacci numbers This seems true empirically, but when I do the math, it looks like you only need to calculate F_n up to about N/2 to make the ratio precise enough. (Since: |phi - (F_(n+1)/F_n)| < (F_n)^(-2) = phi^(-2n)/sqrt(5) (approximately) And, if |a|>>|b|, then: |(a+b)^n - a^n| = n a^(n-1) b (approximately) So our error just has to be < 1/(n phi^(n-1)), which should be true for roughly the N/2 convergent.) In either case, the algorithm is still basically quadratic.
- cperciva 17y agoThis seems true empirically, but when I do the math, it looks like you only need to calculate F_n up to about N/2 to make the ratio precise enough. True -- I oversimplified. But computing both F_n and F_{n+1} (as you need in order to compute the ratio) takes effectively the same amount of time as computing F_{2n}, so it still doesn't win you anything.
- RiderOfGiraffes 17y agoI think you've misunderstood me. You don't evaluate the CF for Phi, you compute with it directly. Gosper showed that it's possible to compute the CF of Phi^2 (say) directly, without evaluating the CF of Phi. Lather, rinse, repeat. The numbers involved are all similar in size to F(n) and so the complexity is linear. The number of multiplications and squarings is log(n), so I think the whole thing is sub-quadratic. Possibly it's n log(n) rather than linear. The point is that there are fast ways of doing these sorts of things, but they tend to be little-known and subtle. I've not gone into the details, there may be something I've missed.