Algorithm to find floors of multiples of the golden ratio

Question

What is an algorithm to calculate $\lfloor n\phi \rfloor$ given some integer $n$, where $\phi$ is the golden ratio?

I am thinking the easiest way will involve calculating multiples of its continued fraction representation, since the golden ratio has a simple representation as a continued fraction ($[1;1,1,1,\dots]$) and it is easy to find the floor of a continued fraction (it is just the integer part of the fraction). However, I do not know how to calculate multiples of a continued fraction.

Also, by algorithm, I mean that it could be efficiently implemented on a computer. The algorithm may use arbitrary-precision integer arithmetic. It should not, however, be sensitive to rounding errors if floating arithmetic is used (I would prefer to avoid floats entirely). Pseudocode would be great, but if you do not include it, that is fine.

Answer 1

The Golden ratio can be approximated with arbitrary precision as the ratio of two consecutive Fibonacci numbers. These are easy to compute incrementally. Then compute and round

$$\left[n\frac{F_{k+1}}{F_k}\right].$$

It is even possible to compute $nF_k$ simultaneously to $F_k$. So the total cost is $2k$ additions and one division.

Answer 2

The golden ratio satisfies $\phi^2-\phi-1=0$, so $n\phi$ is the positive solution to $x^2-nx-n^2=0$. You can use standard numerical methods (bisection, if you're in a hurry coding-wise, but you could save running time by starting with approximate Newton-Raphson until the deltas get small) to bracket the root between two neighboring integers.