4 ms·
I had the (mistaken) impression that the GCC code signicantly transformed the algorithm because there is only one recursive call instruction, but looking at it
by zucker42 6y ago
I had the (mistaken) impression that the GCC code signicantly transformed the algorithm because there is only one recursive call instruction, but looking at it closer it's still exponential. I still think it's a pretty silly idea to use such an unrealistic benchmark. Especially since it might be possible to make a compiler turn the exponential algorithm linear.
- nv-vn 6y agoI'd be very surprised if there's a commercial compiler that would automatically optimize this into linear time. Maybe some obscure functional research language? But certainly don't think LLVM is capable of dynamic programming.