Re: [xsl] How smart are the XSLT processors? Are there any XSLT processors that convert tree-recursive functions into efficient iterative procedures?

[Dimitre Novatchev <dnovatchev@xxxxxxxxx>]

> but the main point is that it's really too hard to expect automatic
> conversions from O(n^2) algorithms to O(log n). My own attempt was the
> following which I'd hoped would beat dimitre's for speed, but it doesn't
> consistently, and his has the advantage of using exact integer arithmetic
(I
> didn't do the analysis to see at what the point the following will succumb
> to rounding error)


I compared the two implementations for F(3000) --> F(3001) in DC's
implementation.

Results:

FXSL:  33ms

DC:      10.5  seconds.     Also, there is loss of accuracy after the
35th digit.




--
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play



On Wed, Apr 28, 2010 at 3:42 PM, David Carlisle <davidc@xxxxxxxxx> wrote:
> On 28/04/2010 23:20, Florent Georges wrote:
>>
>> David Carlisle wrote:
>>
>> B  Hi,
>>
>>> You are making it pretty inefficient in any case by using
>>> value-of (or relying on your xslt engine to optimise this away)
>>> by using value-of you are asking for a document node with a
>>> text node child
>>
>> B  I didn't follow the whole discussion in details, so I probably
>> missed something, but why do you say "by using value-of you are
>> asking for a document node"? B I thought it just created one text
>> node.
>>
>> B  Regards,
>>
>
>
> er because it was the middle of the night and I'm so used to moaning at
> people for using xsl:variable with content rather than a select attribute
> that "document node with text node child" just slipped off my fingers,
> sorry. (If you look at the saxon list you'll see that I hadn't woken up
> enough this morning to notice my error:-)
>
> but the main point is that it's really too hard to expect automatic
> conversions from O(n^2) algorithms to O(log n). My own attempt was the
> following which I'd hoped would beat dimitre's for speed, but it doesn't
> consistently, and his has the advantage of using exact integer arithmetic
(I
> didn't do the analysis to see at what the point the following will succumb
> to rounding error)
>
> <xsl:function name="ex:pow" as="xs:decimal">
> B  <xsl:param name="a" as="xs:decimal"/>
> B  B <xsl:param name="n" as="xs:integer"/>
> B  B <xsl:choose>
> B  B  <xsl:when test="$n=0">
> B  B  B <xsl:sequence select="1"/>
> B  B  </xsl:when>
> B  B  <xsl:when test="$n=1">
> B  B  B <xsl:sequence select="$a"/>
> B  B  </xsl:when>
> B  B  <xsl:when test="$n mod 2 = 0">
> B  B  B <xsl:sequence select="for $z in ex:pow($a,$n idiv 2) return
$z*$z"/>
> B  B  </xsl:when>
> B  B  <xsl:otherwise>
> B  B  B <xsl:sequence select="for $z in ex:pow($a,$n idiv 2) return
$z*$z*$a"/>
> B  B  </xsl:otherwise>
> B  B </xsl:choose>
> </xsl:function>
>
> <xsl:variable name="phi"
> select="1.618033988749894848204586834365638117720"/>
> <xsl:variable name="r5"
> select="2.2360679774997896964091736687312762354406"/>
>
> <xsl:function B name="ex:fibclosed" as="xs:integer">
> B <xsl:param name="n" B as="xs:integer"/>
> B <xsl:sequence select="xs:integer(floor(ex:pow($phi,$n) div $r5 + 0.5))"/>
> </xsl:function>