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

[Andrei Alexandrescu]

Denis Koroskin wrote:
> Of course, but does it *really* discard old values? That's what I doubt.

It really discards old values.

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

Very simple (assuming a[0] = 1):

auto s = series("cast(uint) (log(n) / 3) + 2")(1);

At least that's what I got through expansion :o). What I'm saying is 
that series() does not do the work for you to either have unbounded 
state, backtrack as needed, or do algebraic manipulation. The series 
must come in analytic form.

It's a good point. The current implementation defines a series as k 
initial elements and a method of computing a_{n} given a_{n-1} through 
a_{n-k}. Most series come in this form. Few interesting series don't, 
but they are rare and tricky anyway; they are not supported as of yet. I 
will note that your formula above shouldn't compile (it currently does 
and runs with erratic results).

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

There's no heuristics and no computation vs. storage tradeoff. It's as 
cut and dried as it gets. Given k initial elements and a formula to 
compute an element from the past k elements, series() implements an 
infinite range. But it would be great to extend this to more 
non-analytic series.


Andrei