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

Subject: Re: [xsl] How smart are the XSLT processors? Are there any XSLT processors that convert tree-recursive functions into efficient iterative procedures?
From: David Carlisle <davidc@xxxxxxxxx>
Date: Thu, 29 Apr 2010 09:38:03 +0100
On 29/04/2010 03:19, Dimitre Novatchev wrote:
FXSL: 33ms

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



ah, interesting, I didn't go that far up and saw essentially the same times within experimental error (and exact results). Of course the algorithm I used for power (halving and multiplying: is more or less the same one you used for fib so you'd expect the same number of calculations more or less, but presumably after a while the xs:integer calculations in your version are intrinsically faster then the higher-than-double precision xs:decimal in mine.


the loss of accuracy is of course to be expected, I could have entered phi and root 5 more accurately but I haven't checked recently how many digits of accuracy saxon supports in any case.

The algorithm I used would make more sense (and probably be a lot quicker) if power was a function in the language (and could be directly or closely supported by the hardware arithmetic) but that would be unlikely to be so useful for very high bignum support where a high level optimised library is always(?) going to be needed.

So for the question in the subject line, some compilers may spot some simple non-tail recursive idioms and rewrite but they are unlikely to
(but could; as it only uses high school arithmetic) rewrite linear recurrence relations to non-linear but much more efficient relations (as for Dimitre's version) or closed form solutions (as mine).
I intened to write mine not as a speed race against fxsl but to show a closed form solution but that point was a bit lost as I had to implement power by a recursive algorithm in any case.


For everyone else, the moral is use fxsl more often:-)

David


________________________________________________________________________ The Numerical Algorithms Group Ltd is a company registered in England and Wales with company number 1249803. The registered office is: Wilkinson House, Jordan Hill Road, Oxford OX2 8DR, United Kingdom.

This e-mail has been scanned for all viruses by Star. The service is
powered by MessageLabs. ________________________________________________________________________


Current Thread