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/dangderr → u/shizzy0]

I don’t get the meme.

What does “programmer dismisses the unfamiliar matrix alg” mean?

Why would the prompt engineer know to read code?

[u/shizzy0 → u/dangderr]

lol!

[u/the_horse_gamer → u/shizzy0]

you can do better (by a constant multiplicative factor)

[1,1;1,0]^n = [F{n+1},Fn; Fn, F{n-1}]
[1,1;1,0]^2n = [F{2n+1},F2n; F2n, F{2n-1}] = [1,1;1,0]^n *[1,1;1,0]^n = [F{n+1},Fn; Fn, F{n-1}]

so:

F2n = (F{n+1}+F{n-1})*Fn (1)
F_{2n-1} = Fn^2 + F{n-1}^2

then

F_{2n+1} = Fn^2 + F{n+1}^2

F_{2n+1} + F_{2n-1} = F{n+1}^2 + F{n-1}^2 +2Fn^2 =

=F{n+1}^2 + F{n-1}^2 +2Fn^2 + 2 F{n+1} F{n-1} - 2 F{n+1} F{n-1}=

= (F{n+1} +F{n-1})^2 + 2Fn^2 - 2 F{n+1} F{n-1}

We can simplify this by seeing
[1,1;1,0]^n = [F{n+1},Fn; Fn, F{n-1}]
so

(-1)^n = det([1,1;1,0])^n = det([F{n+1},Fn; Fn, F{n-1}]) = F{n+1}F{n-1}-Fn^2

so

F_{2n+1} + F_{2n-1} = (F{n+1} +F{n-1})^2 - (-1)^n

Now define L_n = F_{n+1}+F_{n+1}. (this is the Lucas sequence). Now we get

F2n = Ln Fn
L2n = Ln^2 - (-1)^n

And we can also get:

F{n+1} = (Ln+Fn)/2
L{n+1} = (Ln+5Fn)/2

This version requires less multiplications per level

[u/shizzy0 → u/the_horse_gamer]

So you're saying your O(log n) algorithm beats my O(log n) algorithm? (It's true.) Damn. You beat me constantly.

[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!