floating point range generator

[Neal Holtz]

Carl Banks <imbosol at aerojockey.com> wrote in message news:<7O%Ua.8994$AO6.2045 at nwrdny02.gnilink.net>...
> ...
> A more robust version would look something like this (but it still has
> problem #3):
> 
>     def frange(start, stop, step=1.0):
>         sign = cmp(0,step)
> 	for i in xrange(sys.maxint):
>             v = start+i*step
> 	    if cmp(v,stop) != sign:
>                 break
>             yield v
> 
> The most robust way to handle this is to iterpolate, i.e., instead of
> passing start, stop, and step, pass start, stop, and n_intervals:
> 
>    def interiter(start, stop, n_intervals):
>        diff = stop - start
>        for i in xrange(n_intervals+1):
>            yield start + (i*diff)/n_intervals
> 
> An IEEE 754 (whatever) geek can probably point out even more accurate
> ways to do these.


You can easily invent examples where the number of elements generated
may (or may not) suprise you.  Here is an implementation that attempts
to account for some of the problems of floating point arithmetic:

# (See  http://www.python.org/doc/current/tut/node14.html)

def epsilon():
    """Compute machine epsilon: smallest number, e, s.t. 1 + e > 1"""
    one = 1.0
    eps = 1.0
    while (one + eps) > one:
        eps = eps / 2.0
    return eps*2.0

_Epsilon = epsilon()

def frange2( start, stop, step=1.0, fuzz=_Epsilon ):
    sign = cmp( step, 0.0 )
    _fuzz = sign*fuzz*abs(stop)
    for i in xrange(sys.maxint):
        value = start + i*step
        if cmp( stop, value + _fuzz ) != sign:
            break
        yield value

And we can generate a bunch of test cases to compare this
implementation with the first one above:

for step in frange( 0.0, 1.0, 0.01 ):
    for stop in frange( 0.01, 10.0, 0.01 ):
        l1 = [x for x in frange( 0.0, stop, step )]
        l2 = [x for x in frange2( 0.0, stop, step )]
        if l1 != l2:
            print stop, step, len(l1), len(l2)
            print repr(stop), repr(step)
            print l1
            print l2
            print

The first of many the differences noted is this:

0.06 0.01 7 6
0.060000000000000005 0.01
[0.0, 0.01, 0.02, 0.029999999999999999, 0.040000000000000001,
0.050000000000000003, 0.059999999999999998]
[0.0, 0.01, 0.02, 0.029999999999999999, 0.040000000000000001,
0.050000000000000003]

Under most normal output conditions, you would think that the stop
value was 0.06 and the step was 0.01, so you would expect to get 6
elements in the sequence.  Yet the first implementation gives you 7.
This might be surprising, as under most output conditions the last
value would appear to be equal to the stop value.  Of course, the
actual stop value is just slightly greater than 0.06.  The second
implementation gives you 6 elements in the sequence; though it can be
argued which is "correct", the second implementation is probably less
surprising in most cases.

This is just another example, of course, of the idea that if it
really, really matters how many elements are in the sequence, don't
use floating point arithmetic to control the # of iterations.