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.
________________________________________________________________________