December 17th, 2014, 2:27 pm
There's an approximation for the Fibonacci series that is a*b^N, where b is the golden ratio and a is some messy little constant. It's floating point, of course, but if one rounds the result to the nearest integer, it works for all values of N.One can compute the series b^1, b^2, b^4, b^8, .... up to the greatest power of 2 that is less than N in O(log(N)) time. And using the binary representation of N, multiply the appropriate subset of those power-of-2 terms.But it does require the rounding function! Of course, if one is using a standard computer processor with a fixed-resolution floating point datatype, then one can find a constant, c, such that induces just the right amount of round-off error to cause (x+c)-c = round(x). ------P.S. I googled a bit to see what the value of a was and found a page with an amazingly better formula that does not need round() even though it involves sums and products of irrational numbers.
Last edited by
Traden4Alpha on December 16th, 2014, 11:00 pm, edited 1 time in total.