# 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:

$n$ | $\phi_n$ |
---|---|

0 | 1.5 |

1 | 1.66666 |

2 | 1.6 |

3 | 1.625 |

4 | 1.61539 |

5 | 1.61905 |

6 | 1.61765 |

7 | 1.61818 |

8 | 1.61798 |

9 | 1.61806 |

10 | 1.61803 |

11 | 1.61803 |

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

$n$ | $\phi_n$ |
---|---|

0 | 1.5 |

1 | 1.61538 |

2 | 1.61765 |

3 | 1.61798 |

4 | 1.61803 |

5 | 1.61803 |

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.