xsl-list
[Top] [All Lists]

Re: [xsl] Math "functions" for XSLT 1.0

2010-03-03 21:08:01
On Wed, Mar 3, 2010 at 11:38 AM, Dimitre Novatchev 
<dnovatchev(_at_)gmail(_dot_)com> wrote:
Alain,

By the way, almost 30 years ago, I already knew that calculators never use
Taylor series (CORDIC algorithms were written in 1959)... Even if they are
mathematically correct, they require too many iterations for small systems
and managing huge numbers such as factorials is not always possible. I'm
interested in XSLT at browser side and speed is important.


I wonder why you think CORDIC algorithms are faster. Here
(http://en.wikipedia.org/wiki/CORDIC#Application) is a statement
comparing the speeds:

"On the other hand, when a hardware multiplier is available (e.g., in
a DSP microprocessor), table-lookup methods and power series are
generally faster than CORDIC".


To substantiate this statement, I ran a quick and dirty test for sin()
on 201 values in the interval [-1, +1], with x(i) = x(i-1) +0.01.


Here are the results (using Msxml4):

CORDIC (Couthures): 93.810ms

Taylor series(FXSL) :   9.664 ms


So, on this test the particular (FXSL) Taylor series - based
implementation of sin() was more than 10 times faster than the
provided particular (Couthures) implementation of CORDIC.

The Win7 computer I ran this test on has CPU speed of 2.67GHz.
Results may vary on different platforms and using different XSLT
processors, however the ration of 10:1 should remain relatively the
same.


Initially I planned similar tests on all provided functions, but this
first result is significant enough to conclude that testing the other
functions would most probably end up with very similar results.

I feel somewhat disappointed, because the ellegancy and the math
laying behind CORDIC seemed very attractive.

So, for anyone who is planning an application for an environment with
limited computational resources, these results clearly show that the
Taylor series function implementation are approximately an order of
magnitude faster than a CORDIC implementation. Good result as it
leaves no ground for hesitation.



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


P.S.  The code and data

Couthures2.xsl
============
<?xml version="1.0" encoding="ISO-8859-1"?>
<xsl:stylesheet
 xmlns=""
 xmlns:xhtml="http://www.w3.org/1999/xhtml";
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
 version="1.0" exclude-result-prefixes="xhtml">
        <xsl:template match="x">
    <xsl:call-template name="fsin"/>
        </xsl:template>
        <xsl:template match="sqrt">
                <p>sqrt(<xsl:value-of select="."/>) = <xsl:call-template
name="sqrt"><xsl:with-param name="x"
select="."/></xsl:call-template></p>
        </xsl:template>
        <xsl:template match="cos">
                <p>cos(<xsl:value-of select="."/>) = <xsl:call-template
name="cos"><xsl:with-param name="x"
select="."/></xsl:call-template></p>
        </xsl:template>
        <xsl:template match="sin" name="fsin">
                <!--<p>sin(<xsl:value-of select="."/>) = --><xsl:call-template
name="sin"><xsl:with-param name="x"
select="."/></xsl:call-template><!--</p>-->
        </xsl:template>
        <xsl:template match="log">
                <p>log(<xsl:value-of select="."/>) = <xsl:call-template
name="log"><xsl:with-param name="x"
select="."/></xsl:call-template></p>
        </xsl:template>
        <xsl:variable name="eps">0.0000000000000001</xsl:variable>
        <xsl:variable name="pi">3.141592653589793</xsl:variable>
        <xsl:template name="atan">
                <xsl:param name="x"/>
                <xsl:param name="k" select="3"/>
                <xsl:param name="y" select="$x * $x"/>
                <xsl:param name="i" select="-1"/>
                <xsl:param name="u" select="$x * $y"/>
                <xsl:choose>
                        <xsl:when test="$u &gt; $eps">
                                <xsl:call-template name="atan">
                                        <xsl:with-param name="x" select="$x + 
$u * $i div $k"/>
                                        <xsl:with-param name="k" select="$k + 
2"/>
                                        <xsl:with-param name="y" select="$y"/>
                                        <xsl:with-param name="u" select="$u * 
