Golden ratio/Convergence

Golden ratio/Convergence
You are encouraged to solve this task according to the task description, using any language you may know.

The golden ratio can be defined as the continued fraction

$\phi =1+{1 \over {1+{1 \over {1+{1 \over {1+\cdots }}}}}}$

Thus $\phi =1+{1/\phi }$. Multiplying both sides by $\phi$ and solving the resulting quadratic equation for its positive solution, one gets $\phi =(1+{\sqrt {5}})/2\approx 1.61803398875$.

The golden ratio has the slowest convergence of any continued fraction, as one might guess by noting that the denominators are made of the smallest positive integer. This task treats the problem of convergence in a somewhat backwards fashion: we are going to iterate the recursion $\phi _{n+1}=1+{1/\phi _{n}}$, $\phi _{0}=1$, and see how long it takes to get an answer.

Task

Iterate $\phi _{n+1}=1+{1/\phi _{n}}$, $\phi _{0}=1$, until $|\phi _{n+1}-\phi _{n}|\leq 1\times 10^{-5}$. Report the final value of $\phi _{n+1}$, the number of iterations required, and the error with respect to $(1+{\sqrt {5}})/2$.

See also

• Metallic ratios

ATS

#include "share/atspre_staload.hats"

%{^
#include <math.h>
%}

extern fn sqrt : double -<> double = "mac#sqrt"

fun
iterate {n   : nat}
        (phi : double,
         n   : int n) : @(double, intGte 1) =
  let
    val phi1 = 1.0 + (1.0 / phi)
    and n1 = succ n
  in
    if abs (phi1 - phi) <= 1.0e-5 then
      @(phi1, n1)
    else
      iterate {n + 1} (phi1, n1)
  end

implement
main0 () =
  let
    val @(phi, n) = iterate {0} (1.0, 0)
    val _ = $extfcall (int, "printf",
                       "Result: %.10f after %d iterations\n",
                       phi, n)
    val _ = $extfcall (int, "printf",
                       "The error is approximately %.10f\n",
                       phi - (0.5 * (1.0 + sqrt (5.0))))
  in
  end

Output:

Result: 1.6180327869 after 14 iterations
The error is approximately -0.0000012019

C

#include <stdio.h>
#include <math.h>

static void
using_float ()                  /* C2x does not require "void". */
{
  int count = 0;
  float phi0 = 1.0f;
  float phi1;
  float difference;
  do
    {
      phi1 = 1.0f + (1.0f / phi0);
      difference = fabsf (phi1 - phi0);
      phi0 = phi1;
      count += 1;
    }
  while (1.0e-5f < difference);

  printf ("Using type float --\n");
  printf ("Result: %f after %d iterations\n", phi1, count);
  printf ("The error is approximately %f\n",
          phi1 - (0.5f * (1.0f + sqrtf (5.0f))));
}

static void
using_double ()                 /* C2x does not require "void". */
{
  int count = 0;
  double phi0 = 1.0;
  double phi1;
  double difference;
  do
    {
      phi1 = 1.0 + (1.0 / phi0);
      difference = fabs (phi1 - phi0);
      phi0 = phi1;
      count += 1;
    }
  while (1.0e-5 < difference);

  printf ("Using type double --\n");
  printf ("Result: %f after %d iterations\n", phi1, count);
  printf ("The error is approximately %f\n",
          phi1 - (0.5 * (1.0 + sqrt (5.0))));
}

int
main ()                         /* C2x does not require "void". */
{
  using_float ();
  printf ("\n");
  using_double ();
}

Output:

Using type float --
Result: 1.618033 after 14 iterations
The error is approximately -0.000001

Using type double --
Result: 1.618033 after 14 iterations
The error is approximately -0.000001

ObjectIcon

import io, util

procedure main ()
  local phi0, phi1, count

  count := 1
  phi0 := 1.0
  while abs ((phi1 := 1.0 + (1.0 / phi0)) - phi0) > 1.0e-5 do
  {
    phi0 := phi1
    count +:= 1
  }
  io.write ("Result: ", phi1, " after ", count, " iterations")
  io.write ("The error is approximately ",
            phi1 - (0.5 * (1.0 + Math.sqrt (5.0))))
end

Output:

Result: 1.618032787 after 14 iterations
The error is approximately -1.201864649e-06

RATFOR

program grconv
  integer count
  real phi0, phi1, diff

  count = 0
  phi0 = 1.0
  diff = 1e+20
  while (1e-5 < diff)
    {
      phi1 = 1.0 + (1.0 / phi0)
      diff = abs (phi1 - phi0)
      phi0 = phi1
      count = count + 1
    }

  write (*,'("Result:", F9.6, " after", I3, " iterations")') _
    phi1, count
  write (*,'("The error is approximately ", F9.6)') _
          phi1 - (0.5 * (1.0 + sqrt (5.0)))
end

Output:

Result: 1.618033 after 14 iterations
The error is approximately -0.000001