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

[H. S. Teoh]

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?


> Try this to verify approaches:
> 
> #!/Users/aalexandre/bin/rdmd
> import std.stdio, std.conv, std.math;
> 
> void main(string[] args)
> {
>     auto low = to!double(args[1]);
>     auto up = to!double(args[2]);
>     auto step = to!double(args[3]);
>     writeln("Predicted: ", low + fmod(up-low, step)*step);
>     for (;;)
>     {
>         auto next = low + step;

Aren't you accumulating roundoff errors here? Since + may introduce an
error of 1/2 ulp, if your loop runs in n steps, wouldn't it accumulate
an error of n/2 ulps? For large n, this would significantly skew your
results.


>         if (next >= up) break;
>         low = next;
>     }
>     writeln("Actual: ", low);
> }
[...]


T

-- 
All problems are easy in retrospect.