Subject: Re: [xsl] Recursion performance (fibonacci numbers) From: Dimitre Novatchev <dnovatchev@xxxxxxxxx> Date: Tue, 17 Jan 2006 06:51:15 +1100 |
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.
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Recursion performance (fi, Mukul Gandhi | Thread | Re: [xsl] Recursion performance (fi, Mukul Gandhi |
RE: [xsl] Recursion performance (fi, Michael Kay | Date | [xsl] Xprss - web app using client-, pramod |
Month |