Golden ratio/Convergence: Difference between revisions

Content added Content deleted

Inline

Revision as of 09:46, 3 June 2023

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

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

BASIC

BASIC256

Translation of: FreeBASIC

call iterate()
end

subroutine iterate()
	iter = 0
	phi0 = 1.0
	do
		phi1 = 1.0 + (1.0 / phi0)
		diferencia = abs(phi1 - phi0)
		phi0 = phi1
		iter += 1
	until (1.0e-5 > diferencia)

	print "Result: "; phi1; " after "; iter; " iterations"
	print "The error is approximately "; phi1 - (0.5 * (1.0 + sqrt(5.0)))
end subroutine

Output:

Result: 1.61803278689 after 14 iterations
The error is approximately -0.00000120186

Chipmunk Basic

Works with: Chipmunk Basic version 3.6.4

Translation of: FreeBASIC

100 iterate
110 end
120 sub iterate()
130 iter = 0
140 phi0 = 1
150 do
160  phi1 = 1+(1/phi0)
170  diff = abs(phi1-phi0)
180  phi0 = phi1
190  iter = iter+1
200 loop until (1.000000E-05 > diff)
210 print "Result: ";phi1;" after ";iter;" iterations"
220 print "The error is approximately ";phi1-(0.5*(1+sqr(5)))
230 end sub

Output:

Result: 1.618033  after 14  iterations
The error is approximately -1.201865E-06

FreeBASIC

Translation of: C

Sub using_Single
    Dim As Integer iter = 0
    Dim As Single phi0 = 1.0f
    Dim As Single phi1
    Dim As Single diferencia
    Do
        phi1 = 1.0f + (1.0f / phi0)
        diferencia = Abs(phi1 - phi0)
        phi0 = phi1
        iter += 1
    Loop While (1.0e-5f < diferencia)
    
    Print "Using type Single --"
    Print Using "Result: #.########## after ## iterations"; phi1; iter
    Print Using "The error is approximately #.##########"; phi1 - (0.5f * (1.0f + Sqr(5.0f)))
End Sub

Sub using_Double
    Dim As Integer iter = 0
    Dim As Double phi0 = 1.0
    Dim As Double phi1
    Dim As Double diferencia
    Do
        phi1 = 1.0 + (1.0 / phi0)
        diferencia = Abs(phi1 - phi0)
        phi0 = phi1
        iter += 1
    Loop While (1.0e-5 < diferencia)
    
    Print "Using type Double --"
    Print Using "Result: #.########## after ## iterations"; phi1; iter
    Print Using "The error is approximately #.##########"; phi1 - (0.5 * (1.0 + Sqr(5.0)))
End Sub

using_Single
Print
using_Double

Sleep

Output:

Using type Single --
Result: 1.6180328131 after 14 iterations
The error is approximately -.0000011921

Using type Double --
Result: 1.6180327869 after 14 iterations
The error is approximately -.0000012019

Gambas

Translation of: FreeBASIC

Public Sub Main() 
  
  using_Single 
  Print 
  using_Float
  
End 

Sub using_Single()
  
  Dim iter As Integer = 0 
  Dim phi0 As Single = 1.0
  Dim phi1 As Single
  Dim diferencia As Single
  
  Do 
    phi1 = 1.0 + (1.0 / phi0) 
    diferencia = Abs(phi1 - phi0) 
    phi0 = phi1 
    iter += 1 
  Loop While (1.0e-5 < diferencia) 
  
  Print "Using type Single --" 
  Print "Result: "; Format$(phi1, "#.##########"); " after "; iter; " iterations"
  Print "The error is approximately "; Format$(phi1 - (0.5 * (1.0 + Sqr(5.0))), "#.##########") 
  
End Sub 

Sub using_Float()
  
  Dim iter As Integer = 0 
  Dim phi0 As Float = 1.0 
  Dim phi1 As Float
  Dim diferencia As Float
  
  Do 
    phi1 = 1.0 + (1.0 / phi0) 
    diferencia = Abs(phi1 - phi0) 
    phi0 = phi1 
    iter += 1 
  Loop While (1.0e-5 < diferencia) 
  
  Print "Using type Float --" 
  Print "Result: "; Format$(phi1, "#.##########"); " after "; iter; " iterations"
  Print "The error is approximately "; Format$(phi1 - (0.5 * (1.0 + Sqr(5.0))), "#.##########") 
  
