RE: [xsl] Recursion performance (fibonacci numbers)

Subject: RE: [xsl] Recursion performance (fibonacci numbers)
From: "Michael Kay" <mike@xxxxxxxxxxxx>
Date: Mon, 16 Jan 2006 18:59:46 -0000
saxon:memo-function="yes" works for me. I get

n      time
1000   90msecs
2000   610msecs

It's not linear at large values of "n" because BigInteger arithmetic takes
longer the larger "n" becomes; but the use of a memo function certainly
solves the XSLT-level problem.

Are you sure you used the right namespace http://saxon.sf.net/ ?

Michael Kay
http://www.saxonica.com/ 

> -----Original Message-----
> From: Mukul Gandhi [mailto:gandhi.mukul@xxxxxxxxx] 
> Sent: 16 January 2006 15:08
> To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
> Subject: [xsl] Recursion performance (fibonacci numbers)
> 
> Dear All,
>    I am running this XSLT stylesheet with Saxon b 8.6.1. This prints
> 1st n Fibonacci numbers, where n is supplied as a stylesheet
> parameter.
> 
> <?xml version="1.0" encoding="UTF-8"?>
> <xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
>                 xmlns:xs="http://www.w3.org/2001/XMLSchema";
>                 xmlns:myfunc="http://dummy";
>                 version="2.0">
> 
> <xsl:output method="text" />
> 
> <xsl:param name="n" />
> 
> <xsl:template match="/">
>   <xsl:for-each select="1 to $n">
>     <xsl:value-of select="myfunc:fibonacci(position())" 
> /><xsl:text> </xsl:text>
>   </xsl:for-each>
> </xsl:template>
> 
> <xsl:function name="myfunc:fibonacci" as="xs:integer">
>   <xsl:param name="n" as="xs:integer" />
> 
>   <xsl:sequence select="if (($n = 1) or ($n = 2))
>                         then
>                           1
>                         else
>                           (myfunc:fibonacci($n - 1) + 
> myfunc:fibonacci($n - 2))"
>                        />
> 
> </xsl:function>
> 
> </xsl:stylesheet>
> 
> The problem is, that it takes long time for large values of n. I
> observed the following timing
> 
> n=32 -> 35.5 secs
> n=33 -> 55.2 secs
> n=34 -> 1 min 27.3 secs
> n=35 -> 2 mins 20.1 secs
> 
> Is it possible I can improve the performance of this stylesheet for
> large values of n?
> 
> Regards,
> Mukul

Current Thread