D Recurrences

[Steven Schveighoffer]

On Thu, 09 Jun 2011 13:31:18 -0400, Ben Grabham <Evil.Nebster at gmail.com>  
wrote:

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

It's a recurring sequence.  As such, each element depends on the previous  
n elements.  I don't see how you can only calculate them when needed,  
unless you want to do some sort of memoization with recursion.  recurrence  
expects to be traversed in a certain order, it's sort of like dynamic  
programming.

The array simply stores all the values needed to an array, so you can  
re-access the same values without running through the recurrence.

One thing you could do is using Appender, you can continue a recurrence.   
So let's say you need the 5th element of the array:

alias recurrence!q{ a[n-1] + a[n-2] } fib;

Appender!int app;

app.put(take(fib(0, 1), 5));

auto elems = app.data;
auto the5thElement = elems[4];

And now, you need the 10th element:

app.put(take(fib(elems[$-2], elems[$-1]), 10 - elems.length)); // extend  
sequence to 10 elements

elems = app.data; // need to re-retrieve the elements
auto the10thElemet = elems[9];

Kind of ugly, but maybe it's close enough to what you want.

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

Yes, you only run through it once, then use the array with the cached data  
to retrieve what you want.  Accessing the array does not recalculate the  
data.

The Appender solution simply keeps a running cache of the data.  You could  
probably abstract out the 'extending' function.  In fact, this whole thing  
could be abstracted into a 'cached recurrence' type.

-Steve