End Sub

Output:

Using type Single --
Result: 1,6180328131 after 14 iterations
The error is approximately -0,0000011757

Using type Float --
Result: 1,6180327869 after 14 iterations
The error is approximately -0,0000012019

Yabasic

Translation of: FreeBASIC

iterate()
end

sub iterate()
    iter = 0
    phi0 = 1.0
    repeat
        phi1 = 1.0 + (1.0 / phi0)
        diferencia = abs(phi1 - phi0)
        phi0 = phi1
        iter = iter + 1
    until (1.0e-5 > diferencia)
    
    print "Result: ", phi1, " after ", iter, " iterations"
	e$ = str$(phi1 - (0.5 * (1.0 + sqrt(5.0))), "%2.10f")
    print "The error is approximately ", e$
end sub

Output:

Result: 1.61803 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

Common Lisp

Translation of: Scheme

Note that, although standard Scheme guarantees a tail recursion will act like a GOTO rather than an ordinary subroutine call, Common Lisp does not. Therefore this implementation, translated from the Scheme, may require stack space. The amount will be very little.

(You could use this recursive method in C and many other languages where tail recursions are not guaranteed to be "proper". The compiler's optimizer may or may not turn the tail call into a GOTO.)

(defun iterate (phi n)
  ;; This is a tail recursive definition, copied from the
  ;; Scheme. Common Lisp does not guarantee proper tail calls, but the
  ;; depth of recursion will not be too great.
  (let ((phi1 (1+ (/ phi)))
        (n1 (1+ n)))
    (if (<= (abs (- phi1 phi)) 1/100000)
        (values phi1 n1)
        (iterate phi1 n1))))

(multiple-value-bind (phi n) (iterate 1 0)
  (princ "Result: ")
  (princ phi)
  (princ " (")
  (princ (* 1.0 phi))
  (princ ") after ")
  (princ n)
  (princ " iterations")
  (terpri)
  (princ "The error is approximately ")
  (princ (- phi (* 0.5 (+ 1.0 (sqrt 5.0)))))
  (terpri))

Output:

Result: 987/610 (1.6180328) after 14 iterations
The error is approximately -1.1920929e-6

Dart

Translation of: C

import 'dart:math';

void iterate() {
  int count = 0;
  double phi0 = 1.0;
  double phi1;
  double difference;
  do {
    phi1 = 1.0 + (1.0 / phi0);
    difference = (phi1 - phi0).abs();
    phi0 = phi1;
    count += 1;
  } while (1.0e-5 < difference);

  print("Result: $phi1 after $count iterations");
  print("The error is approximately ${phi1 - (0.5 * (1.0 + sqrt(5.0)))}");
}

void main() {
  iterate();
}

Output:

Result: 1.6180327868852458 after 14 iterations
The error is approximately -0.0000012018646491362972

EasyLang

phi0 = 1
repeat
   phi = 1 + 1 / phi0
   until abs (phi - phi0) < 1e-5
   phi0 = phi
   iter += 1
.
numfmt 10 0
print "Iterations: " & iter
print "Result: " & phi
print "Error: " & phi - (1 + sqrt 5) / 2

Go

Translation of: Wren

package main

import (
    "fmt"
    "math"
)

func main() {
    oldPhi := 1.0
    var phi float64
    iters := 0
    limit := 1e-5
    for {
        phi = 1.0 + 1.0/oldPhi
        iters++
        if math.Abs(phi-oldPhi) <= limit {
            break
        }
        oldPhi = phi
    }
    fmt.Printf("Final value of phi : %16.14f\n", phi)
    actualPhi := (1.0 + math.Sqrt(5.0)) / 2.0
    fmt.Printf("Number of iterations : %d\n", iters)
    fmt.Printf("Error (approx) : %16.14f\n", phi-actualPhi)
}

Output:

Final value of phi : 1.61803278688525
Number of iterations : 14
Error (approx) : -0.00000120186465

Java

Translation of: Wren

public class GoldenRatio {
    static void iterate() {
        double oldPhi = 1.0, phi = 1.0, limit = 1e-5;
        int iters = 0;
        while (true) {
            phi = 1.0 + 1.0 / oldPhi;
            iters++;
            if (Math.abs(phi - oldPhi) <= limit) break;
            oldPhi = phi;
        }
        System.out.printf("Final value of phi : %16.14f\n", phi);
        double actualPhi = (1.0 + Math.sqrt(5.0)) / 2.0;
        System.out.printf("Number of iterations : %d\n", iters);
        System.out.printf("Error (approx) : %16.14f\n", phi - actualPhi);
    }

    public static void main(String[] args) {
        iterate();
    }
}

Output:

Final value of phi : 1.61803278688525
Number of iterations : 14
Error (approx) : -0.00000120186465

Mercury

Translation of: Scheme

%%% -*- mode: mercury; prolog-indent-width: 2; -*-

:- module golden_ratio_convergence_mercury.

:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.

:- implementation.
:- import_module float.
:- import_module int.
:- import_module math.
:- import_module string.

:- pred iterate(float::in, float::out, int::in, int::out) is det.
iterate(!Phi, !N) :-
  Phi1 = (1.0 + (1.0 / !.Phi)),
  N1 = !.N + 1,
  (if (abs(Phi1 - !.Phi) =< 1.0e-5)
   then (!:Phi = Phi1, !:N = N1)
   else (iterate(Phi1, !:Phi, N1, !:N))).

main(!IO) :-
  iterate(1.0, Phi, 0, N),
  print("Result: ", !IO),
  print(from_float(Phi), !IO),
  print(" after ", !IO),
  print(from_int(N), !IO),
  print(" iterations", !IO),
  nl(!IO),
  print("The error is approximately ", !IO),
  print(from_float(Phi - (0.5 * (1.0 + (sqrt(5.0))))), !IO),
  nl(!IO).

:- end_module golden_ratio_convergence_mercury.

Output:

Result: 1.6180327868852458 after 14 iterations
The error is approximately -1.2018646491362972e-06

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

RPL

RPL 1986

≪ 0 1 1
   DO
      ROT 1 +
      ROT DROP 
      SWAP DUP INV 1 + 
   UNTIL DUP2 - ABS .00001 ≤ END
   SWAP DROP SWAP 
   OVER 1 5 √ + 2 / - ABS
≫ 'PHICONV' STO

Output:

3: 1.61803278688
2: 14
1: .00000120187

RPL 2003

≪ 0 1 5 √ + 2 / → count phi
  ≪ 1 1 
     DO
        'count' INCR DROP
        NIP DUP INV 1 + 
     UNTIL DUP2 - →NUM ABS .00001 ≤ END
     NIP EVAL count 
     OVER phi - →NUM ABS
≫ ≫  'PHICONV' STO

Output:

3: 987/610
2: 14
1: .00000120186

Scheme

Translation of: ATS

This will run without modification in R5RS Scheme implementations, among others.

(define (iterate phi n)
  (let ((phi1 (+ 1 (/ phi)))
        (n1 (+ n 1)))
    (if (<= (abs (- phi1 phi)) 1/100000)
        (values phi1 n1)
        (iterate phi1 n1))))

(call-with-values (lambda () (iterate 1 0))
  (lambda (phi n)
    (display "Result: ")
    (display phi)
    (display " (")
    (display (* 1.0 phi))
    (display ") after ")
    (display n)
    (display " iterations")
    (newline)
    (display "The error is approximately ")
    (display (- phi (* 0.5 (+ 1.0 (sqrt 5.0)))))
    (newline)))

Output:

Result: 987/610 (1.618032786885246) after 14 iterations
The error is approximately -1.2018646489142526e-6

Wren

Library: Wren-fmt

Wren's only built-in numeric type is a 64 bit float.

import "./fmt" for Fmt

var oldPhi = 1
var phi
var iters = 0
var limit = 1e-5
while (true) {
    phi = 1 + 1 / oldPhi
    iters = iters + 1
    if ((phi - oldPhi).abs <= limit) break
    oldPhi = phi
}
Fmt.print("Final value of phi : $16.14f", phi)
var actualPhi = (1 + 5.sqrt) / 2
Fmt.print("Number of iterations : $d", iters)
Fmt.print("Error (approx) : $16.14f", phi - actualPhi)

Output:

Final value of phi : 1.61803278688525
Number of iterations : 14
Error (approx) : -0.00000120186465

Revision as of 09:46, 3 June 2023

Task

See also

RPL 1986

RPL 2003