Performance Zone is brought to you in partnership with:

Antonin Januska is a web developer, designer, writer, life enthusiast, and more. Shedding the third person for a moment, I would like to tell you about who I am. I am a freelancer with extensive background in business, marketing, advertising, and developing products. I have worked with many different media and advertising agencies as well as ambitious individuals hoping to elevate their small businesses above their competitors. From furniture companies, to software development companies, I’ve made websites for businesses in just about every field. Antonin has posted 16 posts at DZone. You can read more from them at their website. View Full User Profile

What Fibonacci taught me about programming

03.14.2014
| 16915 views |
  • submit to reddit

I originally wanted to write this neat piece on how solving the “get a number from the Fibonacci sequence” problem can teach YOU a lot but over the past year, I’ve realized that programming is such a personal experience that I believe I’d do you injustice by preaching and schooling you.

Instead, I’d like to focus on my own experience with it.

A few weeks ago, I was solving the Fibonacci sequence problem:

Given an index, return the correct number from the Fibonacci sequence.

I tried different approaches, looked up how others have done it and learn a few awesome things.

Recursion is badass but can be misleading

One solution that I’ve seen was the recursive one. Recursion to me has always been magic. Partially because you have to approach a problem with a certain mindset to be able to use recursion. And I rarely ever find problems that require that mindset.

Anyways, so I found a solution and just looking at it, I thought that it was the best thing ever.

First, let me show you the functional (mathematically functional) representation of Fibonacci:

F(n) = F(n-1) + F(n-2)

Basically, each Fibonacci number is equal to the sum of its two predecessors. The recursive solution looks very much like the mathematical representation:

function fibRec(i) {
  if (i < 2) {
    return i;
  } else {
    return ( fibRec(i-1) + fibRec(i-2));
  }
}

I thought to myself, “This is perfect! So simple, and it describes itself! This MUST be the perfect solution!” but it’s not. Look at what happens when you run this neat recursive function:

fibonacci-recursion

As you can see, the function gets recursively worse in terms of performance. We’re exponentially calculating the same equation. I’d call this the “near-infinite loop”. Because we calculate and recalculate the same problem over and over and over. The larger our i gets, the more exponentially worse the recursion gets.

So I reminded myself of an old saying:

just because it looks right, it doesn’t mean it is.

I learned that not every problem that looks like a recursion-solvable should be solved with recursion. Technically, this is a prime example of where recursion mirrors the nature of the problem but is not a good solution.

Then comes solving programmatically (or Naive)

Every problem out there has an inelegant “naive” solution. I say “naive” because it’s seemingly inefficient. For instance, the solution to Fibonacci using plain programming is this:

//programmatically
function fibProg(i) {
  var a = 0;
  var b = 0;
  var c = 0;

  for(var d = 0; d < i+1; d++) {
    if(d === 1) {
      c = 1;
    } else {
      c = a+b;
    }
    a = b;
    b = c;
  }

  return c;
}

As you can see, we have to count up from 0 all the way up to the index every single time. It’s terribly inefficient. Isn’t there a way to just “skip” to the correct number instead of this iterative approach? No, not with just programming. However, the solution is performant enough that you can leave it at that. No need to go further.

The recursion solution could result in maximum call stack errors, overflows, and what have you. This solution won’t and it will work efficiently up to some arbitrary high number.

The Mathematical Solution

Being a former math major, I remembered that there is a Fibonacci solving formula based on the golden ratio. A quick look up in Wikipedia resulted in a sweetly simple equation:

fib-equation

I decided to plug it into a function and create a fibMath function for a solution:

function fibMath(i) {
  var sqrtFive = Math.sqrt(5);
  var firstHalf = 0;
  var secondHalf = 0;

  firstHalf = 1 / sqrtFive * Math.pow( ( ( 1 + sqrtFive ) / 2), i);
  secondHalf = 1 / sqrtFive * Math.pow( ( (1 - sqrtFive ) / 2 ), i);
  return Math.round(firstHalf - secondHalf);
}

It’s a pretty neat but completely un-understandable function for a programmer. However, the performance is staggering.

I love how math can cut through problems like butter through innovative formulas. I was taken aback and realized that there are things about programming on the fundamental, mathematical level that I may not fully understand but allow us to work at the speeds we work at.

Note: Someone pointed out to me that the Math.round() function will eventually end up with incorrect solutions due to the floating point error and similar problems. There are some workarounds if you need to be precise and will be using this function out in the real world.

The Tests

I decided to test all of the solutions with JSPerf, a cool little app that employs Benchmark.js for benchmarking.

I set up as fair of a test as I could and put all three solutions to work.

First up is a benchmark that allows fibRec (the recursive solution) to be used. I found that the maximum call error pops up in the range of 50 or above (perhaps even lower). So I started with getting the 20th index.

