ash’s blog / все про maths

Вычисление синуса в XSLT

XSLT помимо хороших, но утилитарных качеств дает необъятные возможности для разных фантазий. Вот еще одна фантазия, которая потребовалась мне для демонстрации возможностей XSLT и производительности libxslt.

Если не подключать никаких расширений, то в базовом комплекте XSLT (а точнее, XPath) не имет в наборе тригонометрических функций. Доступна лишь арифметика: сложить, умножить, разделить, получить остаток — которой, впрочем, достаточно и для того, чтобы вычислить синус и косинус. Мой шаблон для вычисления синуса состоит ровно из ста строк (включая пустые). Это, конечно не три символа для вызова функции sin в любом языке программирования: здесь интерес представляет сам процесс.

Значение синуса для данного x вычислить относительно просто, воспользовавшись разложением в степенной ряд:

Иными словами, требуется сложить нечетные степени x, поочередно меняя знак (наглядно и визуально):

Тестировать правильность вычисления я буду на двух величинах: sin(π) и sin(π/2). Соответственно, результатом должны быть ноль и единица.

Исходные данные записаны в XML:

<?xml version="1.0"?>
<math>
    <sin x="3.1415926535898"/>
    <sin x="1.5707963267949"/>
</math>

Глядя на формулу вычисления синуса, сразу становится понятным, что потребуются рекурсивные вызовы в XSLT. Чуть позже понимаешь, что рекурсия нужна не только для подсчета суммы, но и для вычисления факториала, и для возведения в степень.

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="//sin">
    <xsl:text>sin(</xsl:text>
    <xsl:value-of select="@x"/>
    <xsl:text>) = </xsl:text>   
   
    <xsl:call-template name="sin-row">
        <xsl:with-param name="x" select="@x"/>
        <xsl:with-param name="N" select="10"/>
    </xsl:call-template>
   
    <xsl:text>&#10;</xsl:text>
</xsl:template>

Именованный шаблон sin-row (который и вычисляет синус) получает на входе переменную x и число слагаемых в ряду, которые я хочу учитывать. Чем больше слагаемых, тем больше точность и дольше вычисления.

<xsl:template name="sin-row">
    <xsl:param name="x"/>
    <xsl:param name="n" select="0"/>
    <xsl:param name="N" select="5"/>
    <xsl:param name="sin" select="0"/>

Внутри sin-row вычисляются промежуточные значения — множители, участвующие в вычислении очередного слагаемого: p1 — это степень –1, p2 — нечетная степень x, fact — факториал в знаменателе.

    <xsl:variable name="p1">
        <xsl:call-template name="power">
            <xsl:with-param name="x" select="-1"/>
            <xsl:with-param name="n" select="$n"/>
        </xsl:call-template>
    </xsl:variable>

    <xsl:variable name="p2">
        <xsl:call-template name="power">
            <xsl:with-param name="x" select="$x"/>
            <xsl:with-param name="n" select="2 * $n + 1"/>
        </xsl:call-template>
    </xsl:variable>

    <xsl:variable name="fact">
        <xsl:call-template name="factorial">
            <xsl:with-param name="n" select="2 * $n + 1"/>
        </xsl:call-template>
    </xsl:variable>

Результат суммируется с величиной, полученной на предыдущей итерации:

    <xsl:variable name="sum" select="$sin + $p1 * $p2 div $fact"/>

Итерации повторяются до тех пор, пока не будет достигнуто предварительно заданное число слагаемых N:

    <xsl:choose>
        <xsl:when test="$n &lt; $N">
            <xsl:call-template name="sin-row">
                <xsl:with-param name="x" select="$x"/>
                <xsl:with-param name="n" select="$n + 1"/>
                <xsl:with-param name="N" select="$N"/>
                <xsl:with-param name="sin" select="$sum"/>
            </xsl:call-template>
        </xsl:when>
        <xsl:otherwise>
            <xsl:value-of select="$sum"/>
        </xsl:otherwise>
    </xsl:choose>
</xsl:template>

Возведение в степень выполняет вторая итеративная функция — шаблон с именем power. Его построение довольно прямолинейно: передавая текущее вычисленное значение, повторно вызывать самого себя, пока не иссякнет запрошенный показатель степени:

<xsl:template name="power">
    <xsl:param name="x"/>
    <xsl:param name="n"/>

    <xsl:choose>
        <xsl:when test="$n = 0">1</xsl:when>
        <xsl:when test="$n = 1">
            <xsl:value-of select="$x"/>
        </xsl:when>
        <xsl:otherwise>
            <xsl:variable name="pow-1">
                <xsl:call-template name="power">
                    <xsl:with-param name="x" select="$x"/>
                    <xsl:with-param name="n" select="$n - 1"/>
                </xsl:call-template>
            </xsl:variable>
            <xsl:value-of select="$x * $pow-1"/>
        </xsl:otherwise>
    </xsl:choose>
</xsl:template>

Очень похоже устроен шаблон для вычисления факториала. Разница с power лишь в том, что здесь перемножаются номера итераций, а не аргумент.

<xsl:template name="factorial">
    <xsl:param name="n"/>
   
    <xsl:variable name="fact-1">
        <xsl:choose>
            <xsl:when test="$n &lt;= 1">1</xsl:when>
            <xsl:otherwise>
                <xsl:call-template name="factorial">
                    <xsl:with-param name="n" select="$n - 1"/>
                </xsl:call-template>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:variable>
   
    <xsl:value-of select="$n * $fact-1"/>
</xsl:template>

Все готово для тестирования. Запускаем процессор и передаем ему данные из XML:

$ xsltproc sin.xslt sin.xml

На экране появляются результаты:

    sin(3.1415926535898) =  1.03457906425793e-11

    sin(1.5707963267949) = 1

Единица для sin(π/2) получилось вообще идеальной; результат sin(π) очень близок к нулю.

Скорость работы с учетом того, что требуется прочитать с диска два файла — вдвое меньше, чем вызов функции на перле. Честно говоря, я ожидал, что XSLT будет работать еще медленнее, особенно, если учесть, что в моем примере никак не оптимизированы три момента: во-первых, чередование знака возможно определять, используя деление по модулю, а не вызывом итеративной функции возведения в степень; во-вторых, вычисленные на предыдущих итерациях степени x и промежуточные значения факториала вычисляются вновь и вновь, хотя их следовало бы запоминать и передавать на следующую итерацию.

programming, xslt, fun, maths — 26 июля 2009