Generating equally-spaced floats with least rounding error

[Terry Reedy]

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