In the associated article linked to at "Leaving aside the absurdity of computing Fibonacci numbers recursively,"[1] (which, yes, I agree), we list the various algorithms as (roughly):
how to fibonacci space complexity time complexity
------------------------- ---------------- ---------------
insane recursion exponential exponential
memoized insane recursion linear linear
The space complexity of "insane recursion" without memoization is the maximum stack-depth; the worst case stack is,
fib(n)
fib(n-1)
fib(n-2)
...
fib(1)
Which is n stack frames (and the stack frames are of constant size); the space complexity of the whole thing is thus linear in the size of n. (While the call tree is itself exponential in size, the memory required is only the depth of that tree, since we can't call fib(n-1) & fib(n-2) simultaneously[2].
(The time complexity is, of course, exponential, and I agree with the "insane" moniker. I also like your comment elsewhere in this thread about people hyperfocusing on the example and missing the larger point of the article … and I'm so sorry but I've been sniped by this.)
I too also appreciate the beauty of the "insane" algorithm, from a mathematical view. What I think gets lost on some programmers¹ is that, while that's all good and fine, we're not just doing a computation, we are doing a computation and we're inherently expending time and space to do that computation, and the amount of time and space is inherently part of the problem, or part of the requirements. I want to compute X, but I also do want to do it before the heat death of the universe. Attempting to sweep those under the rug with a "sufficiently smart compiler" is fun when it works, but I think in the sense of engineering software, we need a more rigorous answer to "it will not consume bonkers amounts of space/time to compute X."
"Accidentally Quadratic" was a fun tumblr dedicate to more real world instances of this, and it's sad they're not longer posting, though I still use that term to name real-world sightings of O(lol) time. (O(lol) space is just called "Java".)
¹and since you say "to actually compute it that way", I think you get this, but I want to point it out here
Are there any existing compilers that could compile a function like this -- non-tail recursive and non-tail recursive modulo cons -- into something that executes in sub-exponential time? How would that even work? I've never heard of a compiler sufficiently smart to optimize a definition like this and now I'm very curious
Well, both Clang [0] and GCC [1] do compile the "insanely-recursive" fib into something less insane (or, in case of GCC, something that's insane in a different way). It looks like it's done with partial unrolling/inlining?
And, well, if you disregard heavy optimizations, then this "insanely-recursive" function is actually a somewhat decent way to measure the efficiency of the function calls and arithmetic.
If we account for arbitrary precision operations necessary for large N, I believe the memoized insane recursion is quadratic in space and time. This is actually not as bad of a pessimization as I thought it would be over just using Binet's formula, but it's still a hit.
local fib do
local impl impl = function(n, n1, n2)
if n == 0 then return n1 end
return impl(n - 1, n1 + n2, n1)
end
fib = function(n) return impl(n - 1, 1, 0) end
end
for i = 1, 10 do print(fib(i)) end
Comments
In the associated article linked to at "Leaving aside the absurdity of computing Fibonacci numbers recursively,"[1] (which, yes, I agree), we list the various algorithms as (roughly):
The space complexity of "insane recursion" without memoization is the maximum stack-depth; the worst case stack is, Which is n stack frames (and the stack frames are of constant size); the space complexity of the whole thing is thus linear in the size of n. (While the call tree is itself exponential in size, the memory required is only the depth of that tree, since we can't call fib(n-1) & fib(n-2) simultaneously[2].(The time complexity is, of course, exponential, and I agree with the "insane" moniker. I also like your comment elsewhere in this thread about people hyperfocusing on the example and missing the larger point of the article … and I'm so sorry but I've been sniped by this.)
[1]: https://ianthehenry.com/posts/fibonacci/
[2]: the little demons in my mind are now trying to scheme up an insaner recursion that attempts this. Threads maybe?
"the absurdity of computing Fibonacci numbers recursively"
It's absurd to actually compute it that way, but it's beautiful to express it that way.
From the blog post:
Easy to read, easy to comprehend. You just need a smart compiler to do it efficiently.I too also appreciate the beauty of the "insane" algorithm, from a mathematical view. What I think gets lost on some programmers¹ is that, while that's all good and fine, we're not just doing a computation, we are doing a computation and we're inherently expending time and space to do that computation, and the amount of time and space is inherently part of the problem, or part of the requirements. I want to compute X, but I also do want to do it before the heat death of the universe. Attempting to sweep those under the rug with a "sufficiently smart compiler" is fun when it works, but I think in the sense of engineering software, we need a more rigorous answer to "it will not consume bonkers amounts of space/time to compute X."
"Accidentally Quadratic" was a fun tumblr dedicate to more real world instances of this, and it's sad they're not longer posting, though I still use that term to name real-world sightings of O(lol) time. (O(lol) space is just called "Java".)
¹and since you say "to actually compute it that way", I think you get this, but I want to point it out here
Do you have any idea who the poster behind "Accidentally Quadratic" is? Spounds like he/she would have some interesting stories.
Are there any existing compilers that could compile a function like this -- non-tail recursive and non-tail recursive modulo cons -- into something that executes in sub-exponential time? How would that even work? I've never heard of a compiler sufficiently smart to optimize a definition like this and now I'm very curious
Well, both Clang [0] and GCC [1] do compile the "insanely-recursive" fib into something less insane (or, in case of GCC, something that's insane in a different way). It looks like it's done with partial unrolling/inlining?
And, well, if you disregard heavy optimizations, then this "insanely-recursive" function is actually a somewhat decent way to measure the efficiency of the function calls and arithmetic.
[0] https://godbolt.org/z/3fce1qTdv
[1] https://godbolt.org/z/4jqa453qY
If we account for arbitrary precision operations necessary for large N, I believe the memoized insane recursion is quadratic in space and time. This is actually not as bad of a pessimization as I thought it would be over just using Binet's formula, but it's still a hit.
ha thanks, you are absolutely right. i updated the table :)
In that same article, you have some iterations
That second line is screwed up, which also screws up the subsequent lines. It should look like which then means the line after that should be and so oni think this is just very badly worded. the initial conditions are current=8, previous=41, not the other way around. i should make that more clear
in lua: