Generating equally-spaced floats with least rounding error
Terry Reedy
tjreedy at udel.edu
Mon Sep 26 02:58:57 CEST 2011
On 9/25/2011 3:36 AM, Arnaud Delobelle wrote:
> On 24 September 2011 23:10, Terry Reedy<tjreedy at udel.edu> wrote:
>> The best you can do for this example is
>>>>> ['%20.18f' % (i/10 ) for i in range(0, 22, 3)]
>> ['0.000000000000000000', '0.299999999999999989', '0.599999999999999978',
>> '0.900000000000000022', '1.199999999999999956', '1.500000000000000000',
>> '1.800000000000000044', '2.100000000000000089']
>
> Can you give an implementation for any interval (a, b) where a, b are
> floats and any partition size n where n is a positive int?
I was leaving that as an exercise for Stephen ;-)
but since he is satisfied with using Franctions ...
I accepted the challenge and (I believe) did it.
I first separated float-fractions conversions from generating equally
spaced fractions. While this does not make much if any difference if and
when one converts back to floats, testing with (21,10), for instance, as
input is much easier than with (2.1).as_integer_ratio() ==
(4728779608739021, 2251799813685248). In some applications, small
integer ratios are wanted anyway instead of floats. The main
complication in the code is getting all outputs to have the smallest
possible common denominator across the entire series.
#! python3 -- frange.py
# Copyright 2011 Terry Jan Reedy: use with acknowledgement
'''Generate n+1 equally spaced fractions or float given two endpoints
and the number n of intervals'''
from fractions import gcd
def floatrange(a, b, n):
'''Yield floats a, b, and n-1 equally spaced floats in between.'''
for num,dem in fracrange(a.as_integer_ratio(),
b.as_integer_ratio(), n):
yield num/dem
def fracrange(frac1, frac2, n):
'''Yield fractions frac1, frac2 and n-1 equally spaced fractions in
between.
Fractions are represented as (numerator, denominator > 0) pairs.
For output, use the smallest common denominator of the inputs
that makes the numerator range an even multiple of n.
'''
n1, d1 = frac1
n2, d2 = frac2
dem = d1 * d2 // gcd(d1, d2)
start = n1 * (dem // d1)
stop = n2 * (dem // d2)
rang = stop - start
q, r = divmod(rang, n)
if r:
gcd_r_n = gcd(r, n)
m = n // gcd_r_n
dem *= m
start *= m
stop *= m
step = rang // gcd_r_n # rang * m // n
else:
step = q # if r==0: gcd(r,n)==n, m==1, rang//n == q
for num in range(start, stop+1, step):
yield num,dem
for (i,j), x in zip(fracrange((0,1), (21,10), 7), floatrange(0.0, 2.1, 7)):
print((i,j), '%20.18f' % (i/j ), '%20.18f' % x )
print()
for i,j in fracrange((1,10), (22,10), 7): print(i,j)
print()
for i,j in fracrange((1,5), (1,1), 6): print(i,j)
# output
(0, 10) 0.000000000000000000 0.000000000000000000
(3, 10) 0.299999999999999989 0.299999999999999989
(6, 10) 0.599999999999999978 0.599999999999999978
(9, 10) 0.900000000000000022 0.900000000000000022
(12, 10) 1.199999999999999956 1.199999999999999956
(15, 10) 1.500000000000000000 1.500000000000000000
(18, 10) 1.800000000000000044 1.800000000000000044
(21, 10) 2.100000000000000089 2.100000000000000089
1 10
4 10
7 10
10 10
13 10
16 10
19 10
22 10
3 15
5 15
7 15
9 15
11 15
13 15
15 15
--
Terry Jan Reedy
More information about the Python-list
mailing list