ch-ch-update: series, closed-form series, and strides

[Denis Koroskin]

On Tue, 03 Feb 2009 22:43:06 +0300, Steven Schveighoffer <schveiguy at yahoo.com> wrote:

> "Denis Koroskin" wrote
>> On Tue, 03 Feb 2009 21:25:21 +0300, Sean Kelly <sean at invisibleduck.org>
>> wrote:
>>
>>> Andrei Alexandrescu wrote:
>>>> Ary Borenszweig wrote:
>>>>> Andrei Alexandrescu escribió:
>>>>>> I've updated my code and documentation to include series (as in  
>>>>>> math)
>>>>>> in the form of infinite ranges. Also series in closed form (given n
>>>>>> can compute the nth value without iterating) are supported as
>>>>>> random-access ranges.
>>>>>>
>>>>>> Also Stride is provided. The Matrix container (speaking of  
>>>>>> scientific
>>>>>> computing with D!) will support various representational choices,
>>>>>> most importantly the ones endorsed by high-performance libraries.  
>>>>>> For
>>>>>> Matrix, Stride is an important component as I'm sure anyone who's
>>>>>> ever written a matrix knows.
>>>>>>
>>>>>> http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
>>>>>> http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html
>>>>>>
>>>>>> Back to series. Finally my dream has come true: I can define a  
>>>>>> decent
>>>>>> Fibonacci series clearly and efficiently in one line of code. No  
>>>>>> more
>>>>>> idiotic recursive function that takes exponential time to finish!
>>>>>>
>>>>>> auto fib = series!("a[n-1] + a[n]")(1, 1);
>>>>>> // write 10 Fibonacci numbers
>>>>>> foreach (e; take(10, fib)) writeln(e);
>>>>>
>>>>> That is *SO* awesome!!
>>>>  Thanks! Constant-space factorial is just a line away:
>>>>  auto fact = series!("a[n] * (n + 1)")(1);
>>>> foreach (e; take(10, fact)) writeln(e);
>>>
>>> Awesome :-)  I think that proves the efficacy of the approach all by
>>> itself.
>>>
>>>
>>> Sean
>>
>> I wonder how efficent it is? Does it store last few sequence elements or
>> re-compute then again and again?
>> I wouldn't use it in the latter case.
>
> Factorial series is defined in terms of the last term, so you only need  
> to
> remember the last term.  i.e. 5! = 4! * 5.
>
> So constant space, constant time per iteration.
>

Of course, but does it *really* discard old values? That's what I doubt.

Ok, Factorial/Fibonacci is easy. How would you implement, say, the following sequence:
a[n] = a[0] + a[n / 8]; // ?

Now it is log(n) to compute from scratch but you should store O(n) elements to make it constant time.

I mean, the algorithm ought to have very good heuristics.
And sometimes it is better to re-compute elements instead of caching them.

> One thing I was confused about, you are defining in the function how to
> calculate a[n+1]?  I find it more intuitive to define what a[n] is.  For
> example,
>
> auto fib = series!("a[n - 2] + a[n - 1]")(1, 1); // reads a[n] = a[n-2] +
> a[n-1]
>
> It's even less confusing in the factorial example (IMO):
>
> auto fact = series!("a[n - 1] * n")(1);
>
> Of course, I don't know how the template-fu works, so I'm not sure if  
> it's
> possible ;)
>
> -Steve
>
>

I agree.