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

[Andrei Alexandrescu]

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.

I wouldn't use it either, in fact I have a dim view of all books, 
articles, and courses that promote exponential-time Fibonacci and 
linear-space factorial. It just promotes sloppy algorithmic thinking 
under the pretense that recursion is cool. (I also have a dim view of 
the FP proponents who promote the quicksort that actually doesn't sort 
in place and returns new arrays by value every iteration, consuming O(n 
log n) extra memory. But I digress.)

The size of the state held by a series is equal to the number of initial 
  arguments passed when it is constructed. The arguments are stored in a 
fixed-size array sitting in the series object. So:

auto fib = series!("a[n-1] + a[n]")(1, 1);

holds an int[2], initialized with [1, 1]. The current index in the 
series (a size_t initialized to 0) completes the state size.

When fib.next is called, the ((n+1) % 2)th element in the array is 
overwritten with the result of a[(n-1)%2] + a[n%2]. Then n is 
incremented. fib.head returns a[n%2].

In the factorial case it's simpler because the state size is 1. Since 
the state size is used as a compile-time constant, the compiler has the 
opportunity to optimize away calculations like n%1.


Andrei