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
Thus . Multiplying both sides by and solving the resulting quadratic equation for its positive solution, one gets .
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 , , and see how long it takes to get an answer.
Task
Iterate , , until . Report the final value of , the number of iterations required, and the error with respect to .
See also
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
Common Lisp
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
Mercury
%%% -*- 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
Scheme
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