$y"/>
                                        <xsl:with-param name="i" select="-$i"/>
                                </xsl:call-template>
                        </xsl:when>
                        <xsl:otherwise>
                                <xsl:value-of select="$x"/>
                        </xsl:otherwise>
                </xsl:choose>
        </xsl:template>
        <xsl:template name="sqrt">
                <xsl:param name="x"/>
                <xsl:param name="u1" select="$x"/>
                <xsl:param name="u2" select="1"/>
                <xsl:choose>
                        <xsl:when test="$x &lt; 0">NaN</xsl:when>
                        <xsl:when test="(($u2 - $u1)*(number($u2 &gt; $u1) * 2 
- 1)) &gt; $eps">
                                <xsl:call-template name="sqrt">
                                        <xsl:with-param name="x" select="$x"/>
                                        <xsl:with-param name="u1" select="$u2"/>
                                        <xsl:with-param name="u2" select="($u2 
+ $x div $u2) div 2"/>
                                </xsl:call-template>
                        </xsl:when>
                        <xsl:otherwise>
                                <xsl:value-of select="$u2"/>
                        </xsl:otherwise>
                </xsl:choose>
        </xsl:template>
        <xsl:template name="k">
                <xsl:param name="x"/>
                <xsl:param name="k"/>
                <xsl:choose>
                        <xsl:when test="$k &gt;= $x">
                                <xsl:call-template name="k">
                                        <xsl:with-param name="x" select="$x"/>
                                        <xsl:with-param name="k" select="$k div 
2"/>
                                </xsl:call-template>
                        </xsl:when>
                        <xsl:otherwise>
                                <xsl:value-of select="$k"/>
                        </xsl:otherwise>
                </xsl:choose>
        </xsl:template>
        <xsl:template name="sincostan">
                <xsl:param name="res"/>
                <xsl:param name="x"/>
                <xsl:param name="k" select="0.5"/>
                <xsl:param name="xx" select="1"/>
                <xsl:param name="yy" select="0"/>
                <xsl:choose>
                        <xsl:when test="$x &gt; $eps">
                                <xsl:variable name="k1">
                                        <xsl:call-template name="k">
                                                <xsl:with-param name="x" 
select="$x"/>
                                                <xsl:with-param name="k" 
select="$k"/>
                                        </xsl:call-template>
                                </xsl:variable>
                                <xsl:variable name="x1"><xsl:call-template
name="atan"><xsl:with-param name="x"
select="$k1"/></xsl:call-template></xsl:variable>
                                <xsl:variable name="q"><xsl:call-template
name="sqrt"><xsl:with-param name="x" select="1 + $k1 *
$k1"/></xsl:call-template></xsl:variable>
                                <xsl:call-template name="sincostan">
                                        <xsl:with-param name="res" 
select="$res"/>
                                        <xsl:with-param name="x" select="$x - 
$x1"/>
                                        <xsl:with-param name="k" select="$k1"/>
                                        <xsl:with-param name="xx" select="($xx 
- $yy * $k1) div $q"/>
                                        <xsl:with-param name="yy" select="($xx 
* $k1 + $yy) div $q"/>
                                </xsl:call-template>
                        </xsl:when>
                        <xsl:otherwise>
                                <xsl:choose>
                                        <xsl:when test="$res = 
'sin'"><xsl:value-of select="$yy"/></xsl:when>
                                        <xsl:when test="$res = 
'cos'"><xsl:value-of select="$xx"/></xsl:when>
                                        <xsl:when test="$res = 
'tan'"><xsl:value-of select="$yy div
$xx"/></xsl:when>
                                </xsl:choose>
                        </xsl:otherwise>
                </xsl:choose>
        </xsl:template>
        <xsl:template name="cos">
                <xsl:param name="x"/>
                <xsl:variable name="x0" select="($x div $pi div 2 - floor($x 
div $pi
div 2)) * $pi * 2"/>
                <xsl:variable name="x1">
                        <xsl:choose>
                                <xsl:when test="$x0 = 0 or $x0 = 
$pi">0</xsl:when>
                                <xsl:when test="$x0 &gt; $pi div 2 and $x0 &lt; 
$pi"><xsl:value-of
select="$x0 - $pi"/></xsl:when>
                                <xsl:when test="$x0 &gt; $pi and $x0 &lt; $pi * 
1.5"><xsl:value-of
select="$pi - $x0"/></xsl:when>
                                <xsl:when test="$x0 &gt; $pi"><xsl:value-of 
select="$pi * 2 -
$x0"/></xsl:when>
                                <xsl:otherwise><xsl:value-of 