Check it out. Here are the results for my computer:

fib-benchmark-1

To further test the programmatical vs mathematical solutions, I picked a higher index to compute in a “hardcore mode”.

Check that out and see the difference:

fib-benchmark-2

Note that this hardcore mode tests for the index of 54320 instead of 20. What’s interesting is that while the mathematical solution is much MORE performant, the programmatical solution works just fine. Unless I’m directly dealing with math solutions, there’s no need to go nuclear and convert functions into mathematical representations (although, that would be a neat project).

I believe that game programming relies on mathematical formulas due to these difference, however, they do actually run these equations several million times a second.

So I learned about optimization

The difference between the programming solution and the mathematical solution reminds me of the difference of running native assembly code and something like PHP. The math solution is like magic, and so is assembly (sometimes). But it’s not practical in most cases, in terms of debugging, understanding, and changing.

The entire process taught me that it’s important to avoid potential bottlenecks like the first solution but it’s just as important to not get hung-up at the performance of solutions like the programming solution. I thought it was going to be slow but I was wrong. At 2000 ops/sec with a very high look up index, there was nothing to worry about whatsoever. That’s a performant solution.

Could I do better? Yeah. And I did, the mathematical solution gave me performance several times over the programming one. And if I was using Fibonacci or other mathematical concepts out in the real world, I would have learned my lesson to use the smart way and not the “manual” way (manual, as in, the computer manually computes a solution rather than cutting straight through to the answer).

The downside to the math solution is that it’s not often available for most real-world problems (outside of video gaming and 3D). The non-math solution is good enough though and should not be dismissed.

On the other hand, a less performant but understandable/maintanable solution is much better than a very performant yet illegible is a trap that should be avoided.

I don’t know if that makes sense, but it was an interesting exercise.

Published at DZone with permission of its author, Antonin Januska.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Peter Huber replied on Sat, 2014/03/15 - 3:30am

Some comments:

1.) You could actually factor out the constant terms that you compute over and over again in your mathy solution. only the power-part depends on n. So even more performance when taking many runs...

2.) The mathy solution is in no way unreadable or less maintainable. you just add a comment to your code, that contains the link to wikipedia. And if the wikipedia article says " to the power of n" then let's please name parameters according to wikipedia...In my opinion your way of argumentation is not completely right, you say avoid illegible sollution, but illegible to whom? You allways have to have capable staff in the context of the solution, it's no way we allways chose the lowest standard just to maintain a notion of legibility that is wrong in my eyes. But in a sence you're actually right: Even my past me knew things that my present me has problems to figure out again ;-)

3.) Math.round really? Guess you found out about some fallacy in programming with floats. Floats are NEVER accurate. even the number 0.1 is not mappable to a IEEE float, it only seems like...For precise computations Java has the BigNumber-Types...

4.) The findings of your articel regarding programming is for me:

a.) Know how to ask google for an answer to your problem (this is btw a key competence for programmers today). And do ask google *before* you start programming.

b.) ...be abel to pick the right answer from the 1st or 2nd page of google results, even if it's "oh there's already a lib that has optimized solution to my problem" ;-)

c.) Know how to do performance test and do them right from the start of your programming effort.

Lund Wolfe replied on Sat, 2014/03/15 - 5:28pm

It looks like the efficiency is about 2 ** n, so for nontrivial n you would want a shortcut.

The simplest code would be to just calculate from the base f(n), 0 and 1, or 1 and 2 until you reach the desired f(n) value.  This wouldn't repeat previous calculations, at least, and efficiency of n may well be good enough.

You could also use the fact that the ratio approaches the golden ratio/section so you could use that in a power math function.  It would be approximate, though, which might not be good enough.

What you have is about as simple as it gets.  It only takes as long as two power function calls.

Zakaria Drissi replied on Wed, 2014/03/19 - 5:49pm

 The recursive solution can be improved by caching the values, by using an array or a map, there will be some overhead but it's way efficient than the classical recursive.

Antonin Januska replied on Fri, 2014/03/21 - 3:58pm in response to: Zakaria Drissi

Yep. So, in the original version of my article (before I rewrote it), I mentioned that I wanted to use cache-free methods. Outside of that, yes, using an array or a map will significantly improve the speed of the application. It will, however, increase the memory footprint.

Dean Phillips replied on Wed, 2014/04/02 - 10:37am in response to: Peter Huber

Good points, although his contention that 'good enough' is exactly that is valid.  I would be curious to see the results with the constant  (1 / sqrt(5)) as a constant and only calculating the 2nd half for n where it mattered (probably n < 10?).   I would expect the 2nd optimization to make more difference than the first.

Jerome Sturt replied on Thu, 2014/04/17 - 12:10am

Thanks for sharing such a good information...



JAVA Training Institutes in Chennai 

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.