RE: [xsl] Fibonacci & XSL

["Yates, Danny (ANTS)" <danny.yates@xxxxxxxxxx>]

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.Yates@xxxxxxxxxx
Phone: +44 20 7756 5012
Fax: +44 20 7612 4342


-----Original Message-----
From: Kasper Nielsen [mailto:news@xxxxxx]
Sent: 17 December 2002 11:19
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


***************************************************************************
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