select="$x0"/></xsl:otherwise>
                        </xsl:choose>
                </xsl:variable>
                <xsl:choose>
                        <xsl:when test="$x1 = 0">1</xsl:when>
                        <xsl:when test="$x1 = $pi div 2">0</xsl:when>
                        <xsl:when test="$x1 = $pi">-1</xsl:when>
                        <xsl:when test="$x1 = $pi * 1.5">0</xsl:when>
                        <xsl:when test="$x1 &gt; 0">
                                <xsl:call-template name="sincostan">
                                        <xsl:with-param 
name="res">cos</xsl:with-param>
                                        <xsl:with-param name="x" select="$x1"/>
                                </xsl:call-template>
                        </xsl:when>
                        <xsl:otherwise>
                                <xsl:text>-</xsl:text>
                                <xsl:call-template name="sincostan">
                                        <xsl:with-param 
name="res">cos</xsl:with-param>
                                        <xsl:with-param name="x" select="-$x1"/>
                                </xsl:call-template>
                        </xsl:otherwise>
                </xsl:choose>
        </xsl:template>
        <xsl:template name="sin">
                <xsl:param name="x"/>
                <xsl:variable name="x0" select="($x div $pi div 2 - floor($x 
div $pi
div 2)) * $pi * 2"/>
                <xsl:variable name="x1">
                        <xsl:choose>
                                <xsl:when test="$x0 = 0 or $x0 = 
$pi">0</xsl:when>
                                <xsl:when test="$x0 &gt; $pi div 2 and $x0 &lt; 
$pi *
1.5"><xsl:value-of select="$pi - $x0"/></xsl:when>
                                <xsl:when test="$x0 &gt; $pi * 
1.5"><xsl:value-of select="$x0 -
$pi * 2"/></xsl:when>
                                <xsl:otherwise><xsl:value-of 
select="$x0"/></xsl:otherwise>
                        </xsl:choose>
                </xsl:variable>
                <xsl:choose>
                        <xsl:when test="$x1 = 0">0</xsl:when>
                        <xsl:when test="$x1 = $pi div 2">1</xsl:when>
                        <xsl:when test="$x1 = $pi">0</xsl:when>
                        <xsl:when test="$x1 = $pi * 1.5">-1</xsl:when>
                        <xsl:when test="$x1 &gt; 0">
                                <xsl:call-template name="sincostan">
                                        <xsl:with-param 
name="res">sin</xsl:with-param>
                                        <xsl:with-param name="x" select="$x1"/>
                                </xsl:call-template>
                        </xsl:when>
                        <xsl:otherwise>
                                <xsl:text>-</xsl:text>
                                <xsl:call-template name="sincostan">
                                        <xsl:with-param 
name="res">sin</xsl:with-param>
                                        <xsl:with-param name="x" select="-$x1"/>
                                </xsl:call-template>
                        </xsl:otherwise>
                </xsl:choose>
        </xsl:template>
        <xsl:template name="log">
                <xsl:param name="x"/>
                <xsl:choose>
                        <xsl:when test="$x &lt;=0">NaN</xsl:when>
                        <xsl:when test="$x = 1">0</xsl:when>
                        <xsl:otherwise>
                                <xsl:variable name="x0">
                                        <xsl:choose>
                                                <xsl:when test="$x &lt; 
1"><xsl:value-of select="1 div $x"/></xsl:when>
                                                <xsl:otherwise><xsl:value-of 
select="$x"/></xsl:otherwise>
                                        </xsl:choose>
                                </xsl:variable>
                                <xsl:variable name="x1">
                                        <xsl:call-template name="log_">
                                                <xsl:with-param name="x"
select="concat(substring(string($x0),1,1),'.',translate(substring(string($x0),2),'.',''))"/>
                                                <xsl:with-param name="r"
select="string-length(substring-before(concat(string($x0),'.'),'.')) *
2.30258509299404568402"/>
                                                <xsl:with-param
name="log_numbers">2,1.1,1.01,1.001,1.0001,1.00001,1.000001,1.0000001,1.00000001,</xsl:with-param>
                                                <xsl:with-param
name="log_values">0.69314718055994530942,0.09531017980432486004,0.00995033085316808285,0.00099950033308353317,0.00009999500033308335,0.00000999995000033333,0.00000099999950000033,0.00000009999999500000,0.00000000999999995000,</xsl:with-param>
                                        </xsl:call-template>
                                </xsl:variable>
                                <xsl:value-of select="$x1 * (number($x = $x0) * 
