MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: idiom for recurrence relations

  • To: mathgroup at
  • Subject: [mg26815] Re: [mg26714] idiom for recurrence relations
  • From: Mitch Harris <maharrix at>
  • Date: Wed, 24 Jan 2001 04:18:52 -0500 (EST)
  • References: <> <948rtc$>
  • Sender: owner-wri-mathgroup at

In article <948rtc$kli at>,
  Daniel Lichtblau <danl at> wrote:
> maharrix at 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

[...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
> integers. The built-in Fibonacci code does something similar, I

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
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
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
2 n-bit integers. Since method 5 is really multiplying n matrices, I
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
is currently roughly O(k^2.37) by the Coppersmith/Winograd method. As
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
of the kind I am thinking of? e.g. those embedded in the mathematica
like for partial fractions: Fold[Plus,0,list]. Forever, I was using
like Table[Sum[list[[i]],{i,1,k}],{k,1,Length[list]}], knowing that
was a much easier funcitonal way to do it, but not knowing which
functional operator to start with.

Mitch Harris

Sent via

  • Prev by Date: Re: Re: task
  • Next by Date: Re: Re: Who can help me?
  • Previous by thread: Re: idiom for recurrence relations
  • Next by thread: Re: Re: idiom for recurrence relations