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

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Tue Dec 24 16:12:10 PST 2013


On 12/24/13 3:11 PM, H. S. Teoh wrote:
> You're missing my point.

It's Christmas, let's be nice to one another :o). The only problem here 
is that I didn't explain my point enough, which fostered confusion.

> 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.

No need to explain. I understand all of this already.

> 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.

Of course it does. It's just that it's quite a difficult problem. The 
current implementation is conservative at the expense of speed.

> 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.

No.

Consider:

struct IotaDouble
{
private:
     double begin, end, step, current;
     size_t index;
     enum UpdateMethod { indexed, addition, increment }
     UpdateMethod m;
     UpdateMethod initUpdate()
     {
         ... this is the difficult part ...
     }
     ...
     void popFront()
     {
         final switch (m)
         {
         case UpdateMethod.indexed:
             current = begin + ++index * step;
             break;
         case UpdateMethod.addition:
             current += step;
             break;
         case UpdateMethod.increment:
             ++current;
             break;
         }
     }
}

I suspect increment is not much faster than addition, so they could be 
merged subject to measurement. But I think the addition is quite a bit 
faster than indexing, which makes it worth special casing for. Also, the 
update method will be invariant through the lifetime of the object, 
which will play well with the branch predictor (the test may come at 
virtually or literally no cost).

The difficulty, of course, is choosing the appropriate update method 
depending on the limits and step.


Andrei



More information about the Digitalmars-d mailing list