On Tue, Dec 24, 2013 at 01:18:34PM -0800, Andrei Alexandrescu wrote: > On 12/24/13 1:09 PM, H. S. Teoh wrote: > >On Tue, Dec 24, 2013 at 12:57:02PM -0800, Andrei Alexandrescu wrote: > >>On 12/24/13 11:59 AM, H. S. Teoh wrote: > >>>On Tue, Dec 24, 2013 at 11:35:49AM -0800, Andrei Alexandrescu wrote: > >>>>On 12/24/13 10:56 AM, Craig Dillabaugh wrote: > >>>>>On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu > >>>>>wrote: > >>>[...] > >>>>>>The integral cases are easy. We need to crack the floating point > >>>>>>case: given numbers low, up, and step, what's the closest number > >>>>>>smaller than up that's reached by repeated adds of step to low? > >>>>>> > >>>>>>Andrei > >>>>> > >>>>>Doesn't think work, or am I missing something? > >>>>> > >>>>>low + floor( (up-low)/step ) * step > >>>> > >>>>I doubt it's anything as simple as that. The magnitudes of up, low, > >>>>and step must be taken into account. > >>>[...] > >>> > >>>What about low + fmod(up-low, step)*step? Is that better? (Assuming > >>>that fmod would take relative magnitudes into account, of course.) > >> > >>No, again, I think nothing like that would work. It's hopelessly > >>naive (in addition to being plain wrong for simple inputs like > >>low=1, high=10, step=1). > >> > >>There are combinations of low, high, and step that don't even make > >>progress, i.e. step is sufficiently small compared to low to > >>effectively make low + step == low. > > > >Then what should be returned in that case? > > The same as an iota with step zero. > > >> auto next = low + step; > > > >Aren't you accumulating roundoff errors here? > > Ideally one addition is all needed for popBack. [...]
You're missing my point. I'm not talking about popBack specifically here. I'm talking about the problem of accumulated roundoff error in the implementation of iota. You're suggesting that iota should keep a running accumulator representing the current value of .front, and popFront should simply add step to this accumulator. But this kind of implementation is problematic, because it accumulates roundoff errors. Suppose evaluating current + step introduces a roundoff error of E. Then the next time we call popFront, the error becomes 2*E. Then the third time the error becomes 3*E. So after calling popFront n times, the accumulator is now off from the correct value by n*E. Since n is increasing, eventually n*E > step, which will cause iota to return the wrong number of elements in the range (not to mention that the last few elements will be completely inaccurate). Yet you're suggesting to use this method of incrementally adding step to an accumulator as the standard by which to verify the correctness of .back? That makes no sense. The only floating-point implementation of iota that guarantees the correct number of iterations (up to floating-point precision, of course) is one that *directly* calculates the value of front_i = low + i*step, instead of consecutively adding step to an accumulator, no matter whether you're calling popFront or popBack or opIndex. T -- The fact that anyone still uses AOL shows that even the presence of options doesn't stop some people from picking the pessimal one. - Mike Ellis