Этот пример показывает, как спроектировать функцию, которая принимает многочлен и значение и возвращает знак этого многочлена в этот момент. Эта функция является фильтром: если ответ не гарантирован, функции говорят об этом. Причина использования фильтра, а не простой функции оценки заключается в том, что вычисления с числами с плавающей точкой будут иметь приближения, и этого может быть достаточно, чтобы изменить знак полинома. Так, для проверки результата функция будет использовать интервальную арифметику.
Первым шагом является включение соответствующих заголовков. Поскольку функция будет обрабатывать границы с плавающей запятой, самым простым решением является:
#include <boost/numeric/interval.hpp>
Итак, давайте начнем функцию. Полиномиал дается массивом его коэффициентов и размерами (строго больше его степени). Для упрощения кода в библиотеку включены два пространства имен.
int sign_polynomial(double x, double P[], int sz) {
using namespace boost::numeric;
using namespace interval_lib;
Затем можно определить тип интервала. Поскольку не требуется никакого особого поведения, политики по умолчанию достаточно:
typedef interval<double> I;
Для оценки воспользуемся схемой Хорнера с интервальной арифметикой. Библиотека перегружает все арифметические операторы и обеспечивает смешанные операции, поэтому единственное различие между кодом с интервальной арифметикой и без нее заключается в типе итерируемого значения<y>:
I y = P[sz - 1];
for(int i = sz - 2; i >= 0; i--)
y = y * x + P[i];
Последним шагом является вычисление знака<y>. Делается это путем выбора подходящей схемы сравнения и затем проведения сравнения с обычными операторами:
using namespace compare::certain;
if (y > 0.) return 1;
if (y < 0.) return -1;
return 0;
}
Ответ<0>не означает, что многочлен равен нулю. Это означает, что ответ неизвестен, поскольку<y>содержит ноль и, следовательно, не имеет точного знака.
Теперь у нас есть ожидаемая функция. Однако из-за плохих реализаций округления с плавающей запятой в большинстве процессоров может быть полезно сказать, чтобы оптимизировать код; или, скорее, позволить библиотеке оптимизировать его. Главное условие такой оптимизации состоит в том, что интервальный код не следует смешивать с кодом с плавающей запятой. В данном примере это так, поскольку все операции, выполняемые в функциях, связаны с библиотекой. Код можно переписать:
int sign_polynomial(double x, double P[], int sz) {
using namespace boost::numeric;
using namespace interval_lib;
typedef interval<double> I_aux;
I_aux::traits_type::rounding rnd;
typedef unprotect<I_aux>::type I;
I y = P[sz - 1];
for(int i = sz - 2; i >= 0; i--)
y = y * x + P[i];
using namespace compare::certain;
if (y > 0.) return 1;
if (y < 0.) return -1;
return 0;
}
Разница между этим кодом и предыдущим заключается в использовании другого интервального типа. Этот новый тип<I>указывает библиотеке, что все вычисления могут быть выполнены без учета режима округления. И из-за этого функция должна заботиться о нем: округлый объект должен быть живым, когда используется оптимизированный тип.
Other tests and examples
В<libs/numeric/interval/test/>и<libs/numeric/interval/examples/>приведены некоторые тестовые и примерные программы. Примеры иллюстрируют несколько применений интервалов. Для общего описания и соображений по использованию этой библиотеки и некоторых потенциальных областей применения, пожалуйста, прочтите этот мини-гид..
Tests
Программы тестирования следующие. Обратите внимание, что они требуют использования крепления. Библиотека тестов и может быть автоматически протестирована с помощью<bjam>(за исключением интервала_test.cpp).
add.cppпроверяет, правильно ли реализованы аддитивные и субтрактивные операторы и соответствующие функции округления _std и _opp. Это делается с использованием символических выражений в качестве базового типа.
cmp.cpp,cmp_lex.cpp,cmp_set.cpp, иcmp_tribool.cppтест, если операторы<<><>><<=><>=><==><!=>ведут себя правильно для сравнения по умолчанию, лексикографического, набора и трисостояния.cmp_exp.cppпроверяет явные функции сравнения<cer..>и<pos..>ведут себя правильно.cmp_exn.cppпроверяет, правильно ли различные политики выявляют исключительные случаи. Все эти тесты используют некоторые простые интервалы ([1,2] и [3,4], [1,3] и [2,4], [1,2] и [2,3] и т. Д.).
det.cppтесты, если версии<_std>и<_opp>в защищенном и незащищенном режиме дают тот же результат, когда схема Гаусса используется на неустойчивой матрице (для осуществления округления). Проверка проводится для<interval<float>>и<interval<double>>.
fmod.cppопределяет минималистическую версию<interval<int>>и использует ее для проверки<fmod>на некоторых конкретных интервальных значениях.
mul.cppосуществляет умножение, конечное деление, квадрат и квадратный корень с некоторыми целочисленными интервалами, приводящими к точным результатам.
pi.cppпроверяет, содержит ли интервальное значение π (для<int>,<float>и<double>типов оснований) число π (определяется 21 десятичной цифрой) и является ли оно подмножеством [π±1ulp] (для обеспечения некоторой точности).
pow.cppпроверяет, правильно ли выполняется функция<pow>в некоторых простых тестовых случаях.
test_float.cppвыполняет арифметические операции библиотеки для типов баз с плавающей запятой.
interval_test.cppпроверяет, соблюдает ли библиотека интервалов свойство включения интервальной арифметики, вычисляя некоторые функции и операции для<double>и<interval<double>>.
Examples
filter.cppсодержит фильтры для вычислительной геометрии, способные находить знак детерминанта. Этот пример вдохновлен статьейИнтервальная арифметика дает эффективные динамические фильтры для вычислительной геометрииот Brönnimann, Burnikel and Pion, 2001.
findroot_demo.cppнаходит нули некоторых функций с помощью дихотомии и даже производит данные gnuplot для одной из них. Процессор должен правильно обрабатывать элементарные функции для правильной работы.
horner.cppявляется на самом деле базовым примером незащиты интервальных операций для целой функции (которая вычисляет значение полинома по схеме Хорнера).
io.cppпоказывает некоторые операторы ввода и вывода потока для интервалов. Широкое разнообразие возможностей объясняет, почему в библиотеке не реализованы операторы i/o и они предоставлены пользователю.
newton-raphson.cpp— реализация специализированной версии алгоритма Ньютона-Рафсона для нахождения нулей функции, знающей её производную. Он выполняет незащищенные, полные деления, некоторые заданные операции и пустые интервалы.
transc.cppреализует трансцендентальную часть политики округления для<double>с помощью внешней библиотеки (в данном случае подмножества MPFR GMP).
