- Traden4Alpha
**Posts:**23951**Joined:**

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.

- Traden4Alpha
**Posts:**23951**Joined:**

LOL! You are pulling a Cuch on this one by adding the integer constraint!

- Traden4Alpha
**Posts:**23951**Joined:**

The Golden ratio would be a pre-computed constant using a Taylor series for sqrt(1+x), x = 0.25, and multiply the result by 2. It gets computed once and can then be used an arbitrary number of times for arbitrary values of N. But it would seem that you have different answer in mind. (ponder ponder ponder!)

$$F_{2n-1}= F^2_n+F_{n-1}^2\\F_{2n} = (2F_{n-1}+F_n)F_n$$

- katastrofa
**Posts:**9327**Joined:****Location:**Alpha Centauri

QuoteOriginally posted by: outrunVery nice, even better then what I had found!The method I found uses powers (that can be computed in Log(N)) of the Fibonacci Q matrix[$]Q^n = \left(\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}\right)^n =\left( \begin{matrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{matrix}\right)[$]I guess the method simply comes from fact that the Fibonacci number can be represented as [$]F^n = \left(\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}\right)^{n-2}\left( \begin{matrix} F_1\\ F_0 \end{matrix}\right)[$](F_0 = 0). Forgive my anal-retentiveness, outrun.

Last edited by katastrofa on December 16th, 2014, 11:00 pm, edited 1 time in total.

- katastrofa
**Posts:**9327**Joined:****Location:**Alpha Centauri

QuoteOriginally posted by: outrunVery nice, even better then what I had found!The method I found uses powers (that can be computed in Log(N)) of the Fibonacci Q matrix[$]Q^n = \left(\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}\right)^n =\left( \begin{matrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{matrix}\right)[$]That's quite right, and you just go on to use [$]Q^nQ^m=Q^{n+m}[$] and set [$]n=m[$].

- Cuchulainn
**Posts:**62391**Joined:****Location:**Amsterdam-
**Contact:**

QuoteOriginally posted by: Traden4AlphaLOL! You are pulling a Cuch on this one by adding the integer constraint! ;)You called? It's a silly constraint? Not really. It is a non-issue.Why not1. Compute the characteristic equation of the Fibonacci difference scheme; roots are m1 and m22. Solution F_n = c1 m1 ^n + c2 m2^n (c1 = 1 = -c2)3. m^n using Chandah-sutra (O(nlogn?) whateveryes?

Last edited by Cuchulainn on February 2nd, 2015, 11:00 pm, edited 1 time in total.

- Cuchulainn
**Posts:**62391**Joined:****Location:**Amsterdam-
**Contact:**

==On the other hand...Maybe an exact expansion of c1m1^n + c2m2^n to kill off terms. You see no sqrt(5) appears and *should* not appear for general n. F_n = c1 m1^n + c2 m2^n = (m1^n - m2^n)/sqrt(5) (1)LHS is integer, so RHS must be integer as well. Now all you have to do is prove there are only powers of sqrt(5) in (m1^n - m2^n). ==I tested it up to n = 2 and n =3 and n = 4. Can you prove this by induction (place Wilmott emoticon here). You can also probably compute it using binomial coefficients.QED, almost surely(?)

Last edited by Cuchulainn on February 2nd, 2015, 11:00 pm, edited 1 time in total.

GZIP: On