Subject: Re: [xsl] Math "functions" for XSLT 1.0 From: Dimitre Novatchev <dnovatchev@xxxxxxxxx> Date: Wed, 3 Mar 2010 19:07:07 -0800 |
On Wed, Mar 3, 2010 at 11:38 AM, Dimitre Novatchev <dnovatchev@xxxxxxxxx> 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 > $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 < 0">NaN</xsl:when> <xsl:when test="(($u2 - $u1)*(number($u2 > $u1) * 2 - 1)) > $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 >= $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 > $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 > $pi div 2 and $x0 < $pi"><xsl:value-of select="$x0 - $pi"/></xsl:when> <xsl:when test="$x0 > $pi and $x0 < $pi * 1.5"><xsl:value-of select="$pi - $x0"/></xsl:when> <xsl:when test="$x0 > $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 > 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 > $pi div 2 and $x0 < $pi * 1.5"><xsl:value-of select="$pi - $x0"/></xsl:when> <xsl:when test="$x0 > $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 > 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 <=0">NaN</xsl:when> <xsl:when test="$x = 1">0</xsl:when> <xsl:otherwise> <xsl:variable name="x0"> <xsl:choose> <xsl:when test="$x < 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.00000 001,</xsl:with-param> <xsl:with-param name="log_values">0.69314718055994530942,0.09531017980432486004,0.00995033085 316808285,0.00099950033308353317,0.00009999500033308335,0.0000099999500003333 3,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 < 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.couthures@xxxxxxxxxxxxx> 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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Math "functions" for XSLT, Dimitre Novatchev | Thread | Re: [xsl] Math "functions" for XSLT, COUTHURES Alain |
Re: [xsl] Pattern Substring, Wendell Piez | Date | Re: [xsl] Math "functions" for XSLT, Dimitre Novatchev |
Month |