A Better Fibonacci
improvements can be found in this tip
The Fibonacci series. You know don't know what it is until you understand why this works:
PHI = 1.6180339887498948482045868
fib = lambda do |n|
(
( PHI**n - ( 1 - PHI )**n ) /
Math.sqrt(5)
).
floor
endWith this Ruby code, simply call fib[n] where n is any number to get the corresponding element of the (classical) Fibonacci series.
Why does this work? Because the constant PHI is itself recursively defined. The lesson here is that if you can isolate the recursion in a constant value, you can write a non-recursive mathematical expression.
(The difficulty, of course, is choosing the proper constant. But such is the art of mathematical analysis!)
NOTE: grab the first 2000 Fibonacci numbers here: http://oeis.org/A000045/b000045.txt
Written by Jared Davis
Related protips
8 Responses
Hi Jared,
Very interesting. But this is an approximation, right? Is there a value of n (maybe very big) from which you start getting wrong results?
Thanks!
@alfre2v Yes, that's absolutely correct, and for two reasons. 1) The value of PHI used here is a standard Ruby Float, where as the mathematical constant is transcendental (infinite, non-repeating decimal). 2) Not all real numbers are representable by floating point numbers of any size.
The largest Fibonnaci number discoverable by this code is n = 1474,
49922546054780146353198579531352153533212840109029466994098142197617303359523104269471455390562835412104406019654730583800904132982935807202575490044075132631203284854890505808877430837618493577512703453928379390874730829906652067545822236147772760444400628059249610784412153766674534014113720760876471943168which does not match the known value for the 1474th Fibonnaci.
I'm going to give others a chance to calculate where the computed and actual series diverge; but if someone doesn't I'll post the answer ( finding the answer shouldn't take more than a few minutes ).
Hi Jared,
nice to show this in Coderwall.
BTW, you can do better: from some point on, the formula is still simpler since (1-phi)^n/sqrt(5) becomes strictly less than 0.5 in absolute value, and from that point on you can compute F_n as the nearest integer to phi^n/sqrt(5), i.e., using the round function instead of floor. This is true because the original formula yields an integer.
@antonov nice!
Keep the advice coming everyone; I'll refactor over the weekend -- Thanks!
Jared - Thanks so much for posting this. I know the two standard Fibo algorithms but I'm looking forward to thinking about this. I appreciate antonov's point about .5 and floor().
I've been interested in Fib.. since 7th grade, more years ago than I like to count.
I'll don't know Ruby but will research it. (Mostly I need to find out what lambda means in the Ruby context). In the meantime does anyone have a C/C++ solution. If not I'll post one when I decipher the Ruby code.
Meanwhile, as a card-carrying member of the grammar police I feel compelled to point out it is Fibonacci 1 n, 2 c's
http://en.wikipedia.org/wiki/Fibonacci
and that PHI is the so-called Golden Ratio - the limit approached by the ratio of any two consecutive Fibo numbers - and supposedly the ratio of height to width of the Parthenon.
Thanks for the comments, @davidka !
Try reading http://www.skorks.com/2010/05/ruby-procs-and-lambdas-and-the-difference-between-them/ for a better explanation of Ruby's lambda's than I'm able to provide.
If you're interested in reading more about PHI, I recommend Mario Livio's The Golden Ratio for starters. It's been a long time since I've read it, but I recall the book having a good overview of the number and it's history -- including the supposed Parthenon interpretation.
very interesting, except it's spelled "Fibonacci" :)
@ludwinas corrected, thanks
Have a fresh tip? Share with Coderwall community!
