RE: [xsl] Fibonacci & XSL

["Jason Macki" <jmacki@xxxxxxx>]

To solve this problem in linear time, do it from the bottom up, not from
the top down.

For example, if you wanted to calculate f(6) dynamically, start with 0
and work up to 6 using the results of the previous two calculations.

F(0) = 1
F(1) = 1
F(2) = f(1) + f(0) = 2
F(3) = f(2) + f(1) = 3
F(4) = f(3) + f(2) = 5
F(5) = f(4) + f(3) = 8
F(6) = f(5) + f(4) = 11


-----Original Message-----
From: Kasper Nielsen [mailto:news@xxxxxx] 
Sent: Tuesday, December 17, 2002 5:19 AM
To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
Subject: [xsl] Fibonacci & XSL


This is actually more a question of dynamic programming in XSL. If you
can't remember the function it is:

F0 = 0
F1 = 1
f(n)=f(n-1)+f(n-2) for n>=2

is it possible to make a template that calculates this in linear time (I
know it can be done in O(lg n) but linear is enogh) in xsl? The
straightforward recursive method for calculating f(n) is clearly
exponential in n.

If it is possible I would prefer an example using memoization because I
need it to a similar problem I have.

regards
  Kasper


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list