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