xsl-list
[Top] [All Lists]

Re: Fibonacci & XSL

2002-12-17 14:57:48

"Kasper Nielsen" <news(_at_)kav(_dot_)dk> wrote in message
news:004801c2a5be$1b61aab0$0c00a8c0(_at_)kasper(_dot_)(_dot_)(_dot_)
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.

regards
  Kasper

With FXSL the solution is really compact:

fibo.xsl:
--------
<xsl:stylesheet version="1.0"  
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
 xmlns:fiboNext="f:fiboNext"
 xmlns:initParam="f:initParam"
 xmlns:vendor="urn:schemas-microsoft-com:xslt"
 exclude-result-prefixes="xsl vendor fiboNext initParam">

 <xsl:import href="iter.xsl"/>

  <initParam:initParam>
     <n1>0</n1>
     <n2>1</n2>
  </initParam:initParam>
  
  <xsl:template name="Fibo">
  
    <xsl:param name="pN" select="3"/>
  
    <xsl:variable name="vLast2Elements">
      <xsl:call-template name="iter">
        <xsl:with-param name="pTimes" select="$pN"/>
        <xsl:with-param name="pFun" 
                        select="document('')/*/fiboNext:*[1]"/>
        <xsl:with-param name="pX" 
                        select="document('')/*/initParam:*[1]"/>
      </xsl:call-template>
    </xsl:variable>
    
    <xsl:value-of select="vendor:node-set($vLast2Elements)/n2"/>
  </xsl:template>
  
  <fiboNext:fiboNext/>
  <xsl:template match="fiboNext:*">
    <xsl:param name="arg1" select="/.."/>
    
      <n1><xsl:value-of select="$arg1/n2"/></n1>
      <n2><xsl:value-of select="$arg1/n1 + $arg1/n2"/></n2>

  </xsl:template>
    
</xsl:stylesheet>


Here is a test that uses the "fibo" template to print the first 100
Fibonacci numbers:

testFibo2.xsl:
-------------
<xsl:stylesheet version="1.0" 
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
 xmlns:vendor="urn:schemas-microsoft-com:xslt"
 xmlns:myFibo="f:myFibo" exclude-result-prefixes="myFibo vendor"


  <xsl:import href="fibo.xsl"/>
  <xsl:import href="iter.xsl"/>
  
  <xsl:output method="text"/>
  
  <xsl:template match="/">
    <xsl:variable name="vrtfResults">
      <xsl:call-template name="scanIter">
        <xsl:with-param name="arg1" select="100"/>
        <xsl:with-param name="arg2" 
                        select="document('')/*/myFibo:*[1]"/>
        <xsl:with-param name="arg3" select="'1,1'"/>
      </xsl:call-template>
    </xsl:variable>
    
    <xsl:for-each select="vendor:node-set($vrtfResults)/*">
      <xsl:value-of select="concat('F(', 
                                   substring-before(.,',') + 1, ') = ',

                                   substring-after(.,','), '&#xA;')"/>
    </xsl:for-each>
  </xsl:template>
  
  <myFibo:myFibo/>
  <xsl:template match="myFibo:*">
    <xsl:param name="arg1"/>
    
    <xsl:value-of select="substring-before($arg1, ',') 
                         + 1"/>,<xsl:text/>
      <xsl:call-template name="Fibo">
        <xsl:with-param name="pN" select="substring-before($arg1, ',')
                                          + 1"/>
      </xsl:call-template>
  </xsl:template>
</xsl:stylesheet>

when applied to any source xml(not-used), the result is:

F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55
F(11) = 89
F(12) = 144
F(13) = 233
F(14) = 377
F(15) = 610
F(16) = 987
F(17) = 1597
F(18) = 2584
F(19) = 4181
F(20) = 6765
F(21) = 10946
F(22) = 17711
F(23) = 28657
F(24) = 46368
F(25) = 75025
F(26) = 121393
F(27) = 196418
F(28) = 317811
F(29) = 514229
F(30) = 832040
F(31) = 1346269
F(32) = 2178309
F(33) = 3524578
F(34) = 5702887
F(35) = 9227465
F(36) = 14930352
F(37) = 24157817
F(38) = 39088169
F(39) = 63245986
F(40) = 102334155
F(41) = 165580141
F(42) = 267914296
F(43) = 433494437
F(44) = 701408733
F(45) = 1134903170
F(46) = 1836311903
F(47) = 2971215073
F(48) = 4807526976
F(49) = 7778742049
F(50) = 12586269025
F(51) = 20365011074
F(52) = 32951280099
F(53) = 53316291173
F(54) = 86267571272
F(55) = 139583862445
F(56) = 225851433717
F(57) = 365435296162
F(58) = 591286729879
F(59) = 956722026041
F(60) = 1548008755920
F(61) = 2504730781961
F(62) = 4052739537881
F(63) = 6557470319842
F(64) = 10610209857723
F(65) = 17167680177565
F(66) = 27777890035288
F(67) = 44945570212853
F(68) = 72723460248141
F(69) = 117669030460994
F(70) = 190392490709135
F(71) = 308061521170129
F(72) = 498454011879264
F(73) = 806515533049393
F(74) = 1304969544928657
F(75) = 2111485077978050
F(76) = 3416454622906707
F(77) = 5527939700884757
F(78) = 8944394323791464
F(79) = 14472334024676220
F(80) = 23416728348467684
F(81) = 20000000000000000
F(82) = 43416728348467680
F(83) = 63416728348467680
F(84) = 106833456696935360
F(85) = 170250185045403040
F(86) = 277083641742338400
F(87) = 447333826787741440
F(88) = 724417468530079900
F(89) = 1171751295317821400
F(90) = 1896168763847901200
F(91) = 3067920059165722600
F(92) = 4964088823013624000
F(93) = 8032008882179346000
F(94) = 12996097705192970000
F(95) = 21028106587372314000
F(96) = 34024204292565286000
F(97) = 55052310879937600000
F(98) = 89076515172502900000
F(99) = 144128826052440490000
F(100) = 233205341224943400000
F(101) = 377334167277383840000
F(102) = 610539508502327200000

The time for this transformation with MSXML4 on a 1.7GHz PC was 0.163
seconds.




=====
Cheers,

Dimitre Novatchev.
http://fxsl.sourceforge.net/ -- the home of FXSL

__________________________________________________
Do you Yahoo!?
Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
http://mailplus.yahoo.com

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



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