On: "The worst algorithm in the world?"

[robinhouston]

That’s very nice! And a little rearrangement will bring it from three to two “big multiplications”, making it faster than my routine:

  def fib_ring2(n):
    assert n >= 0
    a, b = 2, 0 # invariant: phi^n = (a + b*sqrt(5)) / 2
    for bit in bits(n):
        ab = a*b
        a, b = (a+b)*((a+5*b)//2) - 3*ab, ab
        if bit: a, b = (a + 5*b)//2, (a+b)//2
    return b

[shasta → robinhouston]

Oops, I should have found that. I looked and thought there was some reason it wouldn't work. Interesting post, thanks for the fun.