_vou1q
Last Updated: February 25, 2016
·
1.391K
· haiqus
Mypic

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
end

With 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

Say Thanks
Respond

8 Responses
Add your response

6592

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!

over 1 year ago ·
6598
Mypic

@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,

49922546054780146353198579531352153533212840109029466994098142197617303359523104269471455390562835412104406019654730583800904132982935807202575490044075132631203284854890505808877430837618493577512703453928379390874730829906652067545822236147772760444400628059249610784412153766674534014113720760876471943168

which 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 ).

over 1 year ago ·
6603

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.

over 1 year ago ·
6604
Mypic

@antonov nice!

Keep the advice coming everyone; I'll refactor over the weekend -- Thanks!

over 1 year ago ·
6624

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.

over 1 year ago ·
6626
Mypic

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.

over 1 year ago ·
6631
2c7cd414f3bbfed489e6bddb7760174b

very interesting, except it's spelled "Fibonacci" :)

over 1 year ago ·
6634
Mypic

@ludwinas corrected, thanks

over 1 year ago ·