Velocity Reviews > Generating equally-spaced floats with least rounding error

# Generating equally-spaced floats with least rounding error

Steven D'Aprano
Guest
Posts: n/a

 09-24-2011
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.---(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(]

[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(]

[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
Guest
Posts: n/a

 09-24-2011
On Sat, Sep 24, 2011 at 11:53 PM, Steven D'Aprano
<(E-Mail Removed)> 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
Guest
Posts: n/a

 09-24-2011
2011/9/24 Chris Angelico <(E-Mail Removed)>:
> On Sat, Sep 24, 2011 at 11:53 PM, Steven D'Aprano
> <(E-Mail Removed)> 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
Guest
Posts: n/a

 09-24-2011
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.---(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(]

> [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(]

> [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
Guest
Posts: n/a

 09-24-2011
On Sep 24, 2:53*pm, Steven D'Aprano <steve
(E-Mail Removed)> 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.---(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
Guest
Posts: n/a

 09-24-2011
Mark Dickinson wrote:

> On Sep 24, 2:53Â*pm, Steven D'Aprano <steve
> (E-Mail Removed)> 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.---(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
Guest
Posts: n/a

 09-24-2011
On Sep 24, 5:46*pm, Steven D'Aprano <steve
(E-Mail Removed)> 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
Guest
Posts: n/a

 09-24-2011
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
Guest
Posts: n/a

 09-24-2011
On Sun, Sep 25, 2011 at 12:26 AM, Mel <(E-Mail Removed)> wrote:
> low_limit + (total_width * i) / intervals
>

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

ChrisA

Chris Angelico
Guest
Posts: n/a

 09-24-2011
On Sun, Sep 25, 2011 at 3:01 AM, Steven D'Aprano
<(E-Mail Removed)> 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

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post ddoherty03 Ruby 4 07-23-2009 02:55 PM AAaron123 ASP .Net 0 10-03-2008 01:25 PM Keflavich Python 13 12-14-2007 03:56 PM itportal C Programming 9 01-17-2006 04:45 AM Kosio C Programming 44 09-23-2005 09:49 AM