On 24/12/13 13:58, monarch_dodra wrote:
> I think you are missing the point of what happens if the step is not 1 (or if
> the passed in type can have fractional input). EG:
>
> iota(0, 105, 10);
> or
> iota(0, 10.5);
>
> In this case, "back" should be 100, and not 95. To compute back, you need to be
> able to evaluate length, and to add length*inc to front.

Oh, snap.  Have we been working on the same problems for too long? :-)

On Tue, Dec 24, 2013 at 11:57:03AM +0000, Jakob Ovrum wrote:
> On Tuesday, 24 December 2013 at 11:47:12 UTC, Francesco Cattoglio wrote:
> >Correct, but there's no way to compute "back" with less than O(n)
> >complexity, unless division by increment is available. (Actually,
> >I think we can achieve O(log n) with multiplication alone, but I
> >think it might be lots of work with very little benefits)
> >I should have specified better: we need to provide `back', and
> >Andrei suggested that no primitive should be more than complex
> >than O(1).
> 
> Implement `back` is really trivial.
> 
> Simplified example:
> ---
> auto iota(T)(T start, T end)
> {
>     static struct Result
>     {
>         T start, end;
> 
>         bool empty() @property { return start == end; }
>         T front() @property { return start; }
>         void popFront() { ++start; }
>         T back() @property { return end; }
>         void popBack() { --end; }
>         // etc
>     }
> 
>     return Result(start, --end);
> }
> ---

This code is wrong for iota(1.0, 9.5), because .back must be of the form start + n*step for some integer n, but in this case end is not an integral multiple of step away from start. (It's not only wrong for .back, it also won't terminate because start==end will never hold.)


T

-- 
I think the conspiracy theorists are out to get us...

On 24/12/13 16:39, H. S. Teoh wrote:
> This code is wrong for iota(1.0, 9.5), because .back must be of the form
> start + n*step for some integer n, but in this case end is not an
> integral multiple of step away from start. (It's not only wrong for
> .back, it also won't terminate because start==end will never hold.)

I don't see the reason why there needs to be a start == end condition -- surely start >= end will suffice?

On 12/24/13 3:57 AM, Jakob Ovrum wrote:
>          bool empty() @property { return start == end; }

This is better start >= end if ordering comparisons are supported.

Andrei

On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:
> On 24/12/13 13:58, monarch_dodra wrote:
>> I think you are missing the point of what happens if the step is not 1
>> (or if
>> the passed in type can have fractional input). EG:
>>
>> iota(0, 105, 10);
>> or
>> iota(0, 10.5);
>>
>> In this case, "back" should be 100, and not 95. To compute back, you
>> need to be
>> able to evaluate length, and to add length*inc to front.
>
> Oh, snap.  Have we been working on the same problems for too long? :-)

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

On Tue, Dec 24, 2013 at 09:10:53AM -0800, Andrei Alexandrescu wrote:
> On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:
> >On 24/12/13 13:58, monarch_dodra wrote:
> >>I think you are missing the point of what happens if the step is not 1 (or if the passed in type can have fractional input). EG:
> >>
> >>iota(0, 105, 10);
> >>or
> >>iota(0, 10.5);
> >>
> >>In this case, "back" should be 100, and not 95. To compute back, you need to be able to evaluate length, and to add length*inc to front.
> >
> >Oh, snap.  Have we been working on the same problems for too long? :-)
> 
> 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?
[...]

The closest number is simply step*floor((up-low)/step). There's probably
a better way to write that expression that avoids bad roundoff errors,
though.


T

-- 
Why can't you just be a nonconformist like everyone else? -- YHL

On Tue, Dec 24, 2013 at 09:27:54AM -0800, H. S. Teoh wrote:
> On Tue, Dec 24, 2013 at 09:10:53AM -0800, Andrei Alexandrescu wrote:
> > On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:
> > >On 24/12/13 13:58, monarch_dodra wrote:
> > >>I think you are missing the point of what happens if the step is not 1 (or if the passed in type can have fractional input). EG:
> > >>
> > >>iota(0, 105, 10);
> > >>or
> > >>iota(0, 10.5);
> > >>
> > >>In this case, "back" should be 100, and not 95. To compute back, you need to be able to evaluate length, and to add length*inc to front.
> > >
> > >Oh, snap.  Have we been working on the same problems for too long? :-)
> > 
> > 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?
> [...]
> 
> The closest number is simply step*floor((up-low)/step). There's
> probably a better way to write that expression that avoids bad
> roundoff errors, though.
[...]

Maybe (up - fmod((up-low), step)) might be better? I'm not 100% sure.


T

-- 
VI = Visual Irritation

On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu
wrote:
> On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:
>> On 24/12/13 13:58, monarch_dodra wrote:
>>> I think you are missing the point of what happens if the step is not 1
>>> (or if
>>> the passed in type can have fractional input). EG:
>>>
>>> iota(0, 105, 10);
>>> or
>>> iota(0, 10.5);
>>>
>>> In this case, "back" should be 100, and not 95. To compute back, you
>>> need to be
>>> able to evaluate length, and to add length*inc to front.
>>
>> Oh, snap.  Have we been working on the same problems for too long? :-)
>
> 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

On Tuesday, 24 December 2013 at 18:56:02 UTC, Craig Dillabaugh
wrote:
> On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu
> wrote:
>> On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:
clip
>
> Doesn't think work, or am I missing something?
>
> low + floor( (up-low)/step ) * step

I meant "Doesn't this work". Why can't I ever make a post without
a typo!

On Tue, Dec 24, 2013 at 06:57:50PM +0000, Craig Dillabaugh wrote:
> On Tuesday, 24 December 2013 at 18:56:02 UTC, Craig Dillabaugh wrote:
> >On Tuesday, 24 December 2013 at 17:10:53 UTC, Andrei Alexandrescu wrote:
> >>On 12/24/13 5:09 AM, Joseph Rushton Wakeling wrote:
> clip
> >
> >Doesn't think work, or am I missing something?
> >
> >low + floor( (up-low)/step ) * step
> 
> I meant "Doesn't this work". Why can't I ever make a post without a typo!

You mean, a tpyo? :-P


T

-- 
No! I'm not in denial!