boost.png (6897 bytes) 區間算術庫

本頁目錄:
簡介
概要
interval 模板類
操作和函數
interval 支持庫
常見的缺陷和危險
基本原理
變更歷史以及致謝
與本頁相關的其它頁面:
捨入策略
檢查策略
策略操作
比較
基本數字類型要求
選擇你自己的區間類型
測試和例子程序
頭文件包含
改進表中的一些事項

簡介和概覽

就像庫的名字暗示的那樣,這個庫打算用來操作數學區間. 它由一個頭文件<boost/numeric/interval.hpp>構成並且包含一個主要的可以用作interval<T>的類型.事實上,這個interval模板被聲明為interval<T,Policies> ,其中,Policies 是一個用來控制這個interval 類的不同行為的策略類; interval<T>碰巧為類型T選擇了默認的策略.

注意! 針對於本地浮點數格式的區間算術並不是對每一種處理器,操作系統和編譯器的結合都得到保證. 下面是一個已知的當使用interval<float>和interval<double>與一些基本的算術運算符可以正確工作的系統的列表.

上面的列表並不是全面的,即使一種系統並不提供針對於硬件浮點數類型的得到保證的計算 ,這個 interval庫仍然可以與用戶自定義的數據類型一起使用以及進行方塊算術(box arithmetic).

區間算術

區間是一對數,這對數用於表示它們之間的所有的數. (當邊界值被包含的時候區間被稱作閉區間.) 這個庫的目的是將一般的算術運算擴展到區間之上. 這些區間將被寫作 [a,b] 用於表示ab之間的所有數(包括a和b ). ab 可以是無限的 (但它們不能是同樣的無限(same infinite)) 並且滿足ab.

區間算術的基本性質是包含性質(inclusion property):

