Subject: Re: [xsl] Fibonacci & XSL From: Mike Brown <mike@xxxxxxxx> Date: Tue, 17 Dec 2002 12:43:18 -0700 (MST) |
Kasper Nielsen wrote: > 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. I have no idea if this meets your complexity requirements. I was just testing 4suite's tail recursion optimization with it a couple months ago. <?xml version="1.0" encoding="utf-8"?> <!-- Fibonacci Numbers if n = 0, f(n) = 0 if n = 1, f(n) = 1 otherwise, f(n) = f(n-2) + f(n-1) tail-recursive version based on Scheme code by Ben Gum and John David Stone, at http://www.math.grin.edu/~gum/courses/151/readings/tail-recursion.xhtml --> <xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"> <xsl:output method="text" indent="no"/> <xsl:param name="n" select="100"/> <xsl:template match="/"> <xsl:value-of select="concat('f(',$n,') = ')"/> <xsl:call-template name="fibo"> <xsl:with-param name="n" select="$n"/> </xsl:call-template> </xsl:template> <xsl:template name="fibo"> <xsl:param name="n" select="0"/> <xsl:call-template name="fibo-guts"> <xsl:with-param name="current" select="0"/> <xsl:with-param name="next" select="1"/> <xsl:with-param name="remaining" select="$n"/> </xsl:call-template> </xsl:template> <xsl:template name="fibo-guts"> <xsl:param name="current" select="0"/> <xsl:param name="next" select="0"/> <xsl:param name="remaining" select="0"/> <xsl:choose> <xsl:when test="$remaining = 0"> <xsl:value-of select="$current"/> </xsl:when> <xsl:otherwise> <xsl:call-template name="fibo-guts"> <xsl:with-param name="current" select="$next"/> <xsl:with-param name="next" select="$current + $next"/> <xsl:with-param name="remaining" select="$remaining - 1"/> </xsl:call-template> </xsl:otherwise> </xsl:choose> </xsl:template> </xsl:stylesheet> Mike -- Mike J. Brown | http://skew.org/~mike/resume/ Denver, CO, USA | http://skew.org/xml/ XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
RE: [xsl] Fibonacci & XSL, bryan | Thread | RE: [xsl] Fibonacci & XSL, Yates, Danny (ANTS) |
RE: [xsl] combining two variables t, Mark Wilgus | Date | RE: [xsl] combining two variables t, bix xslt |
Month |