xsl-list
[Top] [All Lists]

Re: Fibonacci & XSL

2002-12-17 04:47:57
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



<Prev in Thread] Current Thread [Next in Thread>