Knuth Euclid algorithm worst case

Question

I have been reading Knuth's The Art of Computer Programming(vol 2. Seminumerical Algorithms) and noticed the following statement:

If $0 \le u,v < N$, the number of division steps needed by the Euclidean algorithm to process $u, v$ is at most $\lfloor log_\phi(3 - \phi)N \rfloor$.

Now the following website which prompted me to read the book states the same except that the maximum number of steps is in fact $\lceil log_\phi(\sqrt{5}N)\rceil - 2$.

Am I missing some algebraic manipulation here if this actually represents the same or is it a mistake?

Answer 1

Hints:

$ \phi=\dfrac{\sqrt5+1}2 \implies\phi^2=\phi+1$ and $3-\phi=\dfrac {\sqrt5} \phi.$

Also, since $\log_\phi(3-\phi)$ is not an integer, its floor differs from its ceiling by $1$.