D Recurrences

Ben Grabham Evil.Nebster at gmail.com
Thu Jun 9 11:02:47 PDT 2011


On 09/06/11 18:49, Steven Schveighoffer wrote:
> 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

Thanks, that should do the trick!
At the moment I was using auto elems = array(chain(elems, take(primes - 
elems.length))); or something similar to that

Also, when using a foreach, is there a special syntax that says include 
the last number?
As an example, if I want to loop from -n to +n, I have to do foreach(i; 
-n..n+1)

Thanks,
Nebster


More information about the Digitalmars-d mailing list