4 ms·

Fibonacci is better memoized because it changes an exponential time algorithm into a linear time one, but I don't see why factorial would be better memoized.

by tome 5y ago

seanhunter 5y ago
If you memoize you turn either of them into constant time. So it's an improvement to factorial (albeit less dramatic) and in practise if you later on reach for a higher factorial than you have previously calculated you don't need to start from scratch which is a real-world speedup although the O is still linear. That said obviously the decision of whether to memoize depends on whether the function is going to be called more than once. If you're not calling fibbonacci more than once there is a closed form solution which is better for many input values than any of these methods.
- thaumasiotes 5y ago
  > If you're not calling fibbonacci more than once there is a closed form solution which is better for many input values than any of these methods. I don't think that's true; you're pretty much always better off calculating Fibonacci numbers by starting from F_0 and counting up than by using the closed-form solution.
  - tome 5y ago
    Are you sure? The closed form solution can be evaluated in logarithmic time whereas counting up takes linear time.
    - thaumasiotes 5y ago
      Here's an article talking about it: https://towardsdatascience.com/why-is-the-closed-form-of-the-fibonacci-sequence-not-used-in-competitive-programming-674b805da341 https://towardsdatascience.com/why-is-the-closed-form-of-the... It covers a couple of points (all of this is me summarizing the article I just linked; I'm not an expert in numeric computing): - The closed-form expression for Fibonacci numbers involves an irrational number. But we can't do computations on irrational numbers; we're stuck with rational approximations. (Such as IEEE floating point.) Since computing an early Fibonacci number involves raising ϕ to a high exponent, the error involved in giving ϕ a finite representation rapidly compounds, corrupting the result. (According to this article, errors will become visible after F_100. That's quickly enough that you'd be justified in just having a lookup table for the first 100 Fibonacci numbers, which would be much faster than computing them as needed.) - You can represent the Fibonacci recurrence relation directly in matrix form. This is just the counting-up method written down a different way. Each Fibonacci number is the product of the constant matrix [[1 1] [1 0]] with the vector consisting of the previous two Fibonacci numbers. - You can exponentiate the matrix n-1 times to get a matrix that converts F_1 and F_0 (known in advance) into F_n and F_{n-1}. This is just as amenable to the shortcuts involved in calculating large exponents of a value as exponentiating ϕ is. But it's exact integer arithmetic.
      - tome 5y ago
        > You can exponentiate the matrix n-1 times to get a matrix that converts F_1 and F_0 (known in advance) into F_n and F_{n-1}. This is just as amenable to the shortcuts involved in calculating large exponents of a value as exponentiating ϕ is. But it's exact integer arithmetic. Right, and repeated squaring can give you the answer to the exponentiation in logarithmic time.
- gmfawcett 5y ago
  > If you memoize you turn either of them into constant time. At the risk of stumbling into the No True Memoization fallacy, I wouldn't consider that memoizing -- at least not in the dynamic programming sense. To get O(1), you're not temporarily tabling the results during a single run of the algorithm; rather you're building a semi-permanent database of answers and (effectively, in an amortized sense) discarding the algorithm altogether. I think that's formally known as the "just Google it" approach to optimization. :) From a DP perspective you can get O(N) from memoization on open-form Fibonacci, and no gain on open-form factorial, because the lookup table is ephemeral.
  - seanhunter 5y ago
    This is probably the most "hackernews" conversation I've ever had but as far as I've ever seen the term used, "memoization" is not restricted to temporarily tabling the results during a single run of the algorithm but used to mean any caching of results of an expensive pure function for future use. You seem to call that a "semi-permanent database of answers". Here is the original memoization paper [1] where he is using a constant-time table lookup exactly as I envisage in this case rather than only tabling results during a single invocation of the algorithm. Ironically he uses it to memoize a recursively-defined factorial function. [1] https://www.cs.utexas.edu/users/hunt/research/hash-cons/hash-cons-papers/michie-memo-nature-1968.pdf https://www.cs.utexas.edu/users/hunt/research/hash-cons/hash...
    - gmfawcett 5y ago
      lol, yes, we are at Peak HN right now. :) Michie (1968) wins the debate, without a doubt! Thanks for sharing your point of view, and the article.

