wiki:Gold

Gold

The pure gold of programming language design

This is a pure gold because it has all means of abstraction used.

(define (square x) (* x x))

(define (average x y) (/ (+ x y) 2.0))

(define tolerance 0.00001)

;; a search algorithm which converges to an approximation
(define (fixed-point f x)
  (define (close-enough a b)
    (< (abs (- a b)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough guess next)
          next
          (try next))))
  (try x))

;; oscilates
(define (sqrt x)
  (fixed-point (lambda (y) (/ x y))
               1.0))

(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y)))
               1.0))

(sqrt 2)

; wrap a function of arity 1
(define (average-damp f)
  (lambda (x) (average x (f x))))

(define (sqrt x)
  (fixed-point (average-damp (lambda (y) (/ x y))) 1.0))

(sqrt 2)

(define (cube-root x)
  (fixed-point (average-damp (lambda (y) (/ x (square y)))) 1.0))

(cube-root 4)

(define dx 0.0001)
(define (deriv g)
  (lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))

(define (cube x) (* x x x))
((deriv cube) 5)

(define (newton-transform g)
  (lambda (x) (- x (/ (g x) ((deriv g) x)))))

(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))

(define (sqrt x)
  (newtons-method (lambda (y) (- (square y) x)) 1.0))

(sqrt 2)

18 carat gold

val tolerance = 0.00001;

fun fixed_point (f:real->real) (guess:real) = 
  let 
    fun close_enough x y = abs (x - y) < tolerance
    fun try x =
      let 
        val next = f x 
      in
        if close_enough next x
        then next 
        else try next
      end
  in try guess end;

fun average x y = (x + y) / 2.0;

fun average_damp f:real->real =
  fn (x:real) => average x (f x);

fun sqrt x:real =
  fixed_point (average_damp (fn y:real => x / y)) 1.0;

val dx = 0.00001;

fun deriv (g) = fn x => (g(x + dx) - g(x)) / dx;

fun cube (x:real):real = x * x * x;

 (deriv cube) 5.0;

fun newton_transform g = fn x => x - g x / (deriv g) x;

fun newtons_method g guess = fixed_point (newton_transform g) guess;

fun sqrt x = 
  newtons_method (fn y:real => y * y - x) 1.0;

sqrt 2.0;

Pure gold

improve x y = (y + x / y) / 2

goodEnogh x y = abs (y ^ 2 - x) < epsilon
  where
    epsilon = 0.0001

until p f x
  | p x = x
  | otherwise = untill p f (f x)

sqrt x = until (goodEnough x) (improve x) x
sqrt x = until goodEnough improve x
  where
    goodEnough y = abs (y ^ 2 - x) < epsilon
    improve y = (y + x / y) / 2
deriv f x = (f (x + dx) - f x) / dx
  where
    dx = 0.0001

newton f = until goodEnough improve
  where
    goodEnough y = abs (f y) < epsilon
    improve y = y - (f y / deriv f y)
    epsilon = 0.0001

sqrt x = newton f x
  where
    f y = y ^ 2 - x
Last modified 6 weeks ago Last modified on Jan 15, 2020, 2:58:58 PM
Note: See TracWiki for help on using the wiki.