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.
Comments
"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