Factorial in XSLT limit?

Question

Hi. I have the following factorial function implemented in XSLT:

<?xml version="1.0"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"&gt;
    <xsl:output method="text"/>
    <xsl:template match="/">
     <xsl:apply-templates>
     </xsl:apply-templates>
    </xsl:template>

    <xsl:template match="factorial" name="factorial">
     <xsl:param name="n" select="@n" />
     <xsl:param name="f" select="1" />
     <xsl:if test="$n &gt; 1">
      <xsl:call-template name="factorial">
       <xsl:with-param name="n">
        <xsl:value-of select="$n - 1" />
       </xsl:with-param>
       <xsl:with-param name="f">
        <xsl:value-of select="$f * $n" />
       </xsl:with-param>
      </xsl:call-template>
     </xsl:if>
     <xsl:if test="$n = 1">
      <xsl:value-of select="$f" />
     </xsl:if>
    </xsl:template>
</xsl:stylesheet>

In both Firefox and IE7, 170! works fine but 171! only returns NaN. Is this a well-defined limit in XSLT/XPath math, or is there a way of getting even higher values of n! ?

Answer 1

XPath specification defines number type as follows:

A number represents a floating-point number. A number can have any double-precision 64-bit format IEEE 754 value.

So the limits are well-defined. I haven't checked it, but given how large 171! is, you're probably hitting them.

Answer 2

I'm going to hazard a guess that your issue is XSLT implementation dependant.

This looks like a standard overflow problem. I found a hint by replicating the problem using a JavaScript factorial implementation found here: http://www.cs.uml.edu/~ytran/factorial.html

In another language, I would use a BigInteger library for such large numbers. A quick search [terms: XSLT BigInteger] using Google finds that XSLT does not have a native BigInteger type.

Answer 3

Adding to the correct answers for XPath 1.0, in XPath 2.0 there is the xs:integer datatype and there is no maximum for the absolute value of an xs:integer.

Saxon implements BigInteger arithmetic, and given your code (slightly changed with the addition of the xs:integer type):

<xsl:template match="factorial" name="factorial">
 <xsl:param name="n" as="xs:integer"
  select="xs:integer(@n)" />
 <xsl:param name="f" as="xs:integer" select="1" />

 <xsl:if test="$n gt 1">
  <xsl:call-template name="factorial">
   <xsl:with-param name="n">
    <xsl:value-of select="$n - 1" />
   </xsl:with-param>
   <xsl:with-param name="f">
    <xsl:value-of select="$f * $n" />
   </xsl:with-param>
  </xsl:call-template>
 </xsl:if>
 <xsl:if test="$n = 1">
  <xsl:value-of select="$f" />
 </xsl:if>
</xsl:template>

when it is applied to the following XML document:

<factorial n = "171"/>

the correct result is produced:

1241018070217667823424840524103103992616605577501693185388951803611996075221691752992751978120487585576464959501670387052809889858690710767331242032218484364310473577889968548278290754541561964852153468318044293239598173696899657235903947616152278558180061176365108428800000000000000000000000000000000000000000

Certainly, I'd prefer to write this using the FXSL library in a single expression:

    f:foldl(f:mult(), 1, 1 to 171)

within this XSLT stylesheet:

<xsl:stylesheet version="2.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:f="http://fxsl.sf.net/"
>
   <xsl:import href="../f/func-dvc-foldl.xsl"/>
   <xsl:import href="../f/func-Operators.xsl"/>

    <xsl:output  encoding="UTF-8" method="text"/>

    <xsl:template match="/">
      <xsl:value-of select="f:foldl(f:mult(), 1, 1 to 171)"/>
    </xsl:template>
</xsl:stylesheet>