Calculating the golden ratio

Math in this page not rendering? See the fix

My wife was watching the Khan academy video on the golden ratio, in which they used the quadratic equation to calculate the value of the constant. Most of us have access to a fast square root function today to make that calculation easy, and calculating a constant like the golden ratio only has to happen once so having a very efficient algorithm to calculate it is unnecessary. But I picked up the taste for designing little numerical algorithms from Acton’s superb book Real Computing Made Real, and while she finished watching the video happily produced a couple.

First I took the defining equation for the golden ratio, the one you write down from inspecting the rectangles that give its geometric definition

$$\phi = 1 + \frac{1}{\phi}.$$

This is almost an algorithm in its own right. We add some subscripts to get a recurrence that we can run until it converges:

$$\phi_{n+1} = 1 + \frac{1}{\phi_n}.$$

We just need a starting value for $\phi_0$. By definition $\phi$ must be positive, so $1+\frac{1}{\phi} > 1$. And $\phi<2$, since that would correspond to cutting the rectangle in the geometric definition into two equal squares. The equation is quite smooth and regular so long as we stay away from values of $\phi_0$ near 0, so we make a lazy choice and start from 1.5.

The results of this algorithm:

That’s quite a slow convergence. We’re bouncing back and forth across the value. Surely we can do better. For nice, smooth right hand sides the first thing to do is try Newton’s method. The calculations are simple and give a recurrence

$$\phi_{n+1} = \frac{\phi_n^2 + 2\phi_n}{\phi_n^2 + 1}.$$

Taking $\phi_0 = 1.5$ again, we get

Dramatically faster, at the cost of a few more operations in each iteration, and it converges nicely from one direction. That was enough to satisfy me and I went to cook dinner.

« Back to Miscellany | Home