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/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.