D Recurrences

[Ben Grabham]

On 09/06/11 18:11, Steven Schveighoffer wrote:
> On Thu, 09 Jun 2011 13:06:54 -0400, Ben Grabham <Evil.Nebster at gmail.com>
> wrote:
>
>> On 09/06/11 17:57, bearophile wrote:
>>> Ben Grabham:
>>>
>>>> import std.range;
>>>> import std.stdio;
>>>> int main() {
>>>> auto a = recurrence!("a[n-1] + a[n-2]")(0,1);
>>>> int i = 0;
>>>> foreach(int n; a) {
>>>> if(i++> 20) break;
>>>> writefln("%d", n);
>>>> }
>>>> return 0;
>>>> }
>>>
>>> This program does something similar to yours (but it doesn't print
>>> newlines):
>>>
>>>
>>> import std.stdio, std.range;
>>>
>>> void main() {
>>> auto fib = recurrence!q{ a[n-1] + a[n-2] }(0, 1);
>>> writeln(take(fib, 21));
>>> }
>>>
>>> Bye,
>>> bearophile
>>
>> Yeah, thanks
>>
>> I just wanted to post a bit of code which went wrong :P
>> Didn't look for optimisations.
>>
>> Also, how come recurrence isn't properly lazy?
>> If I define a recurrence and iterate over it twice with foreach, it
>> takes the same amount of time due to the stack size being set. Is
>> there a way of defining a lazy list that stores the results when
>> calculated?
>
> That's not lazy, that's caching. lazy is 'calculate this when asked'.
>
> You can cache with array:
>
> auto cached = array(take(fib, 21));
> // cached now contains the first 21 elements of fib.
>
> -Steve

I tried that, but how can I calculate the values only when I want them? 
Would I have to store them in a linked list? Since if I know that I will 
need 100000 prime numbers, it takes my old pc about 4.7 seconds to 
calculate them. But can I only calculate them when I need them?

I am running through the recurrence twice so I don't want to calculate 
it twice.

This is theoretical so please no answers like put them both in one loop, 
etc.

Thanks for all the info so far! I'm learning quite a lot!

Thanks,
Nebster