Serving the Quantitative Finance Community

 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Compute the Nth Fibonacci nr using only + and *

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

Compute the Nth Fibonacci nr using only + and *

December 17th, 2014, 3:22 pm

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

Compute the Nth Fibonacci nr using only + and *

December 17th, 2014, 3:53 pm

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

Compute the Nth Fibonacci nr using only + and *

December 17th, 2014, 6:20 pm

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

Compute the Nth Fibonacci nr using only + and *

December 17th, 2014, 7:49 pm

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.
 
User avatar
katastrofa
Posts: 7440
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Compute the Nth Fibonacci nr using only + and *

December 17th, 2014, 10:01 pm

 
User avatar
MS5
Posts: 2
Joined: May 14th, 2010, 5:00 pm

Compute the Nth Fibonacci nr using only + and *

December 17th, 2014, 10:36 pm

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[$].
 
User avatar
Cuchulainn
Posts: 20252
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Compute the Nth Fibonacci nr using only + and *

February 3rd, 2015, 2:32 pm

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.
 
User avatar
Cuchulainn
Posts: 20252
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Compute the Nth Fibonacci nr using only + and *

February 3rd, 2015, 3:09 pm

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