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?

Ordnance

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))))

Barber

Correct, the only thing to look out for is that this assumes we have a base 2 number. There may be cases in other programming languages that it is a BCD. – Subminiature

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

Plumbing

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))))

Faunus

Maybe I should talk Neil into adding machine-epsilon to racket/math ? – Ordnance

IIUC, there are a whole bunch of these useful things, right? He might have some of them in the plot library already. – Faunus

Could be. The Science Collection has machine-epsilon already. – Ordnance

Answer 4

The existing answers are needlessly complicated, and might lead to non-portable code.

The correct answer is, as documented in Racket's math/flonum package is to use the epsilon.0 value, which will be correct for the current machine, and which won't require you to compute it by hand:

 (require math/flonum)  
 epsilon.0

Dail

Good point. The math/flonum library didn’t exist back in ‘12 though. I guess I succeeded in talking Neil into adding it :-) – Ordnance