Recipe3.5.Implementing Common Math Functions | XSLT Cookbook: Solutions and Examples for XML and XSLT Developers, 2nd Edition

Recipe 3.5. Implementing Common Math Functions

Problem

You need to go beyond fifth-grade math even though XSLT 1.0 does not.

Solution

XSLT 1.0

XSLT 1.0 implementations are provided here for absolute value, square root, logarithms, power, and factorial.

Absolute value: ckbk:abs(x)

The obvious but long-winded way to determine the absolute value of a number is shown here:

<xsl:template name="ckbk:abs">      <xsl:param name="x"/>            <xsl:choose>           <xsl:when test="$x &lt; 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="ckbk:abs">      <xsl:param name="x"/>      <xsl:value-of select="(1 - 2 *($x &lt; 0)) * $x"/> </xsl:template>

I prefer the latter because it is concise. Alternatively, you can use an extension function (see Chapter 12).

Square root: ckbk:sqrt(x)

Nate Austin contributed a native XSLT sqrt to EXSLT that uses Newton's method:

<xsl:template name="ckbk: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="ckbk: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="ckbk: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 &lt; 100) +                        ($number >= 100 and $number &lt; 1000) * 10 +                        ($number >= 1000 and $number &lt; 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 numbers much greater than 10,000, you should keep the iterations at least 10 or add higher ranges to the try initialization.

Logarithms: ckbk:log10(number), ckbk:log(number), and ckbk:logN(x,base)

If your XSLT processor supports EXSLT's exsl:log( ) (natural log), then implementing a logarithm to any other base is easy. In pseudocode:

<!-- A fundamental rule of logarithms --> ckbk:logN(x,base) = ckbk:logN(x,diffBase) div ckbk:logN(base, diffBase)

Unfortunately, no XSLT processors are currently listed on EXSLT.org that implement exsl: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="ckbk: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 &lt;= 0"> <!-- Logarithms are undefined for 0                                and negative numbers. -->          <xsl:value-of select="'NaN'"/>        </xsl:when>        <xsl:when test="$number &lt; 1">  <!-- Fractional numbers have                                 negative logs -->          <xsl:call-template name="ckbk: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="ckbk: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="ckbk: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="ckbk:log">      <xsl:param name="number" select="1"/>          <xsl:variable name="log10-e" select="0.4342944819"/>      <xsl:variable name="log10">        <xsl:call-template name="ckbk: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="ckbk:log-b">      <xsl:param name="number" select="1"/>      <xsl:param name="base" select="2"/>          <xsl:variable name="log10-base">         <xsl:call-template name="ckbk:log10">          <xsl:with-param name="number" select="$base"/>        </xsl:call-template>      </xsl:variable>          <xsl:variable name="log10">        <xsl:call-template name="ckbk: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="ckbk: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"/>           <!-- successive 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 &lt; 10">          <xsl:call-template name="ckbk: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="ckbk: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>

Ckbk: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, ckbk: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:

^[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.

n: The whole part of the answer passed in by ckbk:log10. This parameter is not strictly necessary because it could have held onto it until ckbk:log10-util did its part. However, it eliminates the need to capture the result of ckbk:log10-util in a variable.
frac: The fractional part of the answer. This is what we are really after.
k: An iteration counter that is incremented on each recursive call. The recursion terminates when $k > $maxiter.
divisor: 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.
maxiter: 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.

Power: ckbk:power(base,power)

At this time, EXSLT.org does not list any implementations that support ckbk: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="ckbk: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="ckbk: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="ckbk: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="ckbk: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. In XPath 2.0, you would write this expression as if (power % 2) eq 1 then result * base else result. In XPath 1.0, you emulate it with this bit of XSLT hackery. The net result is that this template ends up computing b¹ * base + b² * base² + b³ * base⁴ * b⁴ * base⁸ ..., where bⁱ is either 0 or 1. It should be fairly easy to see that this sum can add up to base^power for an arbitrary integer power by setting the bⁱs to appropriate valueswhich is 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.^[3]

^[3] 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.

The power function shown earlier only computes powers for positive integral powers. However, as any high-school algebra student can tell you, x^y 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="ckbk: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 &lt; 0">          <xsl:variable name="result">          <xsl:call-template name="ckbk: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="ckbk: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="ckbk: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="ckbk: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="ckbk: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="ckbk: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 ckbk: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, ckbk:power, and a new template, ckbk:power-frac. Template ckbk:power-f takes advantage of the following two mathematical truths about powers:

base^-y = 1 / base^y, which allows you to handle negative powers easily.
base^{(power1+power2)} = base^power1 * base^power2, which lets you reuse the accuracy and efficiency ckbk:power( ) for the whole part of $power and use a good approximation for the fractional part.

The template ckbk:power-frac is a recursive implementation of the Maclaurin series for xy, as shown in Figure 3-1.

Figure 3-1. Maclaurin series for power

One way to implement the trigonometric functions is to create similar recursive implementations of their Maclaurin representation:

Factorial

Oddly, EXSLT has not defined a factorial function. Factorial is, of course, easy to implement:

<xsl:template name="ckbk:fact">      <xsl:param name="number" select="0"/>      <xsl:param name="result" select="1"/>      <xsl:choose>        <xsl:when test="$number &lt; 0 or floor($number) != $number">          <xsl:value-of select="'NaN'"/>        </xsl:when>        <xsl:when test="$number &lt; 2">          <xsl:value-of select="$result"/>        </xsl:when>        <xsl:otherwise>          <xsl:call-template name="ckbk: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="ckbk: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="ckbk: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>

XSLT 2.0

In 2.0, abs( ) is built-in. You can implement the others as functions for maximum convenience:

<!-- Power --> <xsl:function name="ckbk:power" as="xs:double">    <xsl:param name="base" as="xs:double"/>    <xsl:param name="exp" as="xs:integer"/>    <xsl:sequence          select="if ($exp lt 0) then ckbk:power(1.0 div $base, -$exp)                  else                  if ($exp eq 0)                  then 1e0                  else $base * ckbk:power($base, $exp - 1)"/> </xsl:function> <!-- Sqrt --> <xsl:function name="ckbk:sqrt" as="xs:double">    <xsl:param name="number" as="xs:double"/>    <xsl:variable name="try" select="if ($number lt 100.0) then 1.0                                     else if ($number gt 100.0 and $number lt                                              1000.0) then 10.0                                     else if ($number gt 1000.0 and $number lt                                              10000.0) then 31.0                                     else 100.00" as="xs:decimal"/>                                           <xsl:sequence select="if ($number ge 0) then ckbk:sqrt($number,$try,1,20)                           else 'NaN'"/> </xsl:function>    <xsl:function name="ckbk:sqrt" as="xs:double">     <xsl:param name="number" as="xs:double"/>     <xsl:param name="try" as="xs:double"/>     <xsl:param name="iter" as="xs:integer"/>     <xsl:param name="maxiter" as="xs:integer"/>          <xsl:variable name="result" select="$try * $try" as="xs:double"/>     <xsl:sequence select="if ($result eq $number or $iter gt $maxiter)                            then $try                            else ckbk:sqrt($number, ($try - (($result - $number)                                           div (2 * $try))), $iter + 1, $maxiter)"/> </xsl:function> <!-- Factorial --> <xsl:function name="ckbk:factorial" as="xs:decimal">     <xsl:param name="n" as="xs:integer"/>     <xsl:sequence select="if ($n eq 0) then 1 else $n * ckbk:factorial($n - 1)"/>  </xsl:function> <!-- Prod-range --> <xsl:function name="ckbk:prod-range" as="xs:decimal">     <xsl:param name="from" as="xs:integer"/>     <xsl:param name="to" as="xs:integer"/>     <xsl:sequence select="if ($from ge $to)                            then $from                            else $from * ckbk:prod-range($from + 1, $to)"/>  </xsl:function>          <!-- Log10 --> <xsl:function name="ckbk:log10" as="xs:double">   <xsl:param name="number" as="xs:double"/>   <xsl:sequence select="if ($number le 0) then 'NaN' else ckbk:log10($number,0)"/> </xsl:function>    <xsl:function name="ckbk:log10" as="xs:double">     <xsl:param name="number" as="xs:double"/>     <xsl:param name="n" as="xs:double"/>     <xsl:sequence select="if ($number le 1)                            then ckbk:log10($number * 10, $n - 1)                            else if($number gt 10)                            then ckbk:log10($number div 10, $n + 1)                           else if($number eq 10)                            then $n + 1                           else $n + ckbk:log10-util($number,0,0,2,38)"/>   </xsl:function>        <xsl:function name="ckbk:log10-util" as="xs:double">     <xsl:param name="number" as="xs:double"/>     <xsl:param name="frac" as="xs:double"/>     <xsl:param name="iter" as="xs:integer"/>     <xsl:param name="divisor" as="xs:double"/>     <xsl:param name="maxiter" as="xs:integer"/>          <xsl:variable name="x" select="$number * $number"/>     <xsl:sequence select="if ($iter ge $maxiter)                           then round-half-to-even($frac,10)                           else if ($x lt 10)                           then ckbk:log10-util($x,$frac,$iter + 1,                                                 $divisor * 2, $maxiter)                           else ckbk:log10-util($x div 10,                                                $frac + (1 div $divisor),                                                $iter + 1, $divisor * 2,                                                $maxiter)"/> </xsl:function>

Discussion

I would guess that at least 80% of your garden-variety XSLT applications never require math beyond the native capabilities of XPath. When the remaining 20 percent 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.

XSLT 2.0 comes to the rescue by giving you first-class functions. Thus, the 2.0 solutions are more concise and easier to use. However, parameters in xsl:function cannot have default values; thus, you will need to emulate this capability by overloading functions with different arities to emulate defaults. Unfortunately, 2.0 provides no way of encapsulating the private parameters that are used in recursive functions for bookkeeping purposes. When designing libraries of functions, you might want to consider placing the implementation functions (i.e., the one with the artificial bookkeeping parameters) in a different implementation namespace to hint that these are not for general use.

The second problem would be alleviated if a future XSLT version had private parameters that can be used only in a recursive call.