2 - 1)"/>
                        </xsl:otherwise>
                </xsl:choose>
        </xsl:template>
        <xsl:template name="log_">
                <xsl:param name="x"/>
                <xsl:param name="r"/>
                <xsl:param name="log_numbers"/>
                <xsl:param name="log_values"/>
                <xsl:choose>
                        <xsl:when test="$log_numbers != ''">
                                <xsl:variable name="temp"
select="number(substring-before($log_numbers,',')) * $x"/>
                                <xsl:choose>
                                        <xsl:when test="$temp &lt; 10">
                                                <xsl:call-template name="log_">
                                                        <xsl:with-param 
name="x" select="$temp"/>
                                                        <xsl:with-param 
name="r" select="$r -
number(substring-before($log_values,','))"/>
                                                        <xsl:with-param 
name="log_numbers" select="$log_numbers"/>
                                                        <xsl:with-param 
name="log_values" select="$log_values"/>
                                                </xsl:call-template>
                                        </xsl:when>
                                        <xsl:otherwise>
                                                <xsl:call-template name="log_">
                                                        <xsl:with-param 
name="x" select="$x"/>
                                                        <xsl:with-param 
name="r" select="$r"/>
                                                        <xsl:with-param 
name="log_numbers"
select="substring-after($log_numbers,',')"/>
                                                        <xsl:with-param 
name="log_values"
select="substring-after($log_values,',')"/>
                                                </xsl:call-template>
                                        </xsl:otherwise>
                                </xsl:choose>
                        </xsl:when>
                        <xsl:otherwise><xsl:value-of select="$r - (10 - $x) div 
10"/></xsl:otherwise>
                </xsl:choose>
        </xsl:template>
</xsl:stylesheet>


testTrig2.xsl (FXSL):
===============
<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform";>

 <xsl:import href="trignm.xsl"/>
 <!-- To be applied on TestSin.xml -->

 <xsl:output method="text"/>

  <xsl:template match="x">
         <xsl:call-template name="sin">
            <xsl:with-param name="pX" select="."/>
         </xsl:call-template>

  </xsl:template>
</xsl:stylesheet>


