4

There are many instances of software developmet where we seem to solve problems differently than from a mathematical perspective. For instance, consider the classical example of calculating Fibonacci numbers. Why do we implement Fibonacci numbers naively using its definition instead of using the explicit formula https://brilliant.org/discussions/thread/the-explicit-formula-for-fibonacci-sequence/. Is there a reason why this is a standard? Should I be conforming to the "standards" of doing it this way in practice? In interviews?

Another class of examples would be optimization problems. Why do we use Dijksttra's algorithm to compute the shortest path as opposed to translating the graph into an integer program and solving that instead? Similarly for the Knapsack problem, why is dynamic programming favored over integer programing techniques developed in mathematical optimization?

11
  • 10
    In what context? If you're writing an actual production app that needs Fibonacci numbers for some reason (where a numerical solution probably makes your code more efficient), that's very different to if you're doing an exercise to learn about recursion or memoization (where a numerical solution is no use at all).
    – jonrsharpe
    Commented Sep 23, 2020 at 20:09
  • 5
    People "implementing Fibonacci numbers" 99.99% of the time are doing it for teaching/learning or mental excersize. People that are using fibonacci numbers for Real Work™, you can be certain they know all abut Binet's formula. Fibonacci examples from education are far more visible than from people writing code for vending machines, that's why you have an observational bias.
    – whatsisname
    Commented Sep 23, 2020 at 20:11
  • 4
    The "classical" example of Fibonacci in programming is to demonstrate recursion. I would think a non-recursive algorithm would make for a rather ineffective substitute. Now, if you're looking at an implementation intended for production work, you might have a good point there, but without a specific example, it's going to be hard for us to answer, and even with an example, you'll probably get a better answer from the actual author.
    – 8bittree
    Commented Sep 23, 2020 at 20:13
  • 8
    You wouldn't even use Binet's formula for most "Real Work™" . fib(94) overflows a UInt64. The most performant bet is to pre-compute the first 94 elements (don't forget 0!), shove them a 94-element array, and use a single constant-time index into the array to obtain your results. Only needs 6,016 bytes, which is probably less space than the machine code for implementing Binet's formula, which would also be slower (FP instructions have higher latency, and you waste time in Double ⇄ UInt64 conversions).
    – Alexander
    Commented Sep 23, 2020 at 20:34
  • 1
    @coderhk: I'd ask what aspects they are interested in. I very well may implement it the inefficient naive way then explain the shortcomings of doing it that way, if that's what the interviewer is interested in.
    – whatsisname
    Commented Sep 23, 2020 at 21:01

3 Answers 3

Reset to default
17

Why do we implement Fibonacci numbers naively using its definition instead of using the explicit formula https://brilliant.org/discussions/thread/the-explicit-formula-for-fibonacci-sequence/.

We don't. No programmer ever computes Fibonacci numbers. Not recursively. Not iteratively. Not with Binet's Formula.

(Yes, I know. There are a small number of programmers who actually do need to work with Fibonacci numbers. I am assuming that if you are one of those programmers, you understand that absolute statements are never fully true.)

However, every programmer learns recursion, tail-recursion, iteration, and memoization, and the recursive definition of the Fibonacci numbers is something everybody knows from high school, is simple, small, easy to understand, and can be used to demonstrate all four of those concepts.

Why do we use Dijksttra's algorithm to compute the shortest path as opposed to translating the graph into an integer program and solving that instead?

Integer Programming is NP-complete, which means we don't know any efficient algorithm for solving it, and we in fact strongly believe that there cannot be an efficient algorithm.

Dijkstra's Algorithm, OTOH is Θ(|E| + |V|log|V|) when implemented optimally with a Fibonacci heap.

So, at least asymptotically, Diskstra's Algorithm is simply faster.

Note also that often we do not use Dijkstra's Algorithm but rather A* or an A*-variant.

Similarly for the Knapsack problem, why is dynamic programming favored over integer programing techniques developed in mathematical optimization?

There is a dynamic programming algorithm which solves Knapsack in pseudo-polynomial time, while there is no such algorithm for IP. So, again, the algorithm is simply "faster" (for a specific definition of "faster").

3

Regarding the Fibonacci formula:

To implement it, you need floating-point arithmetic. A quick test with Java double-precision shows that from fibonacci(71) on, the results are off by one when rounding to the next integer. And double-precision typically is the best you get without special libraries.

While it's thrilling to have a closed formula for Fibonacci numbers, if you can only use it up to fibonacci(70), a classical iterative or recursive implementation is superior.

And I haven't even checked performance. I bet in most cases up to fibonacci(70), the classical implementation will outperform the closed-formula one.

1

Another class of examples would be optimization problems. Why do we use Dijksttra's algorithm to compute the shortest path as opposed to translating the graph into an integer program and solving that instead? Similarly for the Knapsack problem, why is dynamic programming favored over integer programing techniques developed in mathematical optimization?

Why is special problem not solved with the method for more general problem?

Formulating it like this makes it reasonably clear. If the algorithm for the general problem (integer program) was already the best there is for ALL integer programs, then you would be right to ask that question. It just so happens that if an integer program is of a specific form, better algorithms exist than the general one. The special problem contains more information so a better algorithm for instances of special problem can be created.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.