Hi,
Here's a pseudo-code algorithm which executes in linear time.
I've dry run it, but it's otherwise untested. To implement this
in XSLT you will need to think about recursion - but it's
pretty straightforward.
Rgds,
Dan.
-------PSEUDO-CODE---------
func fib(n) {
if (n < 1) error;
if (n = 0) return 0;
if (n = 1) return 1;
prevprev = 0;
prev = 1;
while (n >= 2) {
temp = prevprev + prev;
prevprev = prev;
prev = temp;
n = n - 1;
}
return prev;
}
--
Danny Yates
Technical Architect
Abbey National Treasury Services
E-mail: Danny(_dot_)Yates(_at_)ants(_dot_)co(_dot_)uk
Phone: +44 20 7756 5012
Fax: +44 20 7612 4342
-----Original Message-----
From: Kasper Nielsen [mailto:news(_at_)kav(_dot_)dk]
Sent: 17 December 2002 11:19
To: xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com
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
***************************************************************************
This communication (including any attachments) contains confidential
information. If you are not the intended recipient and you have received this
communication in error, you should destroy it without copying, disclosing or
otherwise using its contents. Please notify the sender immediately of the
error.
Internet communications are not necessarily secure and may be intercepted or
changed after they are sent. Abbey National Treasury Services plc does not
accept liability for any loss you may suffer as a result of interception or any
liability for such changes. If you wish to confirm the origin or content of
this communication, please contact the sender by using an alternative means of
communication.
This communication does not create or modify any contract and, unless otherwise
stated, is not intended to be contractually binding.
Abbey National Treasury Services plc. Registered Office: Abbey National House,
2 Triton Square, Regents Place, London NW1 3AN. Registered in England under
Company Registration Number: 2338548. Regulated by the Financial Services
Authority (FSA).
***************************************************************************
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list