Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Python (http://www.velocityreviews.com/forums/f43-python.html)
-   -   Generating equally-spaced floats with least rounding error (http://www.velocityreviews.com/forums/t754428-generating-equally-spaced-floats-with-least-rounding-error.html)

 Steven D'Aprano 09-24-2011 01:53 PM

Generating equally-spaced floats with least rounding error

I'm trying to generate a sequence of equally-spaced numbers between a lower
and upper limit. Given arbitrary limits, what is the best way to generate a
list of equally spaced floats with the least rounding error for each point?

For example, suppose I want to divide the range 0 to 2.1 into 7 equal
intervals, then the end-points of each interval are:

(0.0)---(0.3)---(0.6)---(0.9)---(1.2)---(1.5)---(1.8)---(2.1)

and I'd like to return the values in the brackets. Using Decimal or Fraction
is not an option, I must use floats. If the exact value isn't representable
as a float, I'm okay with returning the nearest possible float.

The width of each interval is:

width = (2.1 - 0.0)/7

The relevant points can be calculated in either of two methods:

#1 add multiples of the width to the starting value, 0.

#2 subtract multiples of width from the ending value, 2.1.

(Repeated addition or subtraction should be avoided, as it increases the
amount of rounding error.)

Mathematically the two are equivalent, but due to rounding, they may not be.
Here's a run using Python 3.2:

>>> [0.0 + i*width for i in range(8)]

[0.0, 0.3, 0.6, 0.8999999999999999, 1.2, 1.5, 1.7999999999999998, 2.1]

The 4th and 7th values have rounding errors, the rest are exact.

>>> [2.1 - (7-i)*width for i in range(8)]

[0.0, 0.30000000000000027, 0.6000000000000001, 0.9000000000000001,
1.2000000000000002, 1.5, 1.8, 2.1]

The 2nd, 3rd, 4th and 5th values have rounding errors. Note that the 7th
value is exact here, but not above.

Is there a way to pick between methods #1 and #2 (or some combination of the
two) without human intervention so as to minimise the rounding error? Or is
there some other way to generate equally-spaced floats? My efforts at

--
Steven

 Chris Angelico 09-24-2011 01:58 PM

Re: Generating equally-spaced floats with least rounding error

On Sat, Sep 24, 2011 at 11:53 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> #1 add multiples of the width to the starting value, 0.
>
> #2 subtract multiples of width from the ending value, 2.1.

#3, go half and half - generate the lower half by adding to the lower
bound, and the upper half by subtracting from the upper bound. Not
sure if it'll help or not but it might be worth a shot.

ChrisA

 Vlastimil Brom 09-24-2011 02:17 PM

Re: Generating equally-spaced floats with least rounding error

2011/9/24 Chris Angelico <rosuav@gmail.com>:
> On Sat, Sep 24, 2011 at 11:53 PM, Steven D'Aprano
> <steve+comp.lang.python@pearwood.info> wrote:
>> #1 add multiples of the width to the starting value, 0.
>>
>> #2 subtract multiples of width from the ending value, 2.1.

>
> #3, go half and half - generate the lower half by adding to the lower
> bound, and the upper half by subtracting from the upper bound. Not
> sure if it'll help or not but it might be worth a shot.
>
> ChrisA
> --

Just a naive way:
#4 compute the values in both directions and use the average of the
results (of, course, given, there isn't a better way to distinguish
the values showing rounding errors automatically).

(I guess dealing manually with values obtained by .as_integer_ratio()
doesn't count as pure float operation...)

vbr

 Mel 09-24-2011 02:26 PM

Re: Generating equally-spaced floats with least rounding error

Steven D'Aprano wrote:

> I'm trying to generate a sequence of equally-spaced numbers between a
> lower and upper limit. Given arbitrary limits, what is the best way to
> generate a list of equally spaced floats with the least rounding error for
> each point?
>
> For example, suppose I want to divide the range 0 to 2.1 into 7 equal
> intervals, then the end-points of each interval are:
>
> (0.0)---(0.3)---(0.6)---(0.9)---(1.2)---(1.5)---(1.8)---(2.1)
>
> and I'd like to return the values in the brackets. Using Decimal or
> Fraction is not an option, I must use floats. If the exact value isn't
> representable as a float, I'm okay with returning the nearest possible
> float.
>
> The width of each interval is:
>
> width = (2.1 - 0.0)/7
>
> The relevant points can be calculated in either of two methods:
>
> #1 add multiples of the width to the starting value, 0.
>
> #2 subtract multiples of width from the ending value, 2.1.
>
> (Repeated addition or subtraction should be avoided, as it increases the
> amount of rounding error.)
>
> Mathematically the two are equivalent, but due to rounding, they may not
> be. Here's a run using Python 3.2:
>
>>>> [0.0 + i*width for i in range(8)]

> [0.0, 0.3, 0.6, 0.8999999999999999, 1.2, 1.5, 1.7999999999999998, 2.1]
>
> The 4th and 7th values have rounding errors, the rest are exact.
>
>
>>>> [2.1 - (7-i)*width for i in range(8)]

> [0.0, 0.30000000000000027, 0.6000000000000001, 0.9000000000000001,
> 1.2000000000000002, 1.5, 1.8, 2.1]
>
> The 2nd, 3rd, 4th and 5th values have rounding errors. Note that the 7th
> value is exact here, but not above.
>
> Is there a way to pick between methods #1 and #2 (or some combination of
> the two) without human intervention so as to minimise the rounding error?
> Or is there some other way to generate equally-spaced floats? My efforts
> at googling have not been helpful.

When I've done this with ints (usually in small embedded systems) I've
always preferred

low_limit + (total_width * i) / intervals

since it does the rounding on the biggest numbers where proportional error
will be least, and it's guaranteed to hit the low_limit and high_limit
exactly (as exactly as they can be represented, anyway.)

Mel.

 Mark Dickinson 09-24-2011 03:17 PM

Re: Generating equally-spaced floats with least rounding error

On Sep 24, 2:53*pm, Steven D'Aprano <steve
+comp.lang.pyt...@pearwood.info> wrote:
> I'm trying to generate a sequence of equally-spaced numbers between a lower
> and upper limit. Given arbitrary limits, what is the best way to generatea
> list of equally spaced floats with the least rounding error for each point?
>
> For example, suppose I want to divide the range 0 to 2.1 into 7 equal
> intervals, then the end-points of each interval are:
>
> (0.0)---(0.3)---(0.6)---(0.9)---(1.2)---(1.5)---(1.8)---(2.1)
>
> and I'd like to return the values in the brackets. Using Decimal or Fraction
> is not an option, I must use floats. If the exact value isn't representable
> as a float, I'm okay with returning the nearest possible float.

Can you explain why you're constrained not to use Fraction? Speed?

Using Fraction for intermediate calculations actually works perfectly
for this, since conversions from float to Fraction are exact, while
conversions from Fraction to float are correctly rounded. So if
you're using Python, you're not too bothered about efficiency, and you
want provably correctly-rounded results, why not use Fraction?

>>> from fractions import Fraction
>>> start, stop, n = 0.0, 2.1, 7
>>> [float(Fraction(start) + i * (Fraction(stop) - Fraction(start)) / n) for i in range(n+1)]

[0.0, 0.3, 0.6, 0.9, 1.2, 1.5, 1.8, 2.1]

--
Mark

 Steven D'Aprano 09-24-2011 04:46 PM

Re: Generating equally-spaced floats with least rounding error

Mark Dickinson wrote:

> On Sep 24, 2:53Â*pm, Steven D'Aprano <steve
> +comp.lang.pyt...@pearwood.info> wrote:
>> I'm trying to generate a sequence of equally-spaced numbers between a
>> lower and upper limit. Given arbitrary limits, what is the best way to
>> generate a list of equally spaced floats with the least rounding error
>> for each point?
>>
>> For example, suppose I want to divide the range 0 to 2.1 into 7 equal
>> intervals, then the end-points of each interval are:
>>
>> (0.0)---(0.3)---(0.6)---(0.9)---(1.2)---(1.5)---(1.8)---(2.1)
>>
>> and I'd like to return the values in the brackets. Using Decimal or
>> Fraction is not an option, I must use floats. If the exact value isn't
>> representable as a float, I'm okay with returning the nearest possible
>> float.

>
> Can you explain why you're constrained not to use Fraction? Speed?

Speed is important, but secondary to correctness. To be honest, I never even
thought of using fractions as an intermediate result -- I was thinking of
generating lists of Fractions. I think I can use this approach.

But out of curiosity, how would you do it using nothing but floats? Is there
a way?

--
Steven

 Mark Dickinson 09-24-2011 04:55 PM

Re: Generating equally-spaced floats with least rounding error

On Sep 24, 5:46*pm, Steven D'Aprano <steve
+comp.lang.pyt...@pearwood.info> wrote:
> Speed is important, but secondary to correctness. To be honest, I never even
> thought of using fractions as an intermediate result -- I was thinking of
> generating lists of Fractions. I think I can use this approach.

Speed could be improved greatly by using integer arithmetic (with some
help from the float.as_integer_ratio method) instead of using Fraction
directly, though it would require writing quite a lot more code;
Fraction's many and slow gcd calls for normalization are a problem
here, and since all denominators will be powers of 2 they're largely
unnecessary.

> But out of curiosity, how would you do it using nothing but floats? Is there
> a way?

Hmm. Beyond writing my own multiple-precision integer library using
floats as the base type, I can't think of anything obvious. :-)

--
Mark

 Steven D'Aprano 09-24-2011 05:01 PM

Re: Generating equally-spaced floats with least rounding error

Mark Dickinson wrote:

> Using Fraction for intermediate calculations actually works perfectly
> for this, since conversions from float to Fraction are exact, while
> conversions from Fraction to float are correctly rounded. So if
> you're using Python, you're not too bothered about efficiency, and you
> want provably correctly-rounded results, why not use Fraction?
>
>>>> from fractions import Fraction
>>>> start, stop, n = 0.0, 2.1, 7
>>>> [float(Fraction(start) + i * (Fraction(stop) - Fraction(start)) / n)
>>>> [for i in range(n+1)]

> [0.0, 0.3, 0.6, 0.9, 1.2, 1.5, 1.8, 2.1]

Ah, I knew it was too easy!

>>> from fractions import Fraction as F
>>> start, stop, n = 1, 3.1, 7
>>> [float(F(start) + i*(F(stop)-F(start))/n) for i in range(n+1)]

[1.0, 1.3, 1.6, 1.9000000000000001, 2.2, 2.5, 2.8000000000000003, 3.1]
>>>
>>> start, stop, n = -1, 1.1, 7
>>> [float(F(start) + i*(F(stop)-F(start))/n) for i in range(n+1)]

[-1.0, -0.7, -0.39999999999999997, -0.09999999999999996,
0.20000000000000004, 0.5000000000000001, 0.8, 1.1]

--
Steven

 Chris Angelico 09-24-2011 05:03 PM

Re: Generating equally-spaced floats with least rounding error

On Sun, Sep 25, 2011 at 12:26 AM, Mel <mwilson@the-wire.com> wrote:
> low_limit + (total_width * i) / intervals
>

Definite improvement, if the range is comparatively small. Multiply
first, then divide.

ChrisA

 Chris Angelico 09-24-2011 05:19 PM

Re: Generating equally-spaced floats with least rounding error

On Sun, Sep 25, 2011 at 3:01 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> Mark Dickinson wrote:
>
>> Using Fraction for intermediate calculations actually works perfectly
>> for this, since conversions from float to Fraction are exact, while
>> conversions from Fraction to float are correctly rounded. *So if
>> you're using Python, you're not too bothered about efficiency, and you
>> want provably correctly-rounded results, why not use Fraction?
>>

> Ah, I knew it was too easy!

Try using Fraction for the start and stop too:
>>> from fractions import Fraction as F
>>> start,stop,n = F(0),F(21,10),7
>>> [float(start+i*(stop-start)/n) for i in range(n+1)]

[0.0, 0.3, 0.6, 0.9, 1.2, 1.5, 1.8, 2.1]
>>> [float(start+i*(stop-start)/n) for i in range(n+1)]

[-1.0, -0.7, -0.4, -0.1, 0.2, 0.5, 0.8, 1.1]

(Tested in Py 3.2 for Win)

ChrisA

All times are GMT. The time now is 06:25 AM.