Ниже предлагаются реализации на языке XSLT 1.0 функций для вычисления абсолютного значения, квадратного корня, логарифмов, степенной функции и факториала.
<xsl:templatename="ckbk:sqrt"><!-- Число, из которого извлекается квадратный корень. --><xsl:paramname="number"select="0"/><!-- Текущее "приближение". Внутренняя переменная. --><xsl:paramname="try"select="1"/><!-- Номер текущей итерации. Сравнивается с maxiter для ограничения количества повторений цикла. --><xsl:paramname="iter"select="1"/><!-- Этот параметр предотвращает бесконечный цикл. --><xsl:paramname="maxiter"select="20"/><!-- Этот шаблон написал Нэйт Остин, применив метод Ньютона для извлечения корня. --><xsl:choose><xsl:whentest="$try * $try = $number or $iter > $maxiter"><xsl:value-ofselect="$try"/></xsl:when><xsl:otherwise><xsl:call-templatename="ckbk:sqrt"><xsl:with-paramname="number"select="$number"/><xsl:with-paramname="try"select="$try - (($try * $try - $number) div (2 * $try))"/><xsl:with-paramname="iter"select="$iter + 1"/><xsl:with-paramname="maxiter"select="$maxiter"/></xsl:call-template></xsl:otherwise></xsl:choose></xsl:template>
Изменение начального значения параметра try может заметно повысить производительность:
1 2 3 4 5 6 7 8 910111213
<xsl:templatename="math:sqrt"><!-- Число, из которого извлекается квадратный корень. --><xsl:paramname="number"select="0"/><!-- Текущее "приближение". Внутренняя переменная. --><xsl:paramname="try"select="($number < 100) +102 ($number >= 100 and $number < 1000) * 10 + ($number >= 1000 and $number < 10000) * 31 + ($number >= 10000) * 100"/><!-- Больше ничего не меняется. --></xsl:template>
Этот нехитрый трюк (в котором снова применяется преобразование булевских значений в числовые) позволяет подобрать величину try так, чтобы она лучше аппроксимировала квадратный корень на самой первой итерации. Вычислив в тестовой программе корни из всех чисел от 1 до 10000, я получил выигрыш 10%.
Логарифмы: ckbk:log10(number), ckbk:log(number) и ckbk:logN(x,base)¶
Если имеющийся у вас процессор XSLT поддерживает функцию exsl:log() (натуральный логарифм), то реализовать логарифм по любому другому основанию просто. На псевдокоде это выглядит так:
12
<!-- Основное правило логарифмов -->
ckbk:logN(x,base) = ckbk:logN(x,diffBase) div ckbk:logN(base,diffBase)
К сожалению, ни один из процессоров, перечисленных на сайте EXSLT.org, пока не поддерживает функцию exsl:log. Следующий вариант – реализовать расширение на языке Java, воспользовавшись классом java.lang.Math.log или функцией Math.log в JavaScript. Наконец, можно не прибегать к расширениям вовсе, а написать log10 на чистом XSLT с приемлемой для большинства приложений точностью и производительностью. Имея реализацию log10(), можно вычислять произвольные логарифмы, применяя основное правило.
<xsl:templatename="ckbk:log10"><xsl:paramname="number"select="1"/><xsl:paramname="n"select="0"/><!-- служебная переменная для хранения целой части результата --><xsl:choose><!-- Для нуля и отрицательных чисел логарифм не определен --><xsl:whentest="$number <= 0"><xsl:value-ofselect="NaN"/></xsl:when><xsl:whentest="$number < 1"><!-- Логарифм числа, меньшего 1, отрицателен --><xsl:call-templatename="ckbk:log10"><xsl:with-paramname="number"select="$number * 10"/><xsl:with-paramname="n"select="$n - 1"/></xsl:call-template></xsl:when><xsl:whentest="$number > 10"><!-- Если число больше 10, его логарифм больше 1 --><xsl:call-templatename="ckbk:log10"><xsl:with-paramname="number"select="$number div 10"/><xsl:with-paramname="n"select="$n + 1"/></xsl:call-template></xsl:when><xsl:whentest="$number = 10"><xsl:value-ofselect="$n + 1"/></xsl:when><xsl:otherwise><!-- Нам нужно лишь уметь вычислить логарифмы чисел в диапазоне [1,10) --><xsl:call-templatename="ckbk:log10-util"><xsl:with-paramname="number"select="$number"/><xsl:with-paramname="n"select="$n"/></xsl:call-template></xsl:otherwise></xsl:choose></xsl:template><!-- Вычисляет натуральный логарифм числа --><xsl:templatename="ckbk:log"><xsl:paramname="number"select="1"/><xsl:variablename="log10-e"select="0.4342944819"/><xsl:variablename="log10"><xsl:call-templatename="ckbk:log10"><xsl:with-paramname="number"select="$number"/></xsl:call-template></xsl:variable><xsl:value-ofselect="$log10 div $log10-e"/></xsl:template><!-- Вычисляет логарифм числа по основанию b --><xsl:templatename="ckbk:log-b"><xsl:paramname="number"select="1"/><xsl:paramname="base"select="2"/>104
<xsl:variablename="log10-base"><xsl:call-templatename="ckbk:log10"><xsl:with-paramname="number"select="$base"/></xsl:call-template></xsl:variable><xsl:variablename="log10"><xsl:call-templatename="ckbk:log10"><xsl:with-paramname="number"select="$number"/></xsl:call-template></xsl:variable><xsl:value-ofselect="$log10 div $log10-base"/></xsl:template><!-- Вычисляет log10 для чисел в диапазоне [1,10) + n --><xsl:templatename="ckbk:log10-util"><xsl:paramname="number"/><xsl:paramname="n"/><xsl:paramname="frac"select="0"/><!-- служебная переменная для хранения дробной части --><xsl:paramname="k"select="0"/><!-- счетчик итераций --><xsl:paramname="divisor"select="2"/><!-- последовательные степени 2 для построения дробной части --><xsl:paramname="maxiter"select="38"/><!-- Число итераций. 38 более чем достаточно для получения не менее 10 точных цифр --><xsl:variablename="x"select="$number * $number"/><xsl:choose><xsl:whentest="$k >= $maxiter"><!-- Округлить до 10 значащих десятичных цифр --><xsl:value-ofselect="$n + round($frac * 10000000000) div 10000000000"/></xsl:when><xsl:whentest="$x < 10"><xsl:call-templatename="ckbk:log10-util"><xsl:with-paramname="number"select="$x"/><xsl:with-paramname="n"select="$n"/><xsl:with-paramname="k"select="$k + 1"/><xsl:with-paramname="divisor"select="$divisor * 2"/><xsl:with-paramname="frac"select="$frac"/><xsl:with-paramname="maxiter"select="$maxiter"/></xsl:call-template></xsl:when><xsl:otherwise><xsl:call-templatename="ckbk:log10-util"><xsl:with-paramname="number"select="$x div 10"/><xsl:with-paramname="n"select="$n"/><xsl:with-paramname="k"select="$k + 1"/><xsl:with-paramname="divisor"select="$divisor * 2"/><xsl:with-paramname="frac"select="$frac + (1 div $divisor)"/><xsl:with-paramname="maxiter"select="$maxiter"/></xsl:call-template></xsl:otherwise></xsl:choose></xsl:template>
Основная задача шаблона ckbk:log10 – свести задачу вычисления log10(x) к более простой задаче вычисления log10(x : 1 <= x < 10). Кроме того, контролируются входные данные, так как для нуля и отрицательных чисел логарифм не определен.
Вспомогательный шаблон ckbk:log10-util делает всю сложную работу. Это основанная на хвостовой рекурсии реализация итеративного алгоритма, описанного в книге Кнута. Чтобы организовать хвостовую рекурсию и существенно упростить реализацию, мы ввели несколько служебных параметров:
n
Целая часть результата, передаваемая в шаблон ckbk:log10. Без этого параметра можно было бы обойтись, так как передаваемую величину можно хранить, пока ckbk:log10-util занимается своей работой. Однако он позволяет избежать необходимости сохранять результат ckbk:log10-util в переменной.
frac
Дробная часть результата. Именно ее мы и ищем.
k
Счетчик итераций, который увеличивается на 1 при каждом рекурсивном вызове. Рекурсия прекращается, как только $k > $maxiter.
divisor
Число, которому присваивается следующая по порядку степень 2 при каждом рекурсивном вызове (т. е. 2, 4, 8, 16, ...). Величина 1 div $divisor прибавляется к frac по мере аппроксимации логарифма.
maxiter
Количество итераций для вычисления frac. Чем больше maxiter, тем выше точность результата (в границах, определяемых представлением числа с плавающей точкой в формате IEEE). Этот параметр можно было бы и опустить, но он позволяет вызывающей программе задать требуемое число итераций и тем самым установить компромисс между быстродействием и точностью.
В настоящий момент на сайте EXSLT.org не упомянуты процессоры, поддерживающие функцию ckbk:power(). Однако она определена в проекте EXSLT и может быть легко реализована на чистом XSLT. Джени Теннисон предлагает такой шаблон:
Для большинства приложений этот код вполне приемлем. Однако рекурсия в нем не хвостовая и алгоритмически он не самый эффективный. Следующая реализация лишена первого недостатка, а число операций умножения в ней уменьшилось с O($power) до O(log2($power). Кроме того, добавлена обработка ошибок, предотвращающая бесконечную рекурсию в случае, когда $power равно NaN.
<xsl:templatename="ckbk:power"><xsl:paramname="base"/><xsl:paramname="power"/><xsl:paramname="result"select="1"/><xsl:choose><xsl:whentest="number($base) != $base or number($power) != $power"><xsl:value-ofselect="'NaN'"/></xsl:when><xsl:whentest="$power = 0"><xsl:value-ofselect="$result"/></xsl:when><xsl:otherwise><xsl:call-templatename="ckbk:power"><xsl:with-paramname="base"select="$base * $base"/><xsl:with-paramname="power"select="floor($power div 2)"/><xsl:with-paramname="result"select="$result * $base * ($power mod 2) + $result * not($power mod 2)"/></xsl:call-template></xsl:otherwise></xsl:choose></xsl:template>
Здесь мы ввели служебный параметр $result, в котором строится окончательный результат. Он и позволяет организовать хвостовую рекурсию. При каждом рекурсивном вызове основание возводится в квадрат, а показатель степени уменьшается вдвое. Поскольку мы пользуемся функцией floor(), $result достигнет 0 за ceiling(log2($power)) рекурсивных вызовов. Это повышает производительность. Хитроумная часть заключается в вычислении $result на каждом шаге.
Проанализируем это выражение, обращая внимание на оба слагаемых. Выражение $result * $base * ($power mod 2) равно $result * $base, если $power нечетно и 0 в противном случае. Наоборот, $result * not($power mod 2) равно 0, когда $power четно и $result в противном случае. В XPath 2.0 это можно было бы записать как if ($power % 2) then result *base else result.
А в XPath 1.0 приходится прибегать к трюкам. Так или иначе, шаблон вычисляет сумму b1 _ base + b2 _ base2 + b3 _ base4 + b4 _ base8 ..., где bi попеременно равно 0 или 1.
Легко видеть, что суммирование может производиться до basepower для произвольного целого числа power, если задавать в качестве bi подходящие значения, что как раз и делает выражение $power mod 2. Если идея осталась непонятной, проработайте на бумаге несколько примеров, чтобы убедиться, что все работает правильно.
Показанная выше реализация степенной функции умеет вычислять только целые положительные степени. Однако, как известно любому студенту-математику, xy является вещественным числом для всех вещественных x и y, а не только для натуральных показателей степени. Хорошо было бы иметь общую версию функции power(), вдруг пригодится. Ниже мы приводим соответствующий код.
Чтобы не путать его с power(), шаблон называется power-f(), где f происходит от «floating point» (с плавающей точкой). Если хотите, можете назвать более общую версию power(), только внесите изменения в код ниже. Впрочем, иметь более специализированную версию в качестве отдельной функции тоже полезно.
Честно говоря, я думаю, что по меньшей мере в 80 процентах ваших приложений математика за пределами встроенных в XSLT возможностей никогда не понадобится. Ну а если в оставшихся 20 процентах случаев возникнет необходимость в функциях, отсутствующих в XSLT 1.0, то приведенные выше рецепты могут пригодиться.
Самый крупный недостаток реализаций на чистом XSLT 1.0 заключается в том, что шаблоны нельзя вызывать как настоящие функции из выражений на языке XPath. Поэтому математические операции записываются громоздко и оказываются не очень эффективными; ведь для запоминания вызовов шаблонов, представленных в виде результирующего фрагмента дерева, приходится создавать искусственные переменные. А процессор XSLT должен выполнять обратное преобразование этого фрагмента в число, когда впоследствии оно используется в вычислениях.
Еще одна проблема реализаций на XSLT состоит в том, что открытый интерфейс шаблонов замусорен служебными параметрами, которые лишь затемняют смысл функции. Эти параметры необходимы, чтобы организовать хвостовую рекурсию и предотвратить тем самым излишнюю работу. Например, в шаблоне power-frac логарифм основания вычисляется один раз и передается при каждом рекурсивном вызове. Если бы ln_base не был параметром, то логарифм пришлось бы при каждом таком вызове вычислять заново, и производительность оказалось бы неприемлемо низкой.
XSLT 2.0 решает первую проблему, предоставляя полноценные функции. Поэтому в этой версии решения получаются более компактными и простыми. Но параметры команды xsl:function не могут принимать значения по умолчанию, так что этот недостаток приходится компенсировать, определяя перегруженные варианты функций с различной арностью. К сожалению, XSLT 2.0 не позволяет инкапсулировать закрытые параметры, которые необходимы при рекурсивных вызовах функций для служебных целей. Проектируя библиотеку функций, вы можете поместить внутренние реализации (те, в которых используются служебные параметры) в отдельное пространство имен, чтобы показать, что к таким функциям не следует обращаться напрямую.
Вторая проблема будет отчасти решена, если в будущих версиях XSLT появятся закрытые параметры, предназначенные только для рекурсивных вызовов.