Programming Praxis

Home | Pages | Archives

The Golden Ratio

July 10, 2009 9:00 AM

I was helping my daughter with her math homework recently, and came across this problem in continued fractions:

$1 + \frac 1 { 1 + \frac 1 { 1 + \frac 1 { 1 + \frac 1 { 1 + \frac 1 \ldots } } } }$

This fraction can be considered as a sequence of terms

$G_0 = 1$

$G_1 = 1 + { 1 \over 1 } = 2$

$G_2 = 1 + { 1 \over 1 + { 1 \over 1 } } = { 3 \over 2 }$

$G_3 = 1 + { 1 \over 1 + { 1 \over 1 + { 1 \over 1 } } } = { 5 \over 3 }$

Or, in general

$G_{n+1} = 1 + \frac 1 { G_n }$

The first ten elements of the sequence are 1, 2, 3/2, 5/3, 8/5, 13/8, 21/13, 34/21, 55/34, and 89/55.

Your task is to write a program that evaluates the n^th element of the sequence. What is the value of $G_{200}$ ? When you are finished, you may read or run a suggested solution, or post your own solution or discuss the exercise in the comments below.

Posted by programmingpraxis

Categories: Exercises

Tags:

« Older Newer »

22 Responses to “The Golden Ratio”

[…] Praxis – The Golden Ratio By Remco Niemeijer Today’s Programming Praxis problem is an easy one: all we have to do is make a function that calculates the […]

