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

[Steven Schveighoffer]

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

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