3 ms·

The suggested "efficient" solutions for fibonacci and factorial only work on small inputs as they return the result as a long int. For these small instances the

by tromp 4y ago

The suggested "efficient" solutions for fibonacci and factorial only work on small inputs as they return the result as a long int. For these small instances the use of floating point functions like pow, sqrt, and exp is likely less efficient than a simple iterative solution. For larger instances using bignums as output, floating point computations do not even offer an alternative. It's true though that mathematics offers faster integer only (e.g. matrix based) methods of computing fibonacci.

zozbot234 4y ago
The matrix based method for Fib can be understood as applying the closed-form solution over Q(sqrt5). OP seems to miss this point.
- mschoenert 4y ago
  My thoughts at this point in the original article was: Well - if you want to demonstrate how mathematics helps here, then you should mention that computing the n-th fibonnaci number can be computed as the n-th power of the matrix [[1,0],[1,1]], and that the most efficient way to compute powers (in any associative domain) is the repeated squaring algorithm.
  - bibanez 4y ago
    There are many ways to obtain the formula mentioned in the article. One of them is by diagonalizing this matrix and then applying exponentiation. How can another algorithm be better than constant time in the most general case?
    - mschoenert 4y ago
      No - there isn't really an O(1) solution. And the reason is that the Fibonacci numbers grow without limit. So there can't be an O(1) algorithm - even just writing down the answer takes O(N) - because the answer has O(N) bits. Concretely Fibonacci(1480) is the largest Fibonacci number that fits into a double. So for higher Fibonacci numbers you need to compute this with arbitrary size integers (or floats). And then look at it in terms of bit complexity (i.e. the time to compute a product grows with the size of the integers). Put differently. The "constant time" algorithm only works for N up to 1480. And if you limit N, then it doesn't really make sense to talk about the asymptotic complexity. I believe the optimal algorithm is to compute the Fibonacci number by computing the N-th power of the matrix [[1,1],[1,0]], and compute the power using the repeated squaring algorithm. There are alternative formulations of that using identities for Fibonacci or Lucas numbers, but those identities basically correspond to squaring the matrix. If you really want the asymptotically fastest algorithm you must use the fastest algorithm for integer multiplication (Harvey and van der Hoeven’s). But even with the naive multiplication for arbitrary size integers you can compute Fibonacci(1000000) - which is a number with more than 200'000 digits - in less than a second. ;-)
      - anthk 4y ago
        Well, with Scheme, the difference on computing fib(n) recursively vs the iterative way shows up really fast.
BeetleB 4y ago
Indeed, I kind of stopped reading the article there. The other issue is his picking on Lisp programmers with this example. If you open books on programming using C, it almost always will have either the iterative or the recursive solution - not the closed for one. So why is he picking on Lisp programmers in particular?

by tromp 4y ago

zozbot234 4y ago

The matrix based method for Fib can be understood as applying the closed-form solution over Q(sqrt5). OP seems to miss this point.

mschoenert 4y ago
My thoughts at this point in the original article was: Well - if you want to demonstrate how mathematics helps here, then you should mention that computing the n-th fibonnaci number can be computed as the n-th power of the matrix [[1,0],[1,1]], and that the most efficient way to compute powers (in any associative domain) is the repeated squaring algorithm.
- bibanez 4y ago
  There are many ways to obtain the formula mentioned in the article. One of them is by diagonalizing this matrix and then applying exponentiation. How can another algorithm be better than constant time in the most general case?
  - mschoenert 4y ago
    No - there isn't really an O(1) solution. And the reason is that the Fibonacci numbers grow without limit. So there can't be an O(1) algorithm - even just writing down the answer takes O(N) - because the answer has O(N) bits. Concretely Fibonacci(1480) is the largest Fibonacci number that fits into a double. So for higher Fibonacci numbers you need to compute this with arbitrary size integers (or floats). And then look at it in terms of bit complexity (i.e. the time to compute a product grows with the size of the integers). Put differently. The "constant time" algorithm only works for N up to 1480. And if you limit N, then it doesn't really make sense to talk about the asymptotic complexity. I believe the optimal algorithm is to compute the Fibonacci number by computing the N-th power of the matrix [[1,1],[1,0]], and compute the power using the repeated squaring algorithm. There are alternative formulations of that using identities for Fibonacci or Lucas numbers, but those identities basically correspond to squaring the matrix. If you really want the asymptotically fastest algorithm you must use the fastest algorithm for integer multiplication (Harvey and van der Hoeven’s). But even with the naive multiplication for arbitrary size integers you can compute Fibonacci(1000000) - which is a number with more than 200'000 digits - in less than a second. ;-)
    - anthk 4y ago
      Well, with Scheme, the difference on computing fib(n) recursively vs the iterative way shows up really fast.

BeetleB 4y ago

Indeed, I kind of stopped reading the article there. The other issue is his picking on Lisp programmers with this example. If you open books on programming using C, it almost always will have either the iterative or the recursive solution - not the closed for one. So why is he picking on Lisp programmers in particular?