Services & ResourcesWolfram ForumsMathGroup Archive

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

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