How to find the minimum positive number that added to 1.0 gives something larger?

Question

While translating some Fortran to Scheme/Racket I have come across the function:

; EPSILON(X)      The  least  positive  number  that added
;                 to 1 returns a number that is greater than 1

How do I find the number in Scheme?

Answer 1

#lang racket/base

;; http://en.wikipedia.org/wiki/Machine_epsilon
;; approximates the machine epsilon

(require racket/flonum)

(define (compute-machine-epsilon)
  (let loop ([n 1.0])
    (define next-n (fl/ n 2.0))
    (if (fl= 1.0 (fl+ 1.0 next-n))
        n
        (loop next-n))))

Answer 2

Assuming you're using IEEE-754 floating-point (which may not be the case in Scheme, I don't know), then the machine epsilon is well known: for double-precision arithmetic, it's 1.11e-16.

For other platforms or floating-point implementations, Wikipedia shows the formula to compute it as (in Haskell):

main = print . last . map (subtract 1) . takeWhile (/= 1) . map (+ 1) . iterate (/2) $ 1

Answer 3

This is not a new answer -- it just bothers me that Danny's code makes it look like it's hard to do this kind of thing... it could be simplified to

(let loop ([n 1.0])
  (if (= 1 (+ 1 (/ n 2)))
    n
    (loop (/ n 2))))