Re: [xsl] Fibonacci & XSL

[Dimitre Novatchev <dnovatchev@xxxxxxxxx>]

"Kasper Nielsen" <news@xxxxxx> wrote in message
news:004801c2a5be$1b61aab0$0c00a8c0@xxxxxxxxx
> 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