5 ms·

Fib is a weird case because it's the poster child of dynamic programming. The challenge in this case is that each call spawns multiple recursive calls, and you'

by vitus 5y ago

Fib is a weird case because it's the poster child of dynamic programming. The challenge in this case is that each call spawns multiple recursive calls, and you're ultimately just adding 1's and 0's (so your runtime is comparable to the number you compute). Meanwhile, the DP / iterative approach understands the repeated structure of your recursion and can use that to eliminate redundant computation. Compare this to tail-recursive functions, where you can basically update the stack variables and jump back to the beginning of the function. (Note that you can approximately achieve the performance of the iterative solution by memoizing the results if your functions are pure and your input space is small, e.g. via @functools.cache, but you're paying for it with space, whereas the iterative solution understands when you can discard the intermediate results.)

falcor84 5y ago
>Fib is a weird case because it's the poster child of dynamic programming. It's actually got a closed-form solution, so finding the nth fib number is O(1) (assuming O(1) arithmetic). https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_e...
- tylerhou 5y ago
  Technically not correct, because when you get to large numbers you have to take into account that multiplication of those numbers takes O(nlogn) at best. Fib grows exponentially, so fib(n) takes O(n) bits to write. Python uses Karatsuba’s, which multiples two n-bit numbers in approximately n^1.59 time. Second, to compute the result accurately, you would have to compute many many digits of floating point precision with the closed form solution. That is more expensive than alternative solutions. The fastest freely available, practical implementation that doesn’t have floating point error is probably in libgmp, which uses fast powering (which can be derived from repeated matrix exponentiation). https://gmplib.org/manual/Fibonacci-Numbers-Algorithm https://gmplib.org/manual/Fibonacci-Numbers-Algorithm This takes something like O(multiplication * logn) time. With Karatsuba’s, approximately O(n^1.59 * logn). (Now I see you said assuming O(1) arithmetic after I wrote this post, but that’s not a reasonable assumption…)
  - patrick451 5y ago
    > Technically not correct, because when you get to large numbers you have to take into account that multiplication of those numbers takes O(nlogn) at best. This seems disingenuous. You could make the same claim about any algorithm that involves multiplication.
    - hansvm 5y ago
      Yes you could. For a fixed-width register machine you can go even further and say that there don't exist non-trivial constant time algorithms (it takes at least logarithmic time to read the entire input). This includes bread-and-butter classics like hashtables. In practice we usually hand-waive those details away because they don't apply on the domain of interest; rarely is somebody meaningfully exceeding a 64-bit space for their hashtables. You can formalize that a bit with something like the "Word RAM" model of computation -- assume that you have fixed width registers as wide as your inputs. For the Fibonacci sequence those details are a little harder to hand-waive away because of how quickly the output grows. As soon as the input is bigger than ~64 on a modern computer you'll start to see the effects of that linear runtime. On most clusters you'd have to stream Fib(1<<64) just to see all the bits, and it'd take ages. The reason that idea doesn't (usually) get applied to algorithms involving multiplication is because usually we're operating implicitly in a model that includes constant-time multiplication of "big enough" numbers. In cryptography and other fields operating on large integers though that analysis absolutely does come into play. The overarching theme is that reality is hard to capture both succinctly and accurately, and you want as simple of a model as possible that adequately describes the behavior you're curious about. Often that includes constant-time multiplication, but that'd seriously deceive you in an analysis of Fibonacci runtime.
    - tylerhou 5y ago
      No. Specifically, in this case we are multiplying exponentially large numbers meaning that they have linearly many bits with respect to the input, so you must account for the multiplication costs as they are not insignificant (e.g. O(n^1.59)). For normal computations, you usually deal with numbers that have logarithmically many bits wrt. the input, so the runtime is negligible (something like O(log^1.59(n)), so we can treat it as a constant. It's technically not a constant, but it's so close to the time to actually read the input (log(n) or n) that we can treat it as one.

by vitus 5y ago

falcor84 5y ago

>Fib is a weird case because it's the poster child of dynamic programming. It's actually got a closed-form solution, so finding the nth fib number is O(1) (assuming O(1) arithmetic). https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_e...

tylerhou 5y ago
Technically not correct, because when you get to large numbers you have to take into account that multiplication of those numbers takes O(nlogn) at best. Fib grows exponentially, so fib(n) takes O(n) bits to write. Python uses Karatsuba’s, which multiples two n-bit numbers in approximately n^1.59 time. Second, to compute the result accurately, you would have to compute many many digits of floating point precision with the closed form solution. That is more expensive than alternative solutions. The fastest freely available, practical implementation that doesn’t have floating point error is probably in libgmp, which uses fast powering (which can be derived from repeated matrix exponentiation). https://gmplib.org/manual/Fibonacci-Numbers-Algorithm https://gmplib.org/manual/Fibonacci-Numbers-Algorithm This takes something like O(multiplication * logn) time. With Karatsuba’s, approximately O(n^1.59 * logn). (Now I see you said assuming O(1) arithmetic after I wrote this post, but that’s not a reasonable assumption…)
- patrick451 5y ago
  > Technically not correct, because when you get to large numbers you have to take into account that multiplication of those numbers takes O(nlogn) at best. This seems disingenuous. You could make the same claim about any algorithm that involves multiplication.
  - hansvm 5y ago
    Yes you could. For a fixed-width register machine you can go even further and say that there don't exist non-trivial constant time algorithms (it takes at least logarithmic time to read the entire input). This includes bread-and-butter classics like hashtables. In practice we usually hand-waive those details away because they don't apply on the domain of interest; rarely is somebody meaningfully exceeding a 64-bit space for their hashtables. You can formalize that a bit with something like the "Word RAM" model of computation -- assume that you have fixed width registers as wide as your inputs. For the Fibonacci sequence those details are a little harder to hand-waive away because of how quickly the output grows. As soon as the input is bigger than ~64 on a modern computer you'll start to see the effects of that linear runtime. On most clusters you'd have to stream Fib(1<<64) just to see all the bits, and it'd take ages. The reason that idea doesn't (usually) get applied to algorithms involving multiplication is because usually we're operating implicitly in a model that includes constant-time multiplication of "big enough" numbers. In cryptography and other fields operating on large integers though that analysis absolutely does come into play. The overarching theme is that reality is hard to capture both succinctly and accurately, and you want as simple of a model as possible that adequately describes the behavior you're curious about. Often that includes constant-time multiplication, but that'd seriously deceive you in an analysis of Fibonacci runtime.
  - tylerhou 5y ago
    No. Specifically, in this case we are multiplying exponentially large numbers meaning that they have linearly many bits with respect to the input, so you must account for the multiplication costs as they are not insignificant (e.g. O(n^1.59)). For normal computations, you usually deal with numbers that have logarithmically many bits wrt. the input, so the runtime is negligible (something like O(log^1.59(n)), so we can treat it as a constant. It's technically not a constant, but it's so close to the time to actually read the input (log(n) or n) that we can treat it as one.