TestSin.xml
=========
<nums>
        <x>0</x>
        <x>0.01</x>
        <x>-0.01</x>
        <x>0.02</x>
        <x>-0.02</x>
        <x>0.03</x>
        <x>-0.03</x>
        <x>0.04</x>
        <x>-0.04</x>
        <x>0.05</x>
        <x>-0.05</x>
        <x>0.06</x>
        <x>-0.06</x>
        <x>0.07</x>
        <x>-0.07</x>
        <x>0.08</x>
        <x>-0.08</x>
        <x>0.09</x>
        <x>-0.09</x>
        <x>0.1</x>
        <x>-0.1</x>
        <x>0.11</x>
        <x>-0.11</x>
        <x>0.12</x>
        <x>-0.12</x>
        <x>0.13</x>
        <x>-0.13</x>
        <x>0.14</x>
        <x>-0.14</x>
        <x>0.15</x>
        <x>-0.15</x>
        <x>0.16</x>
        <x>-0.16</x>
        <x>0.17</x>
        <x>-0.17</x>
        <x>0.18</x>
        <x>-0.18</x>
        <x>0.19</x>
        <x>-0.19</x>
        <x>0.2</x>
        <x>-0.2</x>
        <x>0.21</x>
        <x>-0.21</x>
        <x>0.22</x>
        <x>-0.22</x>
        <x>0.23</x>
        <x>-0.23</x>
        <x>0.24</x>
        <x>-0.24</x>
        <x>0.25</x>
        <x>-0.25</x>
        <x>0.26</x>
        <x>-0.26</x>
        <x>0.27</x>
        <x>-0.27</x>
        <x>0.28</x>
        <x>-0.28</x>
        <x>0.29</x>
        <x>-0.29</x>
        <x>0.3</x>
        <x>-0.3</x>
        <x>0.31</x>
        <x>-0.31</x>
        <x>0.32</x>
        <x>-0.32</x>
        <x>0.33</x>
        <x>-0.33</x>
        <x>0.34</x>
        <x>-0.34</x>
        <x>0.35</x>
        <x>-0.35</x>
        <x>0.36</x>
        <x>-0.36</x>
        <x>0.37</x>
        <x>-0.37</x>
        <x>0.38</x>
        <x>-0.38</x>
        <x>0.39</x>
        <x>-0.39</x>
        <x>0.4</x>
        <x>-0.4</x>
        <x>0.41</x>
        <x>-0.41</x>
        <x>0.42</x>
        <x>-0.42</x>
        <x>0.43</x>
        <x>-0.43</x>
        <x>0.44</x>
        <x>-0.44</x>
        <x>0.45</x>
        <x>-0.45</x>
        <x>0.46</x>
        <x>-0.46</x>
        <x>0.47</x>
        <x>-0.47</x>
        <x>0.48</x>
        <x>-0.48</x>
        <x>0.49</x>
        <x>-0.49</x>
        <x>0.5</x>
        <x>-0.5</x>
        <x>0.51</x>
        <x>-0.51</x>
        <x>0.52</x>
        <x>-0.52</x>
        <x>0.53</x>
        <x>-0.53</x>
        <x>0.54</x>
        <x>-0.54</x>
        <x>0.55</x>
        <x>-0.55</x>
        <x>0.56</x>
        <x>-0.56</x>
        <x>0.57</x>
        <x>-0.57</x>
        <x>0.58</x>
        <x>-0.58</x>
        <x>0.59</x>
        <x>-0.59</x>
        <x>0.6</x>
        <x>-0.6</x>
        <x>0.61</x>
        <x>-0.61</x>
        <x>0.62</x>
        <x>-0.62</x>
        <x>0.63</x>
        <x>-0.63</x>
        <x>0.64</x>
        <x>-0.64</x>
        <x>0.65</x>
        <x>-0.65</x>
        <x>0.66</x>
        <x>-0.66</x>
        <x>0.67</x>
        <x>-0.67</x>
        <x>0.68</x>
        <x>-0.68</x>
        <x>0.69</x>
        <x>-0.69</x>
        <x>0.7</x>
        <x>-0.7</x>
        <x>0.71</x>
        <x>-0.71</x>
        <x>0.72</x>
        <x>-0.72</x>
        <x>0.73</x>
        <x>-0.73</x>
        <x>0.74</x>
        <x>-0.74</x>
        <x>0.75</x>
        <x>-0.75</x>
        <x>0.76</x>
        <x>-0.76</x>
        <x>0.77</x>
        <x>-0.77</x>
        <x>0.78</x>
        <x>-0.78</x>
        <x>0.79</x>
        <x>-0.79</x>
        <x>0.8</x>
        <x>-0.8</x>
        <x>0.81</x>
        <x>-0.81</x>
        <x>0.82</x>
        <x>-0.82</x>
        <x>0.83</x>
        <x>-0.83</x>
        <x>0.84</x>
        <x>-0.84</x>
        <x>0.85</x>
        <x>-0.85</x>
        <x>0.86</x>
        <x>-0.86</x>
        <x>0.87</x>
        <x>-0.87</x>
        <x>0.88</x>
        <x>-0.88</x>
        <x>0.89</x>
        <x>-0.89</x>
        <x>0.9</x>
        <x>-0.9</x>
        <x>0.91</x>
        <x>-0.91</x>
        <x>0.92</x>
        <x>-0.92</x>
        <x>0.93</x>
        <x>-0.93</x>
        <x>0.94</x>
        <x>-0.94</x>
        <x>0.95</x>
        <x>-0.95</x>
        <x>0.96</x>
        <x>-0.96</x>
        <x>0.97</x>
        <x>-0.97</x>
        <x>0.98</x>
        <x>-0.98</x>
        <x>0.99</x>
        <x>-0.99</x>
        <x>1</x>
        <x>-1</x>
</nums>





--
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, Mar 3, 2010 at 10:49 AM, COUTHURES Alain
<alain(_dot_)couthures(_at_)agencexml(_dot_)com> wrote:
Dimitre,

Unfortunately, FXSL is not in first results listed by Google when searching
"xslt sin" or "xslt cos".

By the way, almost 30 years ago, I already knew that calculators never use
Taylor series (CORDIC algorithms were written in 1959)... Even if they are
mathematically correct, they require too many iterations for small systems
and managing huge numbers such as factorials is not always possible. I'm
interested in XSLT at browser side and speed is important.

So, if FXSL users consider it good enough for their requirements, it's good
to know. Do you know if they are working at client-side or at server-side ?

Because I spent no more than one day to find algorithms and less than one
another to implement the ones I need, it wasn't for me a costly effort,
anyway.

If only Microsoft had already implemented XSLT 2.0, XPath 2.x, SVG,
XForms,... more efforts would have been saved...

Best regards,

-Alain

--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: 
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--




--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--