Using Fold to Compute a Linear Repeat Result Based on Several Previous Values

Question

I have a linear recurrence problem when the next element relies on more than just the previous value, for example. Fibonacci sequence. One method computing the element n ^th is to determine it by calling a function, for example.

Fibonacci[0] = 0; Fibonacci[1] = 1; Fibonacci[n_Integer?Positive] := Fibonacci[n] + Fibonacci[n - 1] 

and for the sequence I'm working with, this is exactly what I'm doing. (The definition is inside a Module , so I don’t pollute Global` .) However, I am going to use this with 2 ¹⁰ - 2 ¹³ so I worry about the extra overhead when I just need the last term and none of the previous elements. I would like to use Fold to do this, but Fold only conveys directly the previous result, which means that it is not directly useful for the general linear recursion problem.

I need a couple of functions to replace Fold and FoldList , which pass a certain number of elements of the previous sequence to the function, i.e.

 In[1] := MultiFoldList[f, {1,2}, {3,4,5}] (* for lack of a better name *) Out[1]:= {1, 2, f[3,2,1], f[4,f[3,2,1],2], f[5,f[4,f[3,2,1],2],f[3,2,1]]} 

I had something that did this, but I closed the notebook before saving it. So, if I rewrote it myself, I will send it.

Edit : why am I not using RSolve or MatrixPower to solve this problem. My specific problem is that I am performing an n-point Pade approximant to analytically continue the function that I know only at a given number of points on the imaginary axis, {z _i }. Part of creating an approximation is to create a set of coefficients a _i , which is another recurrence relation, which is then fed into the final relation

 A[n+1]== A[n] + (z - z[[n]]) a[[n+1]] A[n-1] 

which defies neither RSolve nor MatrixPower , at least I see.

Answer 1

Can RecurrenceTable complete this task for you?

Find the 1000th term in the repetition depending on the two previous values:

 In[1]:= RecurrenceTable[{a[n] == a[n - 1] + a[n - 2], a[1] == a[2] == 1}, a, {n, {1000}}] Out[1]= {4346655768693745643568852767504062580256466051737178040248172\ 9089536555417949051890403879840079255169295922593080322634775209689623\ 2398733224711616429964409065331879382989696499285160037044761377951668\ 49228875} 

Edit: If your recurrence is determined by the function f[m, n] , which does not like to get estimates for non-numeric m and n, you can use Condition :

 In[2]:= f[m_, n_] /; IntegerQ[m] && IntegerQ[n] := m + n 

Repetition table in terms of f :

 In[3]:= RecurrenceTable[{a[n] == f[a[n - 1], a[n - 2]], a[1] == a[2] == 1}, a, {n, {1000}}] Out[3]= {4346655768693745643568852767504062580256466051737178040248172\ 9089536555417949051890403879840079255169295922593080322634775209689623\ 2398733224711616429964409065331879382989696499285160037044761377951668\ 49228875} 

Answer 2

Several collapsible lists may be useful, but this would not be an efficient way to get linear recursions valued for large inputs. A couple of alternatives are using RSolve or matrix powers multiplied by a vector of initial values.

These are the methods used, for example, if the nth member is n-1, plus two times the n-2 member.

 f[n_] = f[n] /. RSolve[{f[n] == f[n - 1] + 2*f[n - 2], f[1] == 1, f[2] == 1}, f[n], n][[1]] 

Out [67] = 1/3 (- (- 1) ^ n + 2 ^ n)

 f2[n_Integer] := Last[MatrixPower[{{0, 1}, {2, 1}}, n - 2].{1, 1}] {f[11], f2[11]} 

Out [79] = {683, 683}

Daniel Lichtblow Wolfram Research

Answer 3

Almost confusing joke, but you can use the side effect of NestWhileList

 fibo[n_] := Module[{i = 1, s = 1}, NestWhileList[ s &, 1, (s = Total[{##}]; ++i < n) &, 2]]; 

Good performance:

 In[153]:= First@Timing @fibo[10000] Out[153]= 0.235 

Changing the last 2 to any integer, you can pass the last k results of your function (in this case, Total []).

Answer 4

LinearRecurrence and RecurrenceTable very useful.

For small cores, the MatrixPower method that Daniel gave is the fastest.

For some problems this may not apply, and you may need to minimize your own.

I will use Nest because I believe that this is suitable for this problem, but a similar design can be used with Fold.

A concrete example, the Fibonacci sequence. It may not be the cleanest for this, but I believe that you will see the utility when I continue.

 fib[n_] := First@Nest [{##2, # + #2} & @@ # &, {1, 1}, n - 1] fib[15] Fibonacci[15] 

Here I use Apply ( @@ ) so that I can access elements with # , #2 , etc., rather than #[[1]] , etc. I use SlotSequence to remove the first item from the old list and Sequence to the new list at the same time.

If you are going to work with the entire list at once, then a simple Append[ Rest@ #, ... might be better. Any method can be easily generalized. For example, a simple implementation of linear recurrence

  lr[a_, b_, n_Integer] := First@Nest [Append[ Rest@ #, a.#] &, b, n - 1] lr[{1,1}, {1,1}, 15] 

(the kernel is in reverse order from the built-in LinearRecurrence )