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

[Steven Schveighoffer]

"Denis Koroskin" wrote
> 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]; // ?

I don't think such a series is definable with Andrei's template.  I think 
his series template is only usable in situations where computing a[n] 
depends only on n and the elements a[n-X]..a[n-1], where X is a constant.

I'm not really a mathemetician, so I don't know the technical term for the 
differences, I'm sure there is one.

-Steve