The Golden Ratio

July 10, 2009

A useful function is iterate, which repeatedly evaluates a function in a sequence:

(define (iterate n f . bs)
  (let loop ((n n) (b (car bs)) (bs (cdr bs)) (xs '()))
    (if (zero? n) (reverse xs)
      (let ((new-bs (append bs (list (apply f b bs)))))
        (loop (- n 1) (car new-bs) (cdr new-bs) (cons b xs))))))

For instance, (define (fib n) (iterate n + 1 1)) defines a function that calculates the first n fibonacci numbers. Iterate is useful enough that we will add it to the Standard Prelude.

The sequence that computes the golden ratio is

(define (golden n) (iterate n (lambda (x) (+ 1 (/ x))) 1))

and the 201st element (note that iterate counts from zero) of the golden sequence is

> (car (reverse (golden 201)))

This continued fraction is well-known as the value of φ, the golden ratio, an irrational number with a value of { 1 + \sqrt{5} } \over 2 or approximately 1.618; by the 200th term, the error is -7.851 × 10-84. The golden ratio is common in nature, art and music.

You can see this program at The mathematical equations on this page were produced by Donald Knuth’s LaTeX program; for a math pastebin, see

About these ads

Pages: 1 2

22 Responses to “The Golden Ratio”

  1. […] 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 […]

  2. Remco Niemeijer said

    My Haskell solution (see for a version with comments):

    import Data.Ratio
    golden :: Int -> Rational
    golden n = iterate (succ . recip) 1 !! n
    main :: IO ()
    main = print $ golden 200
  3. 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 (-2)

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

  4. brian said
    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)
  5. Connochaetes said


    def golden_mean(n)
      g = 1.0
      n.times { g = 1 + 1/g}
      return g
    puts golden_mean(200)
  6. IChrisI said

    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)
  7. Darren said

    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)))))

  8. Darren said

    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. ]


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


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

    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.

  10. Chris said

    A little ruby solution…

    fib = {|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(‘ / ‘)

  11. jcs said


    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 for an explanation of this that should be accessible to anyone with a little algebra background.

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

    #!/usr/bin/env python
    # compute approximations to the golden ratio using the Fibonacci sequence
    def golden(n):
        a, b = 1, 1
        for x in range(n):
            a, b = a+b, a
        return (a, b)
    print golden(200)
  13. Scott Pedersen said

    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.

  14. Eric H said

    PLT Scheme:

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

  15. veer said

    Trying to get hold of prolog :)

    g(N,G) :-
    	N > 0,M is N-1,
    	G is 1+rdiv(1,H).
    g1(N,G) :-
    	N > 0,M is N-1,
    	G is 1+1/H.
  16. jcs said

    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))))))))
  17. daelin said

    — 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)

  18. Uros Dimitrijevic said

    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
  19. Graham said

    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+ (/ (golden-rec (1- n))))))
    (format t "~S~%" (golden-rec 200))
  20. Heath said

    (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))))

  21. Steven said

    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)))

    ghci> golden 200
    734544867157818093234908902110449296423351 % 453973694165307953197296969697410619233826

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 634 other followers

%d bloggers like this: