Re: Generating equally-spaced floats with least rounding error
On Sun, Sep 25, 2011 at 3:31 PM, Steven D'Aprano steve+comp.lang.pyt...@pearwood.info wrote: If you look again at the code I used, I did. I just did it inside the list comp. You did, but you created a Fraction from a float; my version used Fraction(21,10) instead of (effectively) Fraction(2.1). My description was a little sloppy, but what I meant was to use Fraction for the actual arguments to the function that this is implementing. Something looks a tad suspicious here... the two list comps are identical, but give completely different results, even though you don't re-assign start and stop between calls. You're not editing your results are you? wink Whooops! I had a whole lot of other commands in the scrollback (displaying intermediate results and such), and elided the rather crucial reassignment of parameters along with them! Fortunately, thanks to my reiplophobia, I still have the original session up in IDLE. This is even the most recent thing in it. sys.version '3.2 (r32:88445, Feb 20 2011, 21:29:02) [MSC v.1500 32 bit (Intel)]' 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] start, stop, n = F(-1), F(11,10), 7 [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] There, now it's honest. Sorry about that!! ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
On 9/25/2011 1:21 AM, Steven D'Aprano wrote: Terry Reedy wrote: On 9/24/2011 9:53 AM, Steven D'Aprano wrote: [...] [0.0 + i*width for i in range(8)] [0.0, 0.3, 0.6, 0.8999, 1.2, 1.5, 1.7998, 2.1] The 4th and 7th values have rounding errors, the rest are exact No they are not. Their errors are just smaller and not visible with 16 digits. Pardon. I meant that they were as close to exact as is possible in binary floats. With the exception of 0.8999... and 1.7999... I don't believe any other float can be closer to the exact value. I did mention that If the exact value isn't representable as a float, I'm okay with returning the nearest possible float. :) I do hope you did not stop with my lead-in sentence, and read to the end, where I gave you most of the answer you were looking for, without using the fractions module. -- Terry Jan Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
On Sun, Sep 25, 2011 at 3:31 PM, Steven D'Aprano steve+comp.lang.pyt...@pearwood.info wrote: 2.1 == F(21, 10) False Ahh, but that may just mean that Fraction doesn't implement an == that compares with floats. 2.1==float(F(21,10)) True This may be because one oughtn't to use == with floats anyway. F(2.1)==F(21,10) False F(2.1) Fraction(4728779608739021, 2251799813685248) That denominator is a power of 2 (2**51 as it happens), which is unsurprising for something created from an IEEE floating point value. Rounding F(21,10) off to fit into float produces this same value. ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
On 24 September 2011 23:10, Terry Reedy tjre...@udel.edu wrote: On 9/24/2011 10:18 AM, Arnaud Delobelle wrote: ((n-i)*a + i*b)/n for i in range(n+1) ['%20.18f' % x for x in [((7-i)*0.0 + i*2.1)/7 for i in range(8)]] ['0.00', '0.299989', '0.599978', '0.900133', '1.199956', '1.50', '1.800266', '2.100089'] In the two places where this disagrees with the previous result, I believe it is worse. The *0.0 adds nothing. You are still multiplying an inexactly represented 2.1 by increasingly large numbers. Even 7*2.1/7 is not exact! Of course *0.0 adds nothing in this case. I was suggesting a general solution to the problem of partitioning the interval (a, b) into n subintervals of equal length. As for 7*2.1/7 it is exactly the same as 21/10 to 18 decimal places as the output of your own solution shows below. [...] The best you can do for this example is ['%20.18f' % (i/10 ) for i in range(0, 22, 3)] ['0.00', '0.299989', '0.599978', '0.900022', '1.199956', '1.50', '1.800044', '2.100089'] 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? My suggestion was a simple answer which tries to avoid the obvious pitfalls that the naive approaches may fall into, as shown def bary(start, stop, n): ... return [((n-i)*start + i*stop)/n for i in range(n+1)] ... def width(start, stop, n): ... width = stop - start ... return [start + i*width/n for i in range(n+1)] ... Here is where the 'width' approach will fail: width(-1.0, 1e-20, 4) [-1.0, -0.75, -0.5, -0.25, 0.0] bary(-1.0, 1e-20, 4) [-1.0, -0.75, -0.5, -0.25, 1e-20] -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
Terry Reedy wrote: I do hope you did not stop with my lead-in sentence, and read to the end, where I gave you most of the answer you were looking for, without using the fractions module. Yes, I read your entire post, thank you, and for my purposes I'm happy with the fractions module. -- Steven -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
On 9/25/2011 3:36 AM, Arnaud Delobelle wrote: On 24 September 2011 23:10, Terry Reedytjre...@udel.edu wrote: The best you can do for this example is ['%20.18f' % (i/10 ) for i in range(0, 22, 3)] ['0.00', '0.299989', '0.599978', '0.900022', '1.199956', '1.50', '1.800044', '2.100089'] 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.00 0.00 (3, 10) 0.299989 0.299989 (6, 10) 0.599978 0.599978 (9, 10) 0.900022 0.900022 (12, 10) 1.199956 1.199956 (15, 10) 1.50 1.50 (18, 10) 1.800044 1.800044 (21, 10) 2.100089 2.100089 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 -- http://mail.python.org/mailman/listinfo/python-list
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.8999, 1.2, 1.5, 1.7998, 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.30027, 0.6001, 0.9001, 1.2002, 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. -- Steven -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
On Sat, Sep 24, 2011 at 11:53 PM, Steven D'Aprano steve+comp.lang.pyt...@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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
2011/9/24 Chris Angelico ros...@gmail.com: On Sat, Sep 24, 2011 at 11:53 PM, Steven D'Aprano steve+comp.lang.pyt...@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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
On Sep 24, 2011 2:59 PM, Chris Angelico ros...@gmail.com wrote: On Sat, Sep 24, 2011 at 11:53 PM, Steven D'Aprano steve+comp.lang.pyt...@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 #4 the barycentric approach. ((n-i)*a + i*b)/n for i in range(n+1) Gives you n+1 equally spaced values between a and b inclusive Arnaud -- http://mail.python.org/mailman/listinfo/python-list
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.8999, 1.2, 1.5, 1.7998, 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.30027, 0.6001, 0.9001, 1.2002, 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. -- http://mail.python.org/mailman/listinfo/python-list
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 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? 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 -- http://mail.python.org/mailman/listinfo/python-list
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 -- http://mail.python.org/mailman/listinfo/python-list
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
On Sun, Sep 25, 2011 at 12:26 AM, Mel mwil...@the-wire.com wrote: low_limit + (total_width * i) / intervals Definite improvement, if the range is comparatively small. Multiply first, then divide. ChrisA -- http://mail.python.org/mailman/listinfo/python-list
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.9001, 2.2, 2.5, 2.8003, 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.39997, -0.09996, 0.20004, 0.5001, 0.8, 1.1] -- Steven -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
On Sun, Sep 25, 2011 at 3:01 AM, Steven D'Aprano steve+comp.lang.pyt...@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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
On Sep 24, 6:01 pm, Steven D'Aprano steve +comp.lang.pyt...@pearwood.info wrote: 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.9001, 2.2, 2.5, 2.8003, 3.1] I believe that's still giving correctly-rounded results. Note that the stop value of 3.1 isn't exactly 3.1 here: it's 3.100088817841970012523233890533447265625 So the 4th value above is the closest float to 4/7 * 1.0 + 3/7 * 3.100088817841970012523233890533447265625. -- Mark -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
On 24 September 2011 18:01, Steven D'Aprano steve+comp.lang.pyt...@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? 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.9001, 2.2, 2.5, 2.8003, 3.1] start, stop, n = 1, 3.1, 7 [((n-i)*start + i*stop)/n for i in range(n+1)] [1.0, 1.3, 1.5999, 1.9001, 2.2, 2.5, 2.8003, 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.39997, -0.09996, 0.20004, 0.5001, 0.8, 1.1] start, stop, n = -1, 1.1, 7 [((n-i)*start + i*stop)/n for i in range(n+1)] [-1.0, -0.7001, -0.39997, -0.09996, 0.20004, 0.5, 0.8, 1.1] On these examples, using fractions is no better than what I suggested in my previous post. -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
Arnaud Delobelle arno...@gmail.com wrote: 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.39997, -0.09996, 0.20004, 0.5001, 0.8, 1.1] start, stop, n = -1, 1.1, 7 [((n-i)*start + i*stop)/n for i in range(n+1)] [-1.0, -0.7001, -0.39997, -0.09996, 0.20004, 0.5, 0.8, 1.1] On these examples, using fractions is no better than what I suggested in my previous post. Why not use Decimal if one needs exact endpoints? Something like: def drange(start, stop, step=1): if (step == 0): raise ValueError(step must be != 0) with localcontext() as ctx: ctx.traps[Inexact] = True x = start cmp = -1 if step 0 else 1 while x.compare(stop) == cmp: yield float(x) x += step list(drange(Decimal(1), Decimal(3.1), Decimal(0.3))) [1.0, 1.3, 1.6, 1.9, 2.2, 2.5, 2.8] list(drange(Decimal(-1), Decimal(1.1), Decimal(0.3))) [-1.0, -0.7, -0.4, -0.1, 0.2, 0.5, 0.8] list(drange(Decimal(-1), Decimal(1.1), Decimal(0.1823612873))) [-1.0, -0.8176387127, -0.6352774254, -0.4529161381, -0.2705548508, -0.0881935635, 0.0941677238, 0.2765290111, 0.4588902984, 0.6412515857, 0.823612873, 1.0059741603] list(drange(Decimal(-1), Decimal(1.1), Decimal(1)/3)) Traceback (most recent call last): File stdin, line 1, in module File stdin, line 10, in drange File /usr/lib/python3.2/decimal.py, line 1178, in __add__ ans = ans._fix(context) File /usr/lib/python3.2/decimal.py, line 1652, in _fix context._raise_error(Inexact) File /usr/lib/python3.2/decimal.py, line 3836, in _raise_error raise error(explanation) decimal.Inexact: None Stefan Krah -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
import numpy numpy.arange(0, 3, 0.3) array([ 0. , 0.3, 0.6, 0.9, 1.2, 1.5, 1.8, 2.1, 2.4, 2.7]) -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
On 9/24/2011 9:53 AM, 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 Calculating width is the fundamental problem. .3 cannot be exactly represented in binary, and higher multiples with multiply the error. 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.8999, 1.2, 1.5, 1.7998, 2.1] The 4th and 7th values have rounding errors, the rest are exact No they are not. Their errors are just smaller and not visible with 16 digits. width = (2.1 - 0.0)/7 ['%20.18f' % x for x in [0.0 + i*width for i in range(8)]] ['0.00', '0.299989', '0.599978', '0.899911', '1.199956', '1.50', '1.799822', '2.100089'] On 9/24/2011 10:18 AM, Arnaud Delobelle wrote: ((n-i)*a + i*b)/n for i in range(n+1) ['%20.18f' % x for x in [((7-i)*0.0 + i*2.1)/7 for i in range(8)]] ['0.00', '0.299989', '0.599978', '0.900133', '1.199956', '1.50', '1.800266', '2.100089'] In the two places where this disagrees with the previous result, I believe it is worse. The *0.0 adds nothing. You are still multiplying an inexactly represented 2.1 by increasingly large numbers. Even 7*2.1/7 is not exact! My answer is the same as Mark's. Do exact calculation with fractions (whether using Fraction or not) and convert to float. I believe the least common multiple of a.as_integer_ratio[1], b.as_integer_ratio[1], and n is the common denominator needed to convert the numerators to a range() output. For the current problem, that is lcm(10,7) = 70. The best you can do for this example is ['%20.18f' % (i/10 ) for i in range(0, 22, 3)] ['0.00', '0.299989', '0.599978', '0.900022', '1.199956', '1.50', '1.800044', '2.100089'] Notice that the last place errors are all less than 50, so printing to 16 places will make them appear 'exact'. Without being fancy (to see than you can cancel 7), you get the same output with ['%20.18f' % (i/70 ) for i in range(0, 148, 21)] ['0.00', '0.299989', '0.599978', '0.900022', '1.199956', '1.50', '1.800044', '2.100089'] In the two places where these disagree with the first (your original) they are *better*, with absolute error in the last places of 22 versus 89 and 44 versus 178 for .9 and 1.8. The last place errors greater than 50 gave you the 'inexact' answers in your post, and indeed, they are not the best possible. -- Terry Jan Reedy -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
Arnaud Delobelle wrote: On these examples, using fractions is no better than what I suggested in my previous post. I'm sorry, I can't see your previous post. Perhaps it isn't available on my news provider? -- Steven -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
Terry Reedy wrote: On 9/24/2011 9:53 AM, Steven D'Aprano wrote: [...] [0.0 + i*width for i in range(8)] [0.0, 0.3, 0.6, 0.8999, 1.2, 1.5, 1.7998, 2.1] The 4th and 7th values have rounding errors, the rest are exact No they are not. Their errors are just smaller and not visible with 16 digits. Pardon. I meant that they were as close to exact as is possible in binary floats. With the exception of 0.8999... and 1.7999... I don't believe any other float can be closer to the exact value. I did mention that If the exact value isn't representable as a float, I'm okay with returning the nearest possible float. :) -- Steven -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
Chris Angelico wrote: On Sun, Sep 25, 2011 at 3:01 AM, Steven D'Aprano steve+comp.lang.pyt...@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: If you look again at the code I used, I did. I just did it inside the list comp. 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] Something looks a tad suspicious here... the two list comps are identical, but give completely different results, even though you don't re-assign start and stop between calls. You're not editing your results are you? wink But seriously, you were freaking me out there for a bit. I couldn't see why pulling the conversion to fraction outside of the list comp was giving different results. And then it hit me... 2.1 == F(21, 10) False You're testing different numbers from me. Try again with F(2.1) as the stop value. -- Steven -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating equally-spaced floats with least rounding error
On Sep 24, 6:53 am, 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. Use numpy. from numpy import mgrid seq = mgrid[0.0:2.1:8j] seq array([ 0. , 0.3, 0.6, 0.9, 1.2, 1.5, 1.8, 2.1]) for x in seq: print repr(x) 0.0 0.2 0.59998 0.89991 1.2 1.5 1.7998 2.1001 -- http://mail.python.org/mailman/listinfo/python-list
