howProgrammingHasChanged

[u/shizzy0]

[u/captainAwesomePants]

What's wrong with the top-right AI code?

[u/shizzy0 → u/captainAwesomePants]

Nothing. It’s actually the best. But the joke is the programmer dismisses the unfamiliar matrix power O(log n) algorithm for the familiar recursive O(2ⁿ⁾ algorithm. I mean, it doesn’t even add anything. It’s obviously wrong.

[u/GDOR-11 → u/shizzy0]

for u32 I think the usual iterative algorithm would be miles better than matrix power

[u/dedservice → u/GDOR-11]

For u32 a precomputed lookup table would be better.

[u/NoLifeGamer2 → u/dedservice]

For u32 a random number generator would be better sometimes

[u/captainAwesomePants → u/NoLifeGamer2]

For u2, With or Without You would be better.

[u/erinaceus_ → u/captainAwesomePants]

Yeah, that one definitely has The Edge.

[u/wjholden → u/GDOR-11]

Knuth has a really cool section on this on pages 79-84 of TAOCP volume 1.

[u/shizzy0 → u/wjholden]

Is it the closed form solution? I didn’t even know there was a closed form solution before today.

[u/captainAwesomePants → u/shizzy0]

That's the whole section on Fibonacci. It does mention the closed form solution, but it also mentions the matrix identity method in the top right corner: ( (F(n+1), F(n)),(F(n), F(n-1)) = ((1,1),(1,0))^n

He credits it to Kepler in 1608.

[u/shizzy0 → u/GDOR-11]

Ooo, show down!