`如果f是關於一組數的函數, f 可以被擴展為定義在一個區間上的新的函數. 新的函數 f 帶有一個區間參數並且返回一個區間。例如: ∀ x ∈ [a,b], f(x) ∈ f([a,b]).''

這個性質並不僅限於只有一個參數的函數. 只要有可能, 區間結果應當是可以滿足區間性質的最小的一個區間 (如果新的函數永遠都返回 [-∞,+∞],那麼這個新的函數將沒有實際的用處).

至少有兩個原因一個用戶會使用這個庫. 最明顯的一個原因是當用戶需要進行區間運算. 一個例子是當輸入的數據具有固有的不精確性,輸入變量可以由區間來取代數字進行傳遞。另一個例子是一個用於解方程的應用程序,通過平分一個區間直到這個區間的寬度足夠窄。第三個例子是計算機圖形學中的應用程序,與 矩形(boxes) , 弦,射線相關的計算可以通過區間簡化為與點相關的計算.

另一個使用區間的常見的原因是當計算機不能產生精確結果的時候: 通過使用區間, 可以量化捨入錯誤的傳播. 這種方法經常用在數值計算當中. 例如,假設計算機存儲的數字帶有10個十進制有效數字. 對於 1 + 1E-100 - 1這種計算問題, 計算機的計算結果為0,雖然實際的正確結果為 1E-100. 在區間算術的幫助之下,這計算機計算的結果將會是 [0,1E-9]. 對於這麼小的一個計算結果,[0,1E-9]是一個非常大的區間, 但現在精度是已知的,不需要計算誤差的傳播.

數字,捨入,以及異常行為

基數字類型(base number type) 是用來保存區間邊界值的類型. 為了成功的使用區間算術, 基數字類型(base number type) 必須體現出一些特性. 首先, 依據區間的定義, 基數字類型必須是完全有序的, 所以,例如, complex<T>不能作為區間的基數字類型. 針對於基本數字類型的函數應當與全序(total order)相兼容 (例如,如果 x>y 並且 z>t, 那麼應當滿足 x+z > y+t), 所以,模數類型(modulo types)也是不可用的.

其次, 計算必須是精確的或者提供一些捨入方式 (例如, 向負無窮或是向正無窮捨入) 如果我們想要保證包含性質(inclusion property). 注意, 我們也可以明確地指定沒有捨入,是精確的, 例如,如果基數字類型是精確的. 那麼數字運算的結果永遠都是可以表示而沒有精度的損失.如果數字類型不是精確的, 我們仍然可以指定沒有捨入, 必然的結果是包含性質不再得到保證.

最後, 因為嚴懲的精度損失永遠都是可能的, 一些數必須用來表示無限的概念或者必須定義一種異常行為. 對於NaN(Not a Number)也會發生同樣的情況.

給定所有的這些, 有人可能想要限制interval模板參數T的類型為浮點數類型 float, double, 和 long double, 就像 IEEE-754 標準定義的那樣. 事實上,如果區間算術打算用來取代處理器的浮點運算單元提供的浮點運算,這些類型是最好的選擇.然而,不像std::complex, 我們不想局限於這些類型. 這就是為什麼我們允許用兩種策略來指定捨入和異常行為(捨入和檢查).我們仍然提供了針對於浮點類型的高度優化的捨入和檢查類 .

運算和函數

在包含性質的指導下,可以很直接地定義區間上的初等算術運算(elementary arithmetic operations). 例如, 如果 [a,b] 是 [c,d] 兩個區間, [a,b]+[c,d]可以通過取包含所有的x+y 的和的最小的區間來計算,其中 x 屬於 [a,b] 且 y 屬於 [c,d]; 在這種情況下, a+c 向下捨入並且 b+d向上捨入就足夠的. 類似的也定義了其它的運算符和函數(在下面查看它們的定義).

比較

同樣也定義了一些比較運算符. 給定兩個區間, 結果是一個三態布爾類型 {false,true,indeterminate}. 答案 falsetrue 很容易操作 ,因為它們能夠直接映射為布爾truefalse.但是這種情況並不適用於 indeterminate 因為比較運算符假定是布爾函數. 因此, 為了獲取布爾值,我們應該怎麼辦呢?

一種解決方案是採納一個異常行為, 比如,一個失敗的斷言或是拋出一個異常.在這種情況下,如果結果是未定義的,那麼將會觸發一個異常.

另一種解決方案是將未定義映射為 falsetrue. 如果選擇false , 比較將被稱作"確定;" 實際上, [a,b] < [c,d]為真,當且僅當: ∀ x ∈ [a,b] ∀ y ∈ [c,d], x < y. 如果選擇true , 比較將被稱作是 "可能;" 實際上, [a,b] < [c,d] 為真,當且僅當: ∃ x ∈ [a,b] ∃ y ∈ [c,d], x < y.

因為任意一種解決方案都有一個清楚定義的語義,我們並不清楚到底應當強制使用哪一個解決方案. 出於這樣的 原因,默認的行為是通過在未定義的情況拋出一個異常來模仿真正的比較運算。另一種可以選擇的方式是通過使用特定的比較名字空間,同樣有一些明確命名的比較函數. 詳細內容參見比較頁面.

庫的概覽以及使用

這個庫提供兩個不同的使用層次.一個是使用基本的類模板interval<T>而不指定所使用的策略. 這僅僅需要知道和理解上面描述的內容以及名字空間boost中的內容.除interval<T>之外, 這種層次的使用提供算術運算符(+, -, *, /), 代數和分段代數函數 (abs, square, sqrt, pow), 超越函數和三角函數 (exp, log, sin, cos, tan, asin, acos, atan, sinh, cosh, tanh, asinh, acosh, atanh), 以及標準的比較運算符(<, <=, >, >=, ==, !=), 以及一些區間特定的函數 (min, max, 與標準的std::min and std::max相比,這些函數具有不同的意義; lower, upper, width, median, empty, singleton, equal, in, zero_in, subset, proper_subset, overlap, intersection, hull, bisect).

對於一些帶有多個interval<T> 類型參數的函數, 所有的變量類型Tinterval<T>組合的轉化,其中至少包含一個interval<T>類型的參數, 都被考慮到了,為的是避免從T到一個單元素的interval<T>的轉換. 這是出於效率的考慮 (有時導致不必要的測試).

庫的更高級的使用是手動選擇捨入和檢查策略並將其傳遞給interval<T, Policies>通過使用Policies:= boost::numeric::interval_lib::policies<Rounding,Checking>. 合適的策略能夠通過使用 boost::numeric::interval_lib中提供的各種類來進行組裝,這些類在區間支持庫中有詳細的描述.同樣也可以通過重載運算符來選擇比較的方式,.
.

概要

namespace boost {
namespace numeric {

namespace interval_lib {
/*對於區間類的聲明這個聲明是必須的*/
template <class T> struct default_policies;

/* ... ; 名字空間 interval_lib 的完整概要可以在這裡找到 */

} // namespace interval_lib


/* 模板 interval_policies; 類的定義可以在這裡找到 */
template<class Rounding, class Checking>
struct interval_policies;

/* 模板類 interval; 類的定義可以在 這裡找到 */
template<class T, class Policies = typename interval_lib::default_policies<T>::type > class interval;

/* 涉及區間的算術運算符 */
template <class T, class Policies>  interval<T, Policies> operator+(const interval<T, Policies>& x);
template <class T, class Policies>  interval<T, Policies> operator-(const interval<T, Policies>& x);

template <class T, class Policies>  interval<T, Policies> operator+(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  interval<T, Policies> operator+(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  interval<T, Policies> operator+(const T& x, const interval<T, Policies>& y);

template <class T, class Policies>  interval<T, Policies> operator-(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  interval<T, Policies> operator-(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  interval<T, Policies> operator-(const T& x, const interval<T, Policies>& y);

template <class T, class Policies>  interval<T, Policies> operator*(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  interval<T, Policies> operator*(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  interval<T, Policies> operator*(const T& x, const interval<T, Policies>& y);

template <class T, class Policies>  interval<T, Policies> operator/(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  interval<T, Policies> operator/(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  interval<T, Policies> operator/(const T& r, const interval<T, Policies>& x);

/* 代數函數: sqrt, abs, square, pow, nth_root */
template <class T, class Policies>  interval<T, Policies> abs(const interval<T, Policies>& x);
template <class T, class Policies>  interval<T, Policies> sqrt(const interval<T, Policies>& x);
template <class T, class Policies>  interval<T, Policies> square(const interval<T, Policies>& x);
template <class T, class Policies>  interval<T, Policies> pow(const interval<T, Policies>& x, int y);
template <class T, class Policies>  interval<T, Policies> nth_root(const interval<T, Policies>& x, int y);

/* 超越函數: exp, log */
template <class T, class Policies>  interval<T, Policies> exp(const interval<T, Policies>& x);
template <class T, class Policies>  interval<T, Policies> log(const interval<T, Policies>& x);

/* fmod, 針對於三角函數的參數簡化 (如下) */
template <class T, class Policies>  interval<T, Policies> fmod(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  interval<T, Policies> fmod(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  interval<T, Policies> fmod(const T& x, const interval<T, Policies>& y);

/* 三角函數*/
template <class T, class Policies>  interval<T, Policies> sin(const interval<T, Policies>& x);
template <class T, class Policies>  interval<T, Policies> cos(const interval<T, Policies>& x);
template <class T, class Policies>  interval<T, Policies> tan(const interval<T, Policies>& x);
template <class T, class Policies>  interval<T, Policies> asin(const interval<T, Policies>& x);
template <class T, class Policies>  interval<T, Policies> acos(const interval<T, Policies>& x);
template <class T, class Policies>  interval<T, Policies> atan(const interval<T, Policies>& x);

/* 雙曲三角函數 */
template <class T, class Policies>  interval<T, Policies> sinh(const interval<T, Policies>& x);
template <class T, class Policies>  interval<T, Policies> cosh(const interval<T, Policies>& x);
template <class T, class Policies>  interval<T, Policies> tanh(const interval<T, Policies>& x);
template <class T, class Policies>  interval<T, Policies> asinh(const interval<T, Policies>& x);
template <class T, class Policies>  interval<T, Policies> acosh(const interval<T, Policies>& x);
template <class T, class Policies>  interval<T, Policies> atanh(const interval<T, Policies>& x);

/* min, max 外部函數 (不是 std::min/max, 如下) */
template <class T, class Policies>  interval<T, Policies> max(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  interval<T, Policies> max(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  interval<T, Policies> max(const T& x, const interval<T, Policies>& y);
template <class T, class Policies>  interval<T, Policies> min(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  interval<T, Policies> min(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  interval<T, Policies> min(const T& x, const interval<T, Policies>& y);

/* 邊界相關的區間函數 */
template <class T, class Policies>  T lower(const interval<T, Policies>& x);
template <class T, class Policies>  T upper(const interval<T, Policies>& x);
template <class T, class Policies>  T width(const interval<T, Policies>& x);
template <class T, class Policies>  T median(const interval<T, Policies>& x);
template <class T, class Policies>  T norm(const interval<T, Policies>& x);

/* 邊界相關的區間函數 */
template <class T, class Policies>  bool empty(const interval<T, Policies>& b);
template <class T, class Policies>  bool singleton(const interval<T, Policies>& x);
template <class T, class Policies>  bool equal(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  bool in(const T& r, const interval<T, Policies>& b);
template <class T, class Policies>  bool zero_in(const interval<T, Policies>& b);
template <class T, class Policies>  bool subset(const interval<T, Policies>& a, const interval<T, Policies>& b);
template <class T, class Policies>  bool proper_subset(const interval<T, Policies>& a, const interval<T, Policies>& b);
template <class T, class Policies>  bool overlap(const interval<T, Policies>& x, const interval<T, Policies>& y);

/* 設置操作的區間函數 */
template <class T, class Policies>  interval<T, Policies> intersection(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  interval<T, Policies> hull(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  interval<T, Policies> hull(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  interval<T, Policies> hull(const T& x, const interval<T, Policies>& y);
template <class T, class Policies>  interval<T, Policies> hull(const T& x, const T& y);
template <class T, class Policies>  std::pair<interval<T, Policies>, interval<T, Policies> > bisect(const interval<T, Policies>& x);

/* 區間比較運算符 */
template<class T, class Policies>  bool operator<(const interval<T, Policies>& x, const interval<T, Policies>& y);
template<class T, class Policies>  bool operator<(const interval<T, Policies>& x, const T& y);
template<class T, class Policies>  bool operator<(const T& x, const interval<T, Policies>& y);

template<class T, class Policies>  bool operator<=(const interval<T, Policies>& x, const interval<T, Policies>& y);
template<class T, class Policies>  bool operator<=(const interval<T, Policies>& x, const T& y);
template<class T, class Policies>  bool operator<=(const T& x, const interval<T, Policies>& y);

template<class T, class Policies>  bool operator>(const interval<T, Policies>& x, const interval<T, Policies>& y);
template<class T, class Policies>  bool operator>(const interval<T, Policies>& x, const T& y);
template<class T, class Policies>  bool operator>(const T& x, const interval<T, Policies>& y);

template<class T, class Policies>  bool operator>=(const interval<T, Policies>& x, const interval<T, Policies>& y);
template<class T, class Policies>  bool operator>=(const interval<T, Policies>& x, const T& y);
template<class T, class Policies>  bool operator>=(const T& x, const interval<T, Policies>& y);
template<class T, class Policies>  bool operator==(const interval<T, Policies>& x, const interval<T, Policies>& y);
template<class T, class Policies>  bool operator==(const interval<T, Policies>& x, const T& y);
template<class T, class Policies>  bool operator==(const T& x, const interval<T, Policies>& y);

template<class T, class Policies>  bool operator!=(const interval<T, Policies>& x, const interval<T, Policies>& y);
template<class T, class Policies>  bool operator!=(const interval<T, Policies>& x, const T& y);
template<class T, class Policies>  bool operator!=(const T& x, const interval<T, Policies>& y);

namespace interval_lib {

template<class T, class Policies>  interval<T, Policies> division_part1(const interval<T, Policies>& x, const interval<T, Policies& y, bool& b);
template<class T, class Policies>  interval<T, Policies> division_part2(const interval<T, Policies>& x, const interval<T, Policies& y, bool b = true);
template<class T, class Policies>  interval<T, Policies> multiplicative_inverse(const interval<T, Policies>& x);

template<class I>  I add(const typename I::base_type& x, const typename I::base_type& y);
template<class I>  I sub(const typename I::base_type& x, const typename I::base_type& y);
template<class I>  I mul(const typename I::base_type& x, const typename I::base_type& y);
template<class I>  I div(const typename I::base_type& x, const typename I::base_type& y);

} // namespace interval_lib

} // namespace numeric
} // namespace boost

模板類interval

模板類 interval 的公共接口保持在最小數量:
template <class T, class Policies = typename interval_lib::default_policies<T>::type>
class interval
{
  public:
  typedef T base_type;
  typedef Policies traits_type;

  interval();
  interval(T const &v);
  template<class T1> interval(T1 const &v);
  interval(T const &l, T const &u);
  template<class T1, class T2> interval(T1 const &l, T2 const &u);
  interval(interval<T, Policies> const &r);
  template<class Policies1> interval(interval<T, Policies1> const &r);
  template<class T1, class Policies1> interval(interval<T1, Policies1> const &r);

  interval &operator=(T const &v);
  template<class T1> interval &operator=(T1 const &v);
  interval &operator=(interval<T, Policies> const &r);
  template<class Policies1> interval &operator=(interval<T, Policies1> const &r);
  template<class T1, class Policies1> interval &operator=(interval<T1, Policies1> const &r);

  void assign(T const &l, T const &u);

  T const &lower() const;
  T const &upper() const;

  static interval empty();
  static interval whole();
  static interval hull(T const &x, T const &y);

  interval& operator+= (T const &r);
  interval& operator-= (T const &r);
  interval& operator*= (T const &r);
  interval& operator/= (T const &r);
  interval& operator+= (interval const &r);
  interval& operator-= (interval const &r);
  interval& operator*= (interval const &r);
  interval& operator/= (interval const &r);
};

構造函數創建包含它們的參數的區間. 如果有兩個參數, 第一個參數假定為左邊界,第二個參數假定為右邊界. 因此, 這些參數應當是有序的.如果 !(l <= u) 沒有得到滿足, 將會使用檢查策略創建一個空區間. 如果沒有給定任何參數, 創建的區間是一個單獨的0.

如果參數的類型與基數字類型相同, 這些參數值將直接作為區間的邊界值. 如果類型不一樣, 庫將會使用捨入策略來進行轉化(conv_downconv_up)並且創建一個包含的區間. 如果輸入參數是一個使用不同策略的區間, 輸入的區間將被檢查,為了正確的傳播它的無意義(emptiness ) (如果區間為空).

賦值運算符也有類型的情況,除了它們明顯的只帶有一個參數. 同樣有一個賦值函數assign用於直接改變區間的邊界值. 它的行為類似於帶有兩個參數的構造函數如果參數不是有序的. 沒有只帶有一個區間或者一個數字作為參數的賦值函數,在這種情況下可以使用賦值運算符。

邊界值的類型和區間的策略定義了區間所能包含的數值集合. 例如,在使用默認策略的情況下, 區間是實數值的子集. 靜態函數emptywhole 產生區間子集分別是空集和全集. 它們是靜態成員函數而不是全局函數,因為它們不能推導出返回值的類型.類似地,函數hull. empty 和 whole涉及到檢查策略,用於獲取結果區間的邊界值 .

運算和函數

下面的一些函數 ,除了 min 和 max 都針對於基本類型進行了定義,這是區間類interval僅有的要求(但是策略可以有自己的要求 ).

運算符+ - * / += -= *= /=

基本的運算符是一元的取負和二元的+ - * /. 一元取負運算符帶有一個區間參數,並返回一個區間. 二元的運算符帶有兩個區間參數或者是一個區間和一個數字並且返回一個區間. 如果一個參數是一個數字而不是一個區間,你可以預期結果是一樣的,就好像這個數字首先被轉化成一個區間。這種情況對於下面的所有的函數和運算符都是通用的.

同樣有一些賦值運算符+= -= *= /=.沒有太多需要說明: x op= y 等價於x = x op y. 如果在運算過程中拋出異常,左值不會受影響 (但是有可能在基類型的賦值過程中拋出異常).

運算符//= 將試圖產生一個空集合,如果除數為0 . 如果除數包含0 (但不僅是0), 結果將會是包含除法結果的最小區間; 所以,它的一個邊界將會是無限的, 但它可能不是整個區間 .

lower upper median width norm

lower, upper, median respectively 計算下邊界,上邊界 ,以及區間的中值((lower+upper)/2捨入到最鄰近的值 ). width 計算區間的寬度(upper-lower 上邊界朝正無窮捨入). norm 計算區間的上邊界的絕對值;它是一個數學范數 (就是它的名字)類似於實數的絕對值.

min max abs square pow nth_root division_part? multiplicative_inverse

同樣定義了函數min, maxabs. 請不要將它們與標準庫中的相混淆(也可以叫: a<b?a:b, a>b?a:b, a<0?-a:a). 這些函數兼容區間算術的初等性質(elementary property). 例如, max([a,b], [c,d]) = {max(x,y) 其中 x 屬於 [a,b] 且 y 屬於 [c,d]}.它們並沒有在名字空間std中定義,而是在名字空間boost中定義,為的是避免與其它定義衝突.

square 函數非常特別. 就像你可以從它的名字中推測的那樣, 它計算參數的平方. 提供這個函數的理由是: 當X包含0時 ,square(x) 不是x*x 而是一個子集.例如 , [-2,2]*[-2,2] = [-4,4] 但是 [-2,2]² = [0,4]; 結果是一個更小的區間. 因此, square(x)應當被使用square(x)代替x*x 因為它更加精確並且有一個小的性能提升 .

類似於square, pow 提供了一個更加高效和精確的方法來計算區間的整數冪. 請注意: 當冪指數為0,並且區間不為空, 結果是1, 即使輸入區間包含0. nth_root 計算區間的整數根 (nth_root(pow(x,k),k) 包含x 或者 abs(x) 依據 k 是奇數還是偶數).如果整數參數不是正數, nth_root 的結果是未定義的. multiplicative_inverse 計算1/x.

當用戶希望除法運算返回離散的區間時,division_part1division_part2 就很有用. 例如,包含 [2,3] / [-2,1] 的最窄的閉區間不是 [-∞,∞] 而是[-∞,-1] 和 [2,∞]的並集. 當計算的結果可以用一個單獨的區間來表示的時候 , division_part1 返回這個區間並將布爾引用設為false. 然而,如果結果需要兩個區間來表示, division_part1 返回負的部分並將布爾引用設為true; 現在調用 division_part2 應當獲取正的部分. 第二個函數可以將第一個函數返回的布爾值作為最後一個參數 .如果布爾參數沒有給定, 它的值假定為真,並且,如果除法運算沒有產生第二個區間,這個函數的行為是未定義的,.

intersect hull overlap in zero_in subset proper_subset empty singleton equal

intersect 計算兩個閉集的交集, hull 計算包含兩個參數的最小區間; 這些參數可以是數字或者是區間.如果有一個參數是一個非法的數字或者一個空的區間, 這個函數將會只使用另一個參數來計算結果區間 (如果被檢查策略允許的話).

沒有並集函數,因為如果兩個區間沒有相交,兩個區間的並集就不是一個區間,如果它們相交,函數hull計算並集。

函數overlap 測試兩個區間是否有共同的子集. in 測試一個數字是否在一個區間中; zero_in 測試0 是否在一個區間中. subset 測試第一個區間是否是第二個區間的子集, proper_subset 測試它是否是一個真子集. emptysingleton測試一個區間是否為空或者是一個單元素區間. 最後,equal測試兩個區間是否相等 .

sqrt log exp sin cos tan asin acos atan sinh cosh tanh asinh acosh atanh fmod

同樣也定義了函數sqrt, log, exp, sin, cos, tan, asin, acos, atan, sinh, cosh, tanh, asinh, acosh, atanh. 並沒有太多的需要說明;這些函數擴展傳統函數到區間之上並且滿足基本的區間運算性質. 當當輸入的區間完全在函數的處理範圍之外時,它們使用檢查策略來產生空的區間。 .

函數fmod(interval x, interval y) 期望最小邊界是正的, 並且返回區間Z滿足 0 <= z.lower() < y.upper()zx-n*y 的超集(N是一個整數). 因此, 如果兩個參數是正的單元素區間,函數 fmod(interval, interval) 將會和傳統的函數fmod(double, double)的行為一樣.

請注意fmod 並不滿足區間運算的包含性質. 例如, fmod([13,17],[7,8])的結果應當是 [0,8] (因為它必須包含 [0,3] 和 [5,8]). 但是當目的是限定一個區間為了計算一個週期函數,結果並不是真的有用.這就是函數fmod返回[5,10]的理由.

add sub mul div

這四個函數帶有兩個數字參數,並且返回一個包含的區間. 它會避免在運算之前將一個數字轉化為一個區間.

常量

一些常量隱藏在名字空間boost::numeric::interval_lib中. 它們需要由區間類型明確的模板化. 函數是 pi<I>(), pi_half<I>()pi_twice<I>()返回一個區間類型I的對象. 它們的值分別是π, π/2 和 2π.

異常拋出

區間類和圍繞這個類所定義的函數,它們本身並不拋出任何的異常,然而這並不意味著一個操作永遠都不會拋出異常。例如,讓我們考慮拷貝構造函數,就像上面的解釋那樣,缺省的拷貝構造函數由編譯器產生,所以,如果基類的拷貝構造函數不拋出異常,它就不會拋出異常.

同樣的情況適用於所有的函數,如果基類型或者兩個策略中的一個拋出異常,函數將會拋出異常。

區間支持庫

區間支持庫包含一系列可以組合使用來滿足各種基本需要的區間策略,基本的類和函數,與名字空間boost中基本的類和函數用作interval<T>的連接相對於(參數作為這個類型中隱含的第二個模板參數),這些組件屬於名字空間boost::numeric::interval_lib.

我們僅在這裡給出一些概要並且沒有為每一節製作一個單獨的網頁,因為它僅打算針對那些高級用戶,這使得我們可以擴展每一個主題並帶有一些例子.

概要

namespace boost {
namespace numeric {
namespace interval_lib {
/*內建的捨入策略以及其相應的特化 */
template <class T>  struct rounded_math;
template <>         struct rounded_math<float>;
template <>         struct rounded_math<double>;
template <>         struct rounded_math<long double>;

/* 內建的捨入構造模塊 */
template <class T>  struct rounding_control;

template <class T, class Rounding = rounding_control<T> >  struct rounded_arith_exact;
template <class T, class Rounding = rounding_control<T> >  struct rounded_arith_std;
template <class T, class Rounding = rounding_control<T> >  struct rounded_arith_opp;

template <class T, class Rounding>  struct rounded_transc_dummy;
template <class T, class Rounding = rounded_arith_exact<T> >  struct rounded_transc_exact;
template <class T, class Rounding = rounded_arith_std  <T> >  struct rounded_transc_std;
template <class T, class Rounding = rounded_arith_opp  <T> >  struct rounded_transc_opp;

template <class Rounding> struct save_state;
template <class Rounding> struct save_state_nothing;

/* 內建的檢查策略 */
template <class T> struct checking_base;
template <class T, class Checking = checking_base<T>, class Exception = exception_create_empty>   struct checking_no_empty;
template <class T, class Checking = checking_base<T> >                                            struct checking_no_nan;
template <class T, class Checking = checking_base<T>, class Exception = exception_invalid_number> struct checking_catch_nan;
template <class T> struct checking_strict;

/* 一些用於操作區間策略的元編程代碼 */
template <class Rounding, class Checking> struct policies;
template <class OldInterval, class NewRounding> struct change_rounding;
template <class OldInterval, class NewChecking> struct change_checking;
template <class OldInterval> struct unprotect;

/* 需要明確的模板化的常量*/
template<class I> I pi();
template<class I> I pi_half();
template<class I> I pi_twice();

/* 明確的區間比較函數:
 * 方式可以是 cer=certainly 或者 pos=possibly,
 * 函數 lt=less_than, gt=greater_than, le=less_than_or_equal_to, ge=greater_than_or_equal_to
 *   eq=equal_to, ne= not_equal_to */
template <class T, class Policies>  bool cerlt(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  bool cerlt(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  bool cerlt(const T& x, const interval<T, Policies>& y);

template <class T, class Policies>  bool cerle(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  bool cerle(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  bool cerle(const T& x, const interval<T, Policies>& y);

template <class T, class Policies>  bool cergt(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  bool cergt(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  bool cergt(const T& x, const interval<T, Policies>& y);

template <class T, class Policies>  bool cerge(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  bool cerge(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  bool cerge(const T& x, const interval<T, Policies>& y);

template <class T, class Policies>  bool cereq(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  bool cereq(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  bool cereq(const T& x, const interval<T, Policies>& y);

template <class T, class Policies>  bool cerne(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  bool cerne(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  bool cerne(const T& x, const interval<T, Policies>& y);

template <class T, class Policies>  bool poslt(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  bool poslt(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  bool poslt(const T& x, const interval<T, Policies>& y);

template <class T, class Policies>  bool posle(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  bool posle(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  bool posle(const T& x, const interval<T, Policies>& y);

template <class T, class Policies>  bool posgt(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  bool posgt(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  bool posgt(const T& x, const interval<T, Policies> & y);

template <class T, class Policies>  bool posge(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  bool posge(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  bool posge(const T& x, const interval<T, Policies>& y);

template <class T, class Policies>  bool poseq(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  bool poseq(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  bool poseq(const T& x, const interval<T, Policies>& y);

template <class T, class Policies>  bool posne(const interval<T, Policies>& x, const interval<T, Policies>& y);
template <class T, class Policies>  bool posne(const interval<T, Policies>& x, const T& y);
template <class T, class Policies>  bool posne(const T& x, const interval<T, Policies>& y);

/* 比較名字空間 */
namespace compare {
  namespace certain;
  namespace possible;
  namespace lexicographic;
  namespace set;
  namespace tribool;
} // namespace compare

} // namespace interval_lib
} // namespace numeric
} // namespace boost

每一個區間支持庫的組件在其專屬的頁面中有詳細的描述.

常見的缺陷和危險

檢查

最大的問題之一可能是正確的使用比較函數和運算符.首先, 函數和運算符並不試圖瞭解兩個區間是不是相同的數學對象,因此,如果比較操作是"確定的", 那麼,x != x永遠為真, 除非x是一個單元素的區間; 對於 cereqcerne也有同樣的問題

另一個使人誤解的解釋是: 你不能一直期望 [a,b] < [c,d] 等價於 !([a,b] >= [c,d]) 因為比較並不是必須的完全的. 相等和小於比較,應當被視為兩個不相關的運算符. 然而,默認的比較運算符滿足這些性質,因為無論何時 [a,b] 和 [c,d] 相交,它們將會拋出一個異常,.

區間值 和 引用

這個問題是前面那個問題的衍生問題. 庫中的所有的函數只會考慮區間的值,而不是區間的引用 .特別是你不能期望下面是相等的(除非X是一個單元素的區間): x/x 與 1, x*xsquare(x), x-x 與 0, 等等. 因此主要的問題是區間算術並不會區分相同變量的不同出現. 因此,無論何時,在盡可能的情況下:用戶必須重寫方程來消除同一個變量的多次出現, 例如 , square(x)-2*x 遠沒有 square(x-1)-1精確 .

不受保護的捨入

就像前面解釋的那樣,當基本類型是基本的浮點類型的時候,一個好的加速計算的方法是在區間算法的熱點上(hot spots)去掉保護,這種方法是安全的,並且也是區間運算的一個改進,但是請雇:任何的基本的浮點運算運算在不受保護的塊中,可能會有未定義的行為出現 (但只針對於當前線程). 並且不要忘記創建一個捨入對象就像在這個例子中解釋的那樣.

基本原理

這個庫的目的是提供一個高效且通用的方式來處理區間算術。通過使用模板化的類boost::numeric::interval,我們提供的原理的最大的論點是這個模板的格式.

提供一個類型為 double的interval類或者遵循std::complex 只允許針對於float, double, 以及 long double特化的類將會是很容易的. 我們決定不這樣做而是允許區間類interval同樣適用於用戶自定義的類型, 例如.固定精度的大浮點類型(MPFR, etc),有理數等等.

策略設計. .雖然曾經嘗試使這個類模板只有一個模板參數,實際迫使我們使用策略,這個類的行為可以由兩個策略設置,這兩個策略類被包裝成一個策略類,這是為了理好的易用性(策略類可以通過默認來選擇)和可讀性。 .

第一個策略提供了所有的需要定義在interval類型之上的針對於基本類型的數學函數,第二個策略被用來設置當運算中出現異常時的處理方式.

我們可以預見任何的這些策略的組合都將是合適的,更重要的是,我們想要使得這個庫的用戶可以重用這個類模板,與此同時,也可以選擇類的行為表現,參見這一頁提供的例子.

捨入策略. 這個庫為基本的類型 float 和 double提供了特別實現的捨入策略. 為了使得這些實現正確並且快速,這個庫需發針對捨入方式做很多的工作. 一些處理器提供直接的處理並且一些機制被提供用於加速計算. 表面上看起來為了獲取幾個CPU週期的性能提升是一件繁重而且碰運氣的事情,但實際上,依賴於特定的計算機,加速比可以很容易達到2 到 3 ,更重要的是,這些優化並不會任何主要方式上影響接口(對於我們選擇的設計,任何東西都可以被添加,通過特化或通過傳遞不同的模板參數).

Pred/succ. 在以前的版本中,提供了兩個函數 predsucc, 以及各種相關函數,比如widen. 出發點是通過一個ULP (越少越好)來擴大區間, 例如. 為了保證包含性質. 一旦產生一個T類型的區間, 我們不能夠針對於一個隨機模板參數定義一個ULP. 反過來, 捨入策略允許我們完全避免使用ULP同時使得區間更加緊湊(如果結果是一個單元素區間就沒有必要加寬這個區間).加寬這個區間也是無用的,我們決定放棄這些函數.

Specialization of std::less. 因為<運算符信賴於用戶局部所選擇的比較名字空間,所以不可能正確的特化 std::less,因此,對於所有需要使用它的算法和模板,你需要明確的提供一個這樣的類(例如, std::map).

Input/output. 這個區間庫並沒有包含輸入輸出運算符,打印一個區間的值需要很多的定制,一些人想要打印邊界值,另一些人可能想要打印中位數和區間的寬度等等,例子文件列舉了一些可能性,當用戶定義它們自己的運算符 ,例子程序可以作為一個基礎。 .

Mixed operations with integers. 當使用和復用模板代碼時,存在2x 即操作符的使用是很平常的,然而,這個庫並沒有默認提供它們,因為從int 到基本類型的轉化並不總是正確的,考慮將一個32位的整數轉化為一個單精義的浮點數,所以,這些函數被放在了一個單獨的頭文件中,如果用戶想從這些混合的運算符中獲益,用戶需要明確地包含這些頭文件,另一點,由於它們定義的方式,沒有混合的比較運算符,。

Interval-aware functions. 這個庫中所定義的函數明顯在意它們所操作的區間並且它們依據通常的區間算術定理,因此,相比於通常遇到的非區間敏感(interval-aware)的函數,它們可能會有一個不同的表現 ,例如,函數max被經典的集合擴展定義 並且結果不會一直是兩個參數中的一個 (如果區間沒有相交,那麼結果是兩個區間中的一個).

這種行為與 std::max 返回它兩個參數中的一個的引用不同. 所以,如果用戶希望返回一個引用,他應當使用std::max 因為那剛好是這個函數所做. 請注意:當區間相交時,std::max 將會拋出一個異常. 這種行為並沒有居先(predate) C++標準中所描述的,因為參數是不等價的,並且它允許在 a <= b&b == &std::max(a,b)之間有一個等價(一些特殊的情況由實現來定). 然而,它與SGI中定義的也不同,因為它並不返回第一個參數,即使任何一個參數都不比另一個大.

變更歷史以及致謝

這個庫主要由Jens Maurer先前的工作的啟發,關於它的工作的一些討論在這裡介紹. Jeremy Siek 和 Maarten Keijzer 提供了一些針對於MSVC和Sparc平台捨入的控制.

Guillaume Melquiond, Hervé Brönnimann 和 Sylvain Pion 從Jens所留下的庫開啟這項工作並添加策略設計. Guillaume 和 Sylvain 在代碼上做出了巨大的努力,尤其是可移植性和針對於大多數架構的捨入模式的調整. Guillaume 完成大部分的編碼,而 Sylvain 和 Hervé 為這個庫的編寫提供了一些有用的組件. 基於 Guillaume's的優秀的開端,Herve 重新組織以及撰寫文檔中的章節 .

這份材料部分基於NSF CAREER Grant CCR-0133599之下的國家科學基金(NSF)所提供的支持. 在文檔中所描述的任何意見, 發現和評判或建議都是作者的個人觀點,並不必然反映NSF的觀點.


Valid HTML 4.01 Transitional

Revised 2006-12-25

Copyright © 2002 Guillaume Melquiond, Sylvain Pion, Hervé Brönnimann, Polytechnic University
Copyright © 2003-2006 Guillaume Melquiond, ENS Lyon

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)