 Posts: 23951
Joined: September 20th, 2002, 8:30 pm

### Compute the Nth Fibonacci nr using only + and *

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. Posts: 23951
Joined: September 20th, 2002, 8:30 pm

### Compute the Nth Fibonacci nr using only + and *

LOL! You are pulling a Cuch on this one by adding the integer constraint! Posts: 23951
Joined: September 20th, 2002, 8:30 pm

### Compute the Nth Fibonacci nr using only + and *

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!) MS5
Posts: 54
Joined: May 14th, 2010, 5:00 pm

### Compute the Nth Fibonacci nr using only + and *

$$F_{2n-1}= F^2_n+F_{n-1}^2\\F_{2n} = (2F_{n-1}+F_n)F_n$$ katastrofa
Posts: 9327
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

### Compute the Nth Fibonacci nr using only + and *

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: August 16th, 2007, 5:36 am
Location: Alpha Centauri

### Compute the Nth Fibonacci nr using only + and * MS5
Posts: 54
Joined: May 14th, 2010, 5:00 pm

### Compute the Nth Fibonacci nr using only + and *

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: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Compute the Nth Fibonacci nr using only + and *

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: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Compute the Nth Fibonacci nr using only + and *

==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.  