3 ms·

There are many ways to get to Binet's Formula from the recurrence relation. But it gives wrong result for large values of N. I have also written on the same top

by codepie 12y ago

There are many ways to get to Binet's Formula from the recurrence relation. But it gives wrong result for large values of N. I have also written on the same topic http://www.dipkakwani.appspot.com/5651124426113024 http://www.dipkakwani.appspot.com/5651124426113024

deckar01 12y ago
> Binet's Formula ... gives wrong result for large values of N [due to the fixed precision estimations of the irrationals]. Sounds like a job for an arbitrary precision decimal library and an estimation of the precision the irrationals need to minimize the error at N. Do you know of any attempts to overcome the error of computing with irrational numbers?
- codepie 12y ago
  I think this might provide you a relevant answer : http://stackoverflow.com/questions/9645193/calculating-fibonacci-number-accurately-in-c http://stackoverflow.com/questions/9645193/calculating-fibon...
  - deckar01 12y ago
    > arbitrary precision libraries often come with their own optimised Fibonacci functions. I will check out some of these implementations. http://cs.stackexchange.com/questions/7145/calculating-binets-formula-for-fibonacci-numbers-with-arbitrary-precision http://cs.stackexchange.com/questions/7145/calculating-binet... This post suggests that the matrix solution is desirable. I wonder if the complexity of performing exponentiation on high precision values would ever overtake a logarithmic solution.
- drostie 12y ago
  One topic which might be interesting here is a continued-fraction library. The golden ratio has a nice representation as the infinite stream [1, 1, 1, 1, ...] because it is 1 + 1/(1 + 1/(1 + ...)), a fact which also makes it the most irrational number. If continued-fraction algorithms have developed to the point where you can do arbitrary exponentiations of a continued fraction, then you can just calculate the result to one decimal place and round and you'll get the right result.
- TheLoneWolfling 12y ago
  By the time you do that it'll be slower than just using the matrix exponentiation form.
- TheLoneWolfling 12y ago
  Ball arithmetic is one way to work with irrationals. Effectively you represent numbers explicitly as a += b.

by codepie 12y ago

deckar01 12y ago

> Binet's Formula ... gives wrong result for large values of N [due to the fixed precision estimations of the irrationals]. Sounds like a job for an arbitrary precision decimal library and an estimation of the precision the irrationals need to minimize the error at N. Do you know of any attempts to overcome the error of computing with irrational numbers?

codepie 12y ago
I think this might provide you a relevant answer : http://stackoverflow.com/questions/9645193/calculating-fibonacci-number-accurately-in-c http://stackoverflow.com/questions/9645193/calculating-fibon...
- deckar01 12y ago
  > arbitrary precision libraries often come with their own optimised Fibonacci functions. I will check out some of these implementations. http://cs.stackexchange.com/questions/7145/calculating-binets-formula-for-fibonacci-numbers-with-arbitrary-precision http://cs.stackexchange.com/questions/7145/calculating-binet... This post suggests that the matrix solution is desirable. I wonder if the complexity of performing exponentiation on high precision values would ever overtake a logarithmic solution.
drostie 12y ago
One topic which might be interesting here is a continued-fraction library. The golden ratio has a nice representation as the infinite stream [1, 1, 1, 1, ...] because it is 1 + 1/(1 + 1/(1 + ...)), a fact which also makes it the most irrational number. If continued-fraction algorithms have developed to the point where you can do arbitrary exponentiations of a continued fraction, then you can just calculate the result to one decimal place and round and you'll get the right result.
TheLoneWolfling 12y ago
By the time you do that it'll be slower than just using the matrix exponentiation form.
TheLoneWolfling 12y ago
Ball arithmetic is one way to work with irrationals. Effectively you represent numbers explicitly as a += b.