By Programming Praxis – The Golden Ratio « Bonsai Code on July 10, 2009 at 11:09 AM
My Haskell solution (see http://bonsaicode.wordpress.com/2009/07/10/programming-praxis-the-golden-ratio/ for a version with comments):
```
import Data.Ratio

golden :: Int -> Rational
golden n = iterate (succ . recip) 1 !! n

main :: IO ()
main = print $ golden 200
```
By Remco Niemeijer on July 10, 2009 at 11:09 AM

Regular continued fractions have the nice property that they can be efficiently computed in the forward relation by a well-known recurrence:

let cf f n =
	let module M = struct
		open Num
		let zero, one = Int 0, Int 1
		let rec go h k h' k' i =
			if i = n then string_of_num (h // k) else
			let x = num_of_int (f i) in
			go h' k' (h +/ h' */ x) (k +/ k' */ x) (succ i)
	end in
	M.go M.zero M.one M.one M.zero (-2)

In this case, phi = cf (fun _ -> 1)

By Matías Giovannini on July 10, 2009 at 12:02 PM

import Data.Ratio ((%))

main :: IO ()
main = print (fromRational (g !! 200) :: Double)

g :: [Rational]
g = zipWith (%) (drop 2 fibs) (tail fibs)

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

By brian on July 10, 2009 at 12:21 PM

Ruby:


def golden_mean(n)
  g = 1.0
  n.times { g = 1 + 1/g}
  return g
end

puts golden_mean(200)

By Connochaetes on July 10, 2009 at 2:49 PM

Python’s native bigint support makes this easy.

>>> def golden(num):
... 	g = [1,1]
... 	for i in xrange(num):
... 		g.reverse() # calculate 1/g
... 		g[0] += g[1] # add 1
... 	return tuple(g)

>>> print '%i / %i' % golden(200)

By IChrisI on July 10, 2009 at 7:21 PM

Couple of quick Clojure solutions, first a simple recursive solution:

(defn g [n]
(if (zero? n) 1
(inc (/ 1 (g (dec n))))))

And a more space efficient iterative solution:

(defn g [n]
(loop [x 1 n n]
(if (zero? n) x
(recur (inc (/ 1 x)) (dec n)))))

By Darren on July 10, 2009 at 9:35 PM
Ooops, sorry I hadn’t read the “HOWTO” on posting source:

[ EDIT: Clojure is not one of the supported languages. I changed the sourcecode tag to css. ]

Recursive:
```
(defn g [n]
        (if (zero? n) 1 
            (inc (g (dec n)))))
```
Iterative:
```
(defn g [n]
        (loop [x 1 n n]
          (if (zero? n) x
              (recur (inc (/ 1 x)) (dec n)))))
```
By Darren on July 10, 2009 at 9:46 PM
Since this was posted for my math class (I’m the daughter mentioned in the problem), I was just wondering if anyone here can solve it without using computer programming. The reason I ask is that some interesting mathematical constants start to appear as you solve using algebra. If you don’t remember high school algebra, then solving the first ten numbers by had and leaving the fractions in improper form will reveal some sequences as well. That’s what the homework was actually designed to teach us. Just a thought.

By Anne on July 10, 2009 at 11:41 PM
[…] […]

By Posts about Programming from google blogs as of July 10, 2009 « tryfly.com on July 10, 2009 at 11:59 PM
A little ruby solution…

fib = Hash.new {|h,x| x == 0 ? h[x] = 0 : x == 1 ? h[x] = 1 : h[x] = h[x-1] + h[x-2]}
g = lambda {|x| [fib[x+2],fib[x+1]]}
puts g[200].join(‘ / ‘)

By Chris on July 11, 2009 at 1:33 PM
Anne,

As you noticed, the numerators and denominators of the terms are Fibonacci numbers. That’s because there is an intimate relationship between the Fibonacci numbers and the Golden Ratio. In particular, the ratio of n+1st and nth Fibonacci numbers tend to the Golden Ratio as n gets large. The same thing happens for the continued fraction as your dad illustrated. See http://www.friesian.com/golden.htm for an explanation of this that should be accessible to anyone with a little algebra background.

By jcs on July 11, 2009 at 5:12 PM

Pretty straightforward in Python. Simultaneous assignment makes it look pretty.

#!/usr/bin/env python
# compute approximations to the golden ratio using the Fibonacci sequence
# https://programmingpraxis.com/2009/07/10/the-golden-ratio/

def golden(n):
    a, b = 1, 1
    for x in range(n):
        a, b = a+b, a
    return (a, b)

print golden(200)

By Mark VandeWettering on July 12, 2009 at 11:14 PM

Before I really thought about the problem very much I tried coding it up in C#, which was easy enough. It surprised me when it overflowed a 64-bit unsigned integer. The reason why it caused an overflow became obvious once I took a look at the comments here. The code is just calculating a Fibonacci number. G(n) = F(n+2)/F(n+1). A true solution would require a bigint implementation. Without resorting to that, I rewrote the code using doubles. I thought it was interesting to discover that after G(40), the error in the approximation of the golden ratio became too small to store in a double.

http://inscrutable.pastebin.com/f2dc90711

By Scott Pedersen on July 16, 2009 at 1:26 AM
PLT Scheme:

(define/contract (continued-fraction-term N)
(-> (and/c (not/c negative?)
integer?)
number?)
(if (zero? N)
1.
(add1 (/ (continued-fraction-term (sub1 N))))))

By Eric H on July 18, 2009 at 4:22 PM

Trying to get hold of prolog :)

g(0,1).
g(N,G) :-
	N > 0,M is N-1,
	g(M,H),
	G is 1+rdiv(1,H).


g1(0,1).
g1(N,G) :-
	N > 0,M is N-1,
	g1(M,H),
	G is 1+1/H.

By veer on July 19, 2009 at 3:29 PM

A solution in O(log n) time

It’s nice to see this thread still active. Here’s a solution that runs
in log n time. It’s based on Anne’s observation that Gn = Fibn+1
/ Fibn (easily shown by a simple induction) and the fast-fib routine
from Exercise 1.19 of SICP.

(define golden-ratio
  (lambda (n)
    (let iter ((n n) (p 0) (q 1) (a 1) (b 1))
        (cond ((= n 0) (/ a b))
              ((even? n) (iter (/ n 2) (+ (* p p) (* q q))
                               (+ (* 2 p q) (* q q)) a b))
              (else (iter (- n 1) p q (+ (* b q) (* a q) (* a p))
                          (+ (* b p) (* a q))))))))

By jcs on July 20, 2009 at 3:23 PM

-- Golden ratio as a recursive fraction
phiRatio :: Int -> Double
phiRatio n
    | n > 0 =  1 + ( 1 / phiRatio (n - 1) )
    | otherwise = 1

-- Golden ratio as a recursive square root
phiRoot n
    | n > 0 = sqrt ( 1 + phiRoot (n - 1) )
    | otherwise = 1

I also did one that uses the Fibonacci sequence:

fib :: (Num a, Num b) => a -> b
fib n = fibGen 0 1 n

fibGen :: (Num a, Num b) => b -> b -> a -> b
fibGen a b n = case n of
                 0 -> a
                 n -> fibGen b (a + b) (n - 1)

fib :: (Num a, Num b) => a -> b
fib n = fibGen 0 1 n

fibGen :: (Num a, Num b) => b -> b -> a -> b
fibGen a b n = case n of
                 0 -> a
                 n -> fibGen b (a + b) (n - 1)

By daelin on October 1, 2009 at 8:00 PM

As for Clojure, there’s an even shorter solution than Darren’s:

(def G (iterate (comp inc /) 1)) ;; G is a lazy sequence of Ratios

(def phi (double (nth G 200)))   ;; 1.618033988749895, (an approximation of) the golden ratio!

We could have also BigDecimals, for more precision, like so:

(with-precision 100
  (bigdec (nth G 1000)))
;; Result: 1.6180339887498948482045868343656381177203091798058M

By Uros Dimitrijevic on November 22, 2009 at 3:38 AM

I’m working my way through old exercises in an effort to learn Common Lisp.

(defun golden-iter (n)
  (loop for i from 0 below n with g = 1
        do (setf g (1+ (/ g)))
        finally (return g)))

(format t "~S~%" (golden-iter 200))

(defun golden-rec (n)
  (if (zerop n)
      1
      (1+ (/ (golden-rec (1- n))))))

(format t "~S~%" (golden-rec 200))

By Graham on May 19, 2011 at 5:59 PM

(defun fibonacci (n &optional (a 0) (b 1))
“Accepts a number and fetches the corresponding number in the Fibonacci sequence”
(if (< n 2)
(* n b)
(fibonacci (- n 1) b (+ a b))))

(defun goldenr (n)
"Accepts a number and approximates the golden ratio to that step of certainty"
(/ (fibonacci n) (fibonacci (- n 1))))

By Heath on October 28, 2012 at 6:25 PM
Haskell, using the definitions supplied in the top portion (G0 = 1, G1 = 2 … )

golden :: Int -> Rational
golden 0 = 1
golden 1 = 2
golden n = 1 + (1 / (golden (n-1)))

OUTPUT:
———–
ghci> golden 200
734544867157818093234908902110449296423351 % 453973694165307953197296969697410619233826

By Steven on November 5, 2014 at 4:44 PM

Mobile Site | Full Site

Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.

Programming Praxis

The Golden Ratio

Share this:

Related

22 Responses to “The Golden Ratio”

Leave a Reply