On Tue, 03 Feb 2009 22:43:06 +0300, Steven Schveighoffer <[email protected]>
wrote:
"Denis Koroskin" wrote
On Tue, 03 Feb 2009 21:25:21 +0300, Sean Kelly <[email protected]>
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.