Fibonacci is better memoized because it changes an exponential time algorithm into a linear time one, but I don't see why factorial would be better memoized.

by tome 5y ago

Fibonacci is better memoized because it changes an exponential time algorithm into a linear time one, but I don't see why factorial would be better memoized.

seanhunter 5y ago

If you memoize you turn either of them into constant time. So it's an improvement to factorial (albeit less dramatic) and in practise if you later on reach for a higher factorial than you have previously calculated you don't need to start from scratch which is a real-world speedup although the O is still linear. That said obviously the decision of whether to memoize depends on whether the function is going to be called more than once. If you're not calling fibbonacci more than once there is a closed form solution which is better for many input values than any of these methods.

thaumasiotes 5y ago
> If you're not calling fibbonacci more than once there is a closed form solution which is better for many input values than any of these methods. I don't think that's true; you're pretty much always better off calculating Fibonacci numbers by starting from F_0 and counting up than by using the closed-form solution.
- tome 5y ago
  Are you sure? The closed form solution can be evaluated in logarithmic time whereas counting up takes linear time.
  - thaumasiotes 5y ago
    Here's an article talking about it: https://towardsdatascience.com/why-is-the-closed-form-of-the-fibonacci-sequence-not-used-in-competitive-programming-674b805da341 https://towardsdatascience.com/why-is-the-closed-form-of-the... It covers a couple of points (all of this is me summarizing the article I just linked; I'm not an expert in numeric computing): - The closed-form expression for Fibonacci numbers involves an irrational number. But we can't do computations on irrational numbers; we're stuck with rational approximations. (Such as IEEE floating point.) Since computing an early Fibonacci number involves raising ϕ to a high exponent, the error involved in giving ϕ a finite representation rapidly compounds, corrupting the result. (According to this article, errors will become visible after F_100. That's quickly enough that you'd be justified in just having a lookup table for the first 100 Fibonacci numbers, which would be much faster than computing them as needed.) - You can represent the Fibonacci recurrence relation directly in matrix form. This is just the counting-up method written down a different way. Each Fibonacci number is the product of the constant matrix [[1 1] [1 0]] with the vector consisting of the previous two Fibonacci numbers. - You can exponentiate the matrix n-1 times to get a matrix that converts F_1 and F_0 (known in advance) into F_n and F_{n-1}. This is just as amenable to the shortcuts involved in calculating large exponents of a value as exponentiating ϕ is. But it's exact integer arithmetic.
    - tome 5y ago
      > You can exponentiate the matrix n-1 times to get a matrix that converts F_1 and F_0 (known in advance) into F_n and F_{n-1}. This is just as amenable to the shortcuts involved in calculating large exponents of a value as exponentiating ϕ is. But it's exact integer arithmetic. Right, and repeated squaring can give you the answer to the exponentiation in logarithmic time.
gmfawcett 5y ago
> If you memoize you turn either of them into constant time. At the risk of stumbling into the No True Memoization fallacy, I wouldn't consider that memoizing -- at least not in the dynamic programming sense. To get O(1), you're not temporarily tabling the results during a single run of the algorithm; rather you're building a semi-permanent database of answers and (effectively, in an amortized sense) discarding the algorithm altogether. I think that's formally known as the "just Google it" approach to optimization. :) From a DP perspective you can get O(N) from memoization on open-form Fibonacci, and no gain on open-form factorial, because the lookup table is ephemeral.
- seanhunter 5y ago
  This is probably the most "hackernews" conversation I've ever had but as far as I've ever seen the term used, "memoization" is not restricted to temporarily tabling the results during a single run of the algorithm but used to mean any caching of results of an expensive pure function for future use. You seem to call that a "semi-permanent database of answers". Here is the original memoization paper [1] where he is using a constant-time table lookup exactly as I envisage in this case rather than only tabling results during a single invocation of the algorithm. Ironically he uses it to memoize a recursively-defined factorial function. [1] https://www.cs.utexas.edu/users/hunt/research/hash-cons/hash-cons-papers/michie-memo-nature-1968.pdf https://www.cs.utexas.edu/users/hunt/research/hash-cons/hash...
  - gmfawcett 5y ago
    lol, yes, we are at Peak HN right now. :) Michie (1968) wins the debate, without a doubt! Thanks for sharing your point of view, and the article.