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
