Re: Recursion performance (fibonacci numbers)

Thanks David. This is really fast.

Regards,
Mukul

On 1/16/06, David Carlisle <davidc@xxxxxxxxx> wrote:
>
> Dimitre asked a similar question a while back:
>
> http://www.xslt.com/html/xsl-list/2005-06/msg00844.html
>
> at least, the first part of his question involved calculating fibonacci
> numbers efficiently. I'm not sure he ever published the results that
> people sent him.
>
> For fibonacci, I suggested:
>
> <xsl:function name="x:fib" as="xs:integer">
>  <xsl:param name="n" as="xs:integer"/>
>  <xsl:choose>
>  <xsl:when test="$n=0">
>  <xsl:sequence select="1"/>
>  </xsl:when>
>  <xsl:when test="$n =1">
>  <xsl:sequence select="1"/>
>  </xsl:when>
>  <xsl:when test="$n mod 2 = 0">
>  <xsl:variable name="n2" select="$n idiv 2"/>
>  <xsl:variable name="fn" select="x:fib($n2)"/>
>  <xsl:variable name="fn-1" select="x:fib($n2 -1)"/>
>  <xsl:sequence select="$fn * $fn + $fn-1 * $fn-1"/>
>  </xsl:when>
>  <xsl:when test="$n mod 2 = 1">
>  <xsl:variable name="n2" select="($n - 1) idiv 2"/>
>  <xsl:variable name="fn" select="x:fib($n2)"/>
>  <xsl:variable name="fn-1" select="x:fib($n2 -1)"/>
>  <xsl:sequence select="(2 * $fn-1 + $fn) * $fn"/>
>  </xsl:when>
> </xsl:choose>
> </xsl:function>
>
> which should I think me considerably quicker than the function that you
> suggested for large numbers.
>
>
> David