Re: idiom for recurrence relations

*To*: mathgroup at smc.vnet.net*Subject*: [mg26815] Re: [mg26714] idiom for recurrence relations*From*: Mitch Harris <maharrix at my-deja.com>*Date*: Wed, 24 Jan 2001 04:18:52 -0500 (EST)*References*: <200101180557.AAA16636@smc.vnet.net> <948rtc$kli@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

In article <948rtc$kli at smc.vnet.net>, Daniel Lichtblau <danl at wolfram.com> wrote: > maharrix at my-deja.com wrote: > > > > I have a problem which is mostly esthetic, but could have efficiency > > repercussions. First, the general question: What is the best way to > > implement recurrence relations (e.g. Fibonacci[n])? [...some possibilities deleted...] > > So, how do the above rate and what are the reasonable alternatives? > > One good way might be via matrix powers. Below I show several variations [...some variations deleted...] > fib5[n_] := MatrixPower[{{1,1},{1,0}},n-1][[1,1]] > > fib6[n_] := Fibonacci[n] [...timings deleted...] > Fifth method uses a divide-and-conquer approach in MatrixPower. So it > will be O(log(n)*M(n)) where M(n) is cost of multiplying a pair of n-bit > integers. The built-in Fibonacci code does something similar, I believe. Great answer! (I wish I had done that to begin with). Your matrix method is one kind of alternative that seems fruitful (it generalizes at least for allowing coefficients that are not constants, but doesn't work with non-linear recurrences, which is not a terrible restriction). But I have a couple of nits to pick about running times. You say that versions 2,3, and 4 are O(n^2). Yes, they are, but specifically only for the Fibonacci recurrence (and others whose growth is exponential). I would prefer to separate the number of steps performed (O(n) for these three) and then take into account the size of the answer (e.g. 1) for polynomial coefficients, you can get super-exponential growth, and for appropriate constants (e.g. binomial coefficients) you can get plain old polynomial solutions to the recurrence which gives an O(log n) multiplier. Also, you state that for method 5, that 'M(n)' is the time for multiplying 2 n-bit integers. Since method 5 is really multiplying n matrices, I would think this algorithm really O(n M(k)) where M(k) is the cost of multiplying two k by k matrices that encode a kth-order recurrence (which is currently roughly O(k^2.37) by the Coppersmith/Winograd method. As you say by divide and conquer for handling exponentiation, you can make this O(log(n) M(k)), for constant matrices (as you get with recurrences with constant coefficients). I have not taken into account the sizes of the integers being multiplied within the matrix multiplication. Thanks for the info. Your analysis is exactly what I should have done to begin with. By the way is there any sort of collection somewhere of idioms of the kind I am thinking of? e.g. those embedded in the mathematica book like for partial fractions: Fold[Plus,0,list]. Forever, I was using things like Table[Sum[list[[i]],{i,1,k}],{k,1,Length[list]}], knowing that there was a much easier funcitonal way to do it, but not knowing which functional operator to start with. -- Mitch Harris Sent via Deja.com http://www.deja.com/

**Follow-Ups**:**Re: Re: idiom for recurrence relations***From:*Daniel Lichtblau <danl@wolfram.com>

**References**:**idiom for recurrence relations***From:*maharrix@my-deja.com

**Re: Re: task**

**Re: Re: Who can help me?**

**Re: idiom for recurrence relations**

**Re: Re: idiom for recurrence relations**