std.range.iota enhancement: supporting more types (AKA issue 10762)

[H. S. Teoh]

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