Pure XSLT implementations are provided for absolute value, square root, logarithms, power, and factorial.
The obvious but long-winded way to determine the absolute value of a number is shown here:
<xsl:template name="math:abs"> <xsl:param name="x"/> <xsl:choose> <xsl:when test="$x < 0"> <xsl:value-of select="$x * -1"/> </xsl:when> <xsl:otherwise> <xsl:value-of select="$x"/> </xsl:otherwise> </xsl:choose> </xsl:template>
The short but obscure way relies on the fact that the
true
always converts to the number 1 and
false
to the number 0.
<xsl:template name="math:abs"> <xsl:param name="x"/> <xsl:value-of select="(1 - 2 *($x < 0)) * $x"/> </xsl:template>
I prefer the latter because it is concise. Alternatively, you can use an extension function (see Chapter 12).
Nate Austin contributed a native
XSLT sqrt
to EXSLT that uses
Newton’s method:
<xsl:template name="math:sqrt"> <!-- The number you want to find the square root of --> <xsl:param name="number" select="0"/> <!-- The current 'try'. This is used internally. --> <xsl:param name="try" select="1"/> <!-- The current iteration, checked against maxiter to limit loop count --> <xsl:param name="iter" select="1"/> <!-- Set this up to ensure against infinite loops --> <xsl:param name="maxiter" select="20"/> <!-- This template was written by Nate Austin using Sir Isaac Newton's method of finding roots --> <xsl:choose> <xsl:when test="$try * $try = $number or $iter > $maxiter"> <xsl:value-of select="$try"/> </xsl:when> <xsl:otherwise> <xsl:call-template name="math:sqrt"> <xsl:with-param name="number" select="$number"/> <xsl:with-param name="try" select="$try - (($try * $try - $number) div (2 * $try))"/> <xsl:with-param name="iter" select="$iter + 1"/> <xsl:with-param name="maxiter" select="$maxiter"/> </xsl:call-template> </xsl:otherwise> </xsl:choose> </xsl:template>
Changing the initial value of try
can improve
performance significantly:
<xsl:template name="math:sqrt"> <!-- The number you want to find the square root of --> <xsl:param name="number" select="0"/> <!-- The current 'try'. This is used internally. --> <xsl:param name="try" select="($number < 100) + ($number >= 100 and $number < 1000) * 10 + ($number >= 1000 and $number < 10000) * 31 + ($number >= 10000) * 100"/> <!-- rest of code the same --> </xsl:template>
This little trick (using Boolean-to-numeric conversion again) causes
try
to better approximate the square root on the
first get go. On a test that computes all roots from 1 to 10,000, I
achieved a 10% performance boost. More significantly, the change
reduced the average error from 1 ×
10-5 to 6 ×
10-13. This means you can reduce the
number of iterations to get even more performance at the same average
error rate. For example, I was able to reduce the iterations from 10
to 6 and achieve the same error rate of
10-5, but at a 50% performance increase
using the same test. If you need to compute square roots of number
much greater than 10,000, you should keep the iterations at least 10
or add higher ranges to the try
initialization.
If
your
XSLT processor supports
EXSLT’s math:log( )
(natural log), then implementing a
logarithm to any other base is easy. In pseudocode:
<!-- A fundemetal rule of logarithms --> math:logN(x,base) = math:log(x) div math:log(base)
Unfortunately, no XSLT processors are currently listed on EXSLT.org
that implement math:log
. Your next best bet is to
implement an extension function in terms of Java’s
java.lang.Math.log
class or
JavaScript’s Math.log
. Finally,
if you must avoid extensions, the following pure XSLT implementation
computes log10 to a good degree of accuracy at an acceptable speed
for most (sane) applications. Once you have
log10()
, then log()
follows
from the rule of logarithms:
<xsl:template name="math:log10"> <xsl:param name="number" select="1"/> <xsl:param name="n" select="0"/> <!-- book keeping for whole part of result --> <xsl:choose> <xsl:when test="$number <= 0"> <!-- Logarithms are undefined for 0 and negative numbers. --> <xsl:value-of select="'NaN'"/> </xsl:when> <xsl:when test="$number < 1"> <!-- Fractional numbers have negative logs --> <xsl:call-template name="math:log10"> <xsl:with-param name="number" select="$number * 10"/> <xsl:with-param name="n" select="$n - 1"/> </xsl:call-template> </xsl:when> <xsl:when test="$number > 10"> <!-- Numbers greater than 10 have logs greater than 1 --> <xsl:call-template name="math:log10"> <xsl:with-param name="number" select="$number div 10"/> <xsl:with-param name="n" select="$n + 1"/> </xsl:call-template> </xsl:when> <xsl:when test="$number = 10"> <xsl:value-of select="$n + 1"/> </xsl:when> <xsl:otherwise> <!-- We only need to know how to compute for numbers in range [1,10) --> <xsl:call-template name="math:log10-util"> <xsl:with-param name="number" select="$number"/> <xsl:with-param name="n" select="$n"/> </xsl:call-template> </xsl:otherwise> </xsl:choose> </xsl:template> <!-- Computes log (natural) of number--> <xsl:template name="math:log"> <xsl:param name="number" select="1"/> <xsl:variable name="log10-e" select="0.4342944819"/> <xsl:variable name="log10"> <xsl:call-template name="math:log10"> <xsl:with-param name="number" select="$number"/> </xsl:call-template> </xsl:variable> <xsl:value-of select="$log10 div $log10-e"/> </xsl:template> <!-- Computes log to base b of number--> <xsl:template name="math:log-b"> <xsl:param name="number" select="1"/> <xsl:param name="base" select="2"/> <xsl:variable name="log10-base"> <xsl:call-template name="math:log10"> <xsl:with-param name="number" select="$base"/> </xsl:call-template> </xsl:variable> <xsl:variable name="log10"> <xsl:call-template name="math:log10"> <xsl:with-param name="number" select="$number"/> </xsl:call-template> </xsl:variable> <xsl:value-of select="$log10 div $log10-base"/> </xsl:template> <!-- Computes log10 of numbers in the range [1,10) and returns the result + n--> <xsl:template name="math:log10-util"> <xsl:param name="number"/> <xsl:param name="n"/> <xsl:param name="frac" select="0"/> <!-- book keeping variable for fractional part --> <xsl:param name="k" select="0"/> <!-- iteration counter --> <xsl:param name="divisor" select="2"/> <!-- sucessive powers of 2 used to build up frac --> <xsl:param name="maxiter" select="38"/> <!-- Number of iterations. 38 is more than sufficient to get at least 10 dec place prec --> <xsl:variable name="x" select="$number * $number"/> <xsl:choose> <xsl:when test="$k >= $maxiter"> <!-- Round to 10 decimal places --> <xsl:value-of select="$n + round($frac * 10000000000) div 10000000000"/> </xsl:when> <xsl:when test="$x < 10"> <xsl:call-template name="math:log10-util"> <xsl:with-param name="number" select="$x"/> <xsl:with-param name="n" select="$n"/> <xsl:with-param name="k" select="$k + 1"/> <xsl:with-param name="divisor" select="$divisor * 2"/> <xsl:with-param name="frac" select="$frac"/> <xsl:with-param name="maxiter" select="$maxiter"/> </xsl:call-template> </xsl:when> <xsl:otherwise> <xsl:call-template name="math:log10-util"> <xsl:with-param name="number" select="$x div 10"/> <xsl:with-param name="n" select="$n"/> <xsl:with-param name="k" select="$k + 1"/> <xsl:with-param name="divisor" select="$divisor * 2"/> <xsl:with-param name="frac" select="$frac + (1 div $divisor)"/> <xsl:with-param name="maxiter" select="$maxiter"/> </xsl:call-template> </xsl:otherwise> </xsl:choose> </xsl:template>
Math:log10
’s main purpose is to
reduce the problem of computing log10(x)
to the
simpler problem of computing log10(x
:
1
<=
x
<
10)
.
This is done by observing that log10(x
:
x
>
10)
=
log10(
x
div
10)
+
1
and
log10(x
:
x
<
1)
=
log10(
x
*
10)
-
1
.
Error checking is also performed because logarithms are not defined
for zero or negative numbers.
The utility template, math:log10-util
,
does the hard part; it is a
tail-recursive implementation of an iterative technique found in
Knuth.[2]
To keep the implementation tail recursive and greatly simplify the
implementation, several bookkeeping parameters are defined:
The whole part of the answer passed in by
math:log10
. This parameter is not strictly
necessary because it could have held onto it until
math:log10-util
did its part. However, it
eliminates the need to capture the result of
math:log10-util
in a variable.
The fractional part of the answer. This is what we are really after.
An iteration counter that is incremented on each recursive call. The
recursion terminates when $k > $maxiter
.
A number that is set to the next higher power of 2 on each recursive
call (e.g., 2,4,8,16,...). The value 1 div $divisor
is added to frac
as you
approximate the logarithm.
The number of iterations used to compute frac
. The
higher maxiter
is, the greater the precision of
the result (up to the limits of IEEE floating point). A parameter
need not be used, but it opens the possibility of extending
log10
to allow the caller to determine the
required number of iterations and hence tweak speed versus accuracy.
At this
time, EXSLT.org does not list any implementations that support
math:power( )
. However, as it is defined by EXSLT,
power( )
is easy to implement in pure XSLT.
Jeni Tennison provides the following implementation:
<xsl:template name="math:power"> <xsl:param name="base"/> <xsl:param name="power"/> <xsl:choose> <xsl:when test="$power = 0"> <xsl:value-of select="1"/> </xsl:when> <xsl:otherwise> <xsl:variable name="temp"> <xsl:call-template name="math:power"> <xsl:with-param name="base" select="$base"/> <xsl:with-param name="power" select="$power - 1"/> </xsl:call-template> </xsl:variable> <xsl:value-of select="$base * $temp"/> </xsl:otherwise> </xsl:choose> </xsl:template>
For most applications, this code will do just fine; however, it is
neither tail recursive nor the most algorithmically efficient
implementation. The following implementation is tail recursive and
reduces the number of multiplications from
O($power)
to O(log2($power))
.
It also adds error handling, which prevents an infinite recursion if
$power
is NaN:
<xsl:template name="math:power"> <xsl:param name="base"/> <xsl:param name="power"/> <xsl:param name="result" select="1"/> <xsl:choose> <xsl:when test="number($base) != $base or number($power) != $power"> <xsl:value-of select="'NaN'"/> </xsl:when> <xsl:when test="$power = 0"> <xsl:value-of select="$result"/> </xsl:when> <xsl:otherwise> <xsl:call-template name="math:power"> <xsl:with-param name="base" select="$base * $base"/> <xsl:with-param name="power" select="floor($power div 2)"/> <xsl:with-param name="result" select="$result * $base * ($power mod 2) + $result * not($power mod 2)"/> </xsl:call-template> </xsl:otherwise> </xsl:choose> </xsl:template>
This section introduces a bookkeeping parameter,
$result
, to build up the final answer. It allows
you to make the function tail recursive. On each recursive step,
square the base and halve the power. Because you use floor( )
, $result
will reach 0 in
ceiling(log2($power))
recursions. This accounts
for the better performance. The tricky part is the computation of
$result
at each step.
Let’s analyze this expression by looking at each
side of the addition. The expression $result * $base * ($power mod 2)
will be equal to $result * $base
when $power
is odd and 0
otherwise. Conversely, $result * not($power mod 2)
will be equal to 0 when $power
is odd and
$result
otherwise. If you were in C or Java you
would write this expression as (power % 2) ? result * base : result
. XPath 1.0 does not have a ?
:
operator, so you emulate it with this bit of XSLT hackery.[3] The net result is that this
template ends up computing b1 * base +
b2 * base2 +
b3 * base4 *
b4 * base8 ...,
where bi is either 0 or 1. It should be
fairly easy to see that this sum can add up to
basepower for an arbitrary integer power
by setting the bis to appropriate
values—whichis just what the expression
$power
mod
2
determines. If this concept is still unclear, then work out a few
cases by hand to convince yourself that it works.[4]
The power function shown earlier only computes powers for positive
integral powers. However, as any high-school algebra student can tell
you, xy is a real number for all real x
and y, not just positive integers. It would be nice to have a
generalized version of power( )
lying around in
case you need it, so here it is. Not to be confused with
power( )
, this template is called
power-f( )
, where the f
stands
for floating point. If you prefer to have the most general version
called power( )
, then go right ahead and rename it
in your own code. However, having the restricted version available as
a separate function is still useful:
<xsl:template name="math:power-f"> <xsl:param name="base"/> <xsl:param name="power"/> <xsl:choose> <xsl:when test="number($base) != $base or number($power) != $power"> <xsl:value-of select="'NaN'"/> </xsl:when> <xsl:when test="$power < 0"> <xsl:variable name="result"> <xsl:call-template name="math:power-f"> <xsl:with-param name="base" select="$base"/> <xsl:with-param name="power" select="-1 * $power"/> </xsl:call-template> </xsl:variable> <xsl:value-of select="1 div $result"/> </xsl:when> <xsl:otherwise> <xsl:variable name="powerN" select="floor($power)"/> <xsl:variable name="resultN"> <xsl:call-template name="math:power"> <xsl:with-param name="base" select="$base"/> <xsl:with-param name="power" select="$powerN"/> </xsl:call-template> </xsl:variable> <xsl:choose> <xsl:when test="$power - $powerN"> <xsl:variable name="resultF"> <xsl:call-template name="math:power-frac"> <xsl:with-param name="base" select="$base"/> <xsl:with-param name="power" select="$power - $powerN"/> </xsl:call-template> </xsl:variable> <xsl:value-of select="$resultN * $resultF"/> </xsl:when> <xsl:otherwise> <xsl:value-of select="$resultN"/> </xsl:otherwise> </xsl:choose> </xsl:otherwise> </xsl:choose> </xsl:template> <xsl:template name="math:power-frac"> <xsl:param name="base"/> <xsl:param name="power"/> <xsl:param name="n" select="1"/> <xsl:param name="ln_base"> <xsl:call-template name="math:log"> <xsl:with-param name="number" select="$base"/> </xsl:call-template> </xsl:param> <xsl:param name="ln_base_n" select="$ln_base"/> <xsl:param name="power_n" select="$power"/> <xsl:param name="n_fact" select="$n"/> <xsl:param name="result" select="1"/> <xsl:choose> <xsl:when test="20 >= $n"> <xsl:call-template name="math:power-frac"> <xsl:with-param name="base" select="$base"/> <xsl:with-param name="power" select="$power"/> <xsl:with-param name="n" select="$n + 1"/> <xsl:with-param name="ln_base" select="$ln_base "/> <xsl:with-param name="ln_base_n" select="$ln_base_n * $ln_base"/> <xsl:with-param name="power_n" select="$power_n * $power"/> <xsl:with-param name="n_fact" select="$n_fact * ($n+1)"/> <xsl:with-param name="result" select="$result + ($power_n * $ln_base_n) div $n_fact"/> </xsl:call-template> </xsl:when> <xsl:otherwise> <xsl:value-of select="round($result * 1000000000) div 1000000000"/> </xsl:otherwise> </xsl:choose> </xsl:template>
The math:power-f
template does not do the meat of
the calculation. Instead, it checks for errors and then computes the
result in terms of the existing template,
math:power
, and a new template,
math:power-frac
. Template
math:power-f
takes advantage of the following two
mathematical truths about powers:
base-y = 1 / basey, which allows you to handle negative powers easily.
base(power1+power2) =
basepower1 *
basepower2, which lets you reuse the
accuracy and efficiency math:power( )
for the
whole part of $power
and use a good approximation
for the fractional part.
The template math:power-frac
is
a recursive implementation of the Maclaurin series for basepower, as shown in
Figure 2-1.
One way to implement the trigonometric functions is to create similar recursive implementations of their Maclaurin representation.
Oddly, EXSLT has not defined a factorial function. Factorial is, of course, easy to implement:
<xsl:template name="math:fact"> <xsl:param name="number" select="0"/> <xsl:param name="result" select="1"/> <xsl:choose> <xsl:when test="$number < 0 or floor($number) != $number"> <xsl:value-of select="'NaN'"/> </xsl:when> <xsl:when test="$number < 2"> <xsl:value-of select="$result"/> </xsl:when> <xsl:otherwise> <xsl:call-template name="math:fact"> <xsl:with-param name="number" select="$number - 1"/> <xsl:with-param name="result" select="$number * $result"/> </xsl:call-template> </xsl:otherwise> </xsl:choose> </xsl:template>
A useful generalization of factorial is a function that computes the product of all numbers in a range:
<xsl:template name="math:prod-range"> <xsl:param name="start" select="1"/> <xsl:param name="end" select="1"/> <xsl:param name="result" select="1"/> <xsl:choose> <xsl:when test="$start > $end"> <xsl:value-of select="$result"/> </xsl:when> <xsl:otherwise> <xsl:call-template name="math:prod-range"> <xsl:with-param name="start" select="$start + 1"/> <xsl:with-param name="end" select="$end"/> <xsl:with-param name="result" select="$start * $result"/> </xsl:call-template> </xsl:otherwise> </xsl:choose> </xsl:template>
I would guess that at least 80% of your garden-variety XSLT applications never require math beyond the native capabilities of XPath 1.0. When the remaining 20% need to go beyond XPath 1.0, chances are high that one or more of the previous functions are necessary.
The biggest drawback of a pure XSLT 1.0 implementation is that the templates cannot be invoked as first-class functions from XPath expression. This makes doing math awkward and slightly more inefficient because you need to create artificial variables to capture the results of template calls as result-tree fragments. Internally, the XSLT processor has to convert these fragments back to numbers when you use them in subsequent calculations.
Another problem with XSLT implementations is that the public
interface of these templates is polluted with bookkeeping parameters
that obscure the nature of the function. The bookkeeping parameters
are often necessary to make the implementation tail recursive and
prevent unnecessary work. For example, the implementation of
power-frac
needs to compute the log of the base
and have it available at all times. If ln_base
were not a parameter, then log
would be invoked on
every recursive call, resulting in unacceptable performance.
EXSLT defines the extension elements func:function
and
func:result
, which solve the first problem by
allowing XSLT programmers to define first-class functions. If your
XSLT 1.0 processor implements these extensions, you should consider
using them if absolute W3C standard conformance is not a priority.
The XSLT 2.0 working draft proposes xsl:function
and xsl:result
elements that are very similar to
EXSLT’s. Yeah!
The second problem would be alleviated if a future XSLT version had private parameters that can be used only in a recursive call.
Example 2-8 shows how power-frac
might look if function
,
if-else
, and private
parameters
became available.
Example 2-8. Nonstandard XSLT 1.0
<xsl:function name="math:power-frac"> <xsl:param name="base"/> <xsl:param name="power"/> <xsl:private name="n" select="1"/> <xsl:private name="ln_base" select="math:log($base)"/> <xsl:private name="ln_base_n" select="$ln_base"/> <xsl:private name="power_n" select="$power"/> <xsl:private name="n_fact" select="$n"/> <xsl:private name="result" select="1"/> <xsl:result select="if (20 >= $n) then math:power-frac($base,$power,$n + 1,ln_base, $ln_base_n * $ln_base,$power_n * $power, $n_fact * ($n+1), $result + $power_n * $ln_base_n) div $n_fact) else round($result * 1000000000) div 1000000000"/> </xsl:function>
[2] The math is beyond the scope of this book. See Knuth, D.E. The Art of Computer Programming, Vol. 1, p. 24 (Addison Wesley, 1973) for details.
[3] XPath 2.0 will most likely have an equivalent construct.
According to the 2.0 working draft, this example would look like
if ($power mod 2) then $result * $base else $result
.
[4] Despite the fact that formal proofs of algorithmic correctness are important, I find them tedious and boring, so you will not see any in this book. I prefer intuition and testing my code. Chapter 12 shows how the homoiconic nature (in which the program form is the same as the data form) of XSLT greatly simplifies testing. A real computer scientist would prove everything by induction and not need to test.