CODEWITHSUNDEEP
xmlinternet-explorerfirefoxxslt
erjiang
erjiang

Reputation: 45727

Factorial in XSLT limit?

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">
    <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! ?

Upvotes: 2

Views: 1505

Answers (3)

Dimitre Novatchev
Dimitre Novatchev

Reputation: 243529

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>

Upvotes: 3

Berin
Berin

Reputation: 75

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.

Upvotes: 0

Pavel Minaev
Pavel Minaev

Reputation: 101615

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.

Upvotes: 2

Related Questions