Re: Fibonacci & XSL

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