xsl-list
[Top] [All Lists]

## Re: Recursion performance (fibonacci numbers)

2006-01-16 12:51:15
```On 1/17/06, David Carlisle <davidc(_at_)nag(_dot_)co(_dot_)uk> 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
anti-virus service working around the clock, around the globe, visit:
http://www.star.net.uk
________________________________________________________________________

--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--

```
```

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

--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--

```
 Current Thread Recursion performance (fibonacci numbers), Mukul Gandhi RE: Recursion performance (fibonacci numbers), Michael Kay Re: Recursion performance (fibonacci numbers), David Carlisle Re: Recursion performance (fibonacci numbers), Mukul Gandhi Re: Recursion performance (fibonacci numbers), Dimitre Novatchev <= Message not available Re: Recursion performance (fibonacci numbers), Mukul Gandhi RE: Recursion performance (fibonacci numbers), Michael Kay Message not available Re: Recursion performance (fibonacci numbers), Mukul Gandhi Re: Recursion performance (fibonacci numbers), omprakash . v Re: Recursion performance (fibonacci numbers), jeb501 Re: Recursion performance (fibonacci numbers), Mukul Gandhi RE: Recursion performance (fibonacci numbers), Michael Kay Message not availableRe: Recursion performance (fibonacci numbers), andrew welch Re: Recursion performance (fibonacci numbers), andrew welch