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