Re: [xsl] Recursion performance (fibonacci numbers)

[Dimitre Novatchev <dnovatchev@xxxxxxxxx>]

On 1/17/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


Yes. I owe an apology to David and to everyone for not posting the
responses to the XSLT puzzle.

I planned to do this before New Year, but just then someone I loved
died and I was overseas for three weeks. I will summarize David's and
mine solution most probably this weekend.

Dimitre


>
> at least, the first part of his question involved calculating fibonacci
> numbers efficiently.

Yes, this algorithm has a time complexity of O(log2 N).

>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
>
>
> ________________________________________________________________________
> This e-mail has been scanned for all viruses by Star. The
> service is powered by MessageLabs. For more information on a proactive
> anti-virus service working around the clock, around the globe, visit:
> http://www.star.net.uk
> ________________________________________________________________________
>
>



--
Cheers,
Dimitre Novatchev
---------------------------------------
To avoid situations in which you might make mistakes may be the
biggest mistake of all.