Re: Fibonacci & XSL

On Tue, 2002-12-17 at 12:19, 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?

What about something such as (not tested, may include typos...):

<xsl:template name="fibonacci">
 <xsl:param name="n"/>
 <xsl:choose>
  <xsl:when test="$n &lt;= 0">
   <xsl:text>0</xsl:text>
  </xsl:when>
  <xsl:when test="$n = 1">
   <xsl:text>1</xsl:text>
  </xsl:when>
  <xsl:otherwise>
   <xsl:call-template name="fiboloop">
    <xsl:with-param name="fn1" select="1"/>
    <xsl:with-param name="fn2" select="0"/>
    <xsl:with-param name="remains" select="$n - 2"/>
   </xsl:call-template>
 </xsl:choose>
</xsl:template>

<xsl:template name="fiboloop">
 <xsl:param name="fn1"/>
 <xsl:param name="fn2"/>
 <xsl:param name="remains"/>
 <xsl:variable name="current" select="$fn1 + $fn2"/>
 <xsl:choose>
  <xsl:when test="$remains = 0">
   <xsl:value-of select="$current">
  </xsl:when>
  <xsl:otherwise>
   <xsl:call-template name="fiboloop">
    <xsl:with-param name="fn1" select="$current"/>
    <xsl:with-param name="fn2" select="$fn1"/>
    <xsl:with-param name="remains" select="$remains - 1"/>
   </xsl:call-template>
 </xsl:choose>
</xsl:template>


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

For this you would need to store the values already calculated in a
variable, use a node-set extension and do a copy-of the previous values
at each iteration and this would probably not scale that well.

Hope this helps,

Eric
-- 
Freelance consulting and training.
                                            http://dyomedea.com/english/
------------------------------------------------------------------------
Eric van der Vlist       http://xmlfr.org            http://dyomedea.com
(W3C) XML Schema ISBN:0-596-00252-1 http://oreilly.com/catalog/xmlschema
------------------------------------------------------------------------


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list