boost.png (6897 bytes) Rational Numbers

目錄

  1. 類 rational 的摘要
  2. 原理
  3. 背景
  4. 對整數類型的 要求
  5. 接口
  6. 性能
  7. 異常
  8. 內部表示
  9. 設計說明
  10. 參考
  11. 歷史和 鳴謝

類 rational 的摘要

#include <boost/rational.hpp>

namespace boost {

template <typename I> I gcd(I n, I m);
template <typename I> I lcm(I n, I m);

class bad_rational;

template<typename I> class rational {
typedef implementation-defined bool_type;

public:
typedef I int_type;

// 構造函數
rational(); // 零
rational(I n); // 等於 n/1
rational(I n, I d); // 普通情形 (n/d)

// 普通的複製構造函數和賦值構造函數

// 賦值自 I
rational& operator=(I n);

// 就地賦值
rational& assign(I n, I d);

// 表示法
I numerator() const;
I denominator() const;

// 除了以下操作符,還有其它 "明顯的" 派生操作符 - 請見 operators.hpp

// 算術操作符
rational& operator+= (const rational& r);
rational& operator-= (const rational& r);
rational& operator*= (const rational& r);
rational& operator/= (const rational& r);

// 與整數的算術運算
rational& operator+= (I i);
rational& operator-= (I i);
rational& operator*= (I i);
rational& operator/= (I i);

// 遞增與遞減
const rational& operator++();
const rational& operator--();

// 取非操作符
bool operator!() const;

// 布爾類型轉換
operator bool_type() const;

// 比較操作符
bool operator< (const rational& r) const;
bool operator== (const rational& r) const;

// 與整數進行比較
bool operator< (I i) const;
bool operator> (I i) const;
bool operator== (I i) const;
};

// 單參操作符
template <typename I> rational<I> operator+ (const rational<I>& r);
template <typename I> rational<I> operator- (const rational<I>& r);

// 整數(或可轉換為整數的)類型與 rational 間的反序 - 和 / 操作符
template <typename I, typename II> inline rational<I> operator- (II i, const rational<I>& r);
template <typename I, typename II> inline rational<I> operator/ (II i, const rational<I>& r);

// 絕對值
template <typename I> rational<I> abs (const rational<I>& r);

// 輸入與輸出
template <typename I> std::istream& operator>> (std::istream& is, rational<I>& r);
template <typename I> std::ostream& operator<< (std::ostream& os, const rational<I>& r);

// 類型轉換
template <typename T, typename I> T rational_cast (const rational<I>& r);

原理

數字具有多種不同的形式。最基本的形式是自然數(非負的"純粹的"數字)、整數和實數。這些類型大致相當於C++的內建類型 unsigned int, int, 和 float (以及它們的不同大小的變體)。

C++ 標準庫擴展了數字類型的範圍,提供了 complex 複數類型。

本庫則提供另一種數字類型,rational 有理數。

rational 類實際上是以模板來實現的,在某種意義上類似於標準的 complex 類。

背景

有理數的數學概念就是通常所說的分數 - 即一個可以表示為兩個整數之比的數。這個概念與實數是截然不同的,後者具有多得多的可能值(例如,2的平方根就不能表示為一個分數)。

計算機不能完全精確地表示數學上的概念 - 總是要進行一些折衷。機器的整數具有值範圍的限制(通常為32位),而機器的近似實數則具有精度上的限制。折衷具有不同的動機 - 機器整數可以進行精確的計算,但具有範圍的限制,而機器實數則允許更大的取值範圍,但要以犧牲精度為代價。

有理數類提供了另一種折衷。有理數的計算是精確的,但它們的有效值範圍也是有限制的。精確地說,有理數不過是分子與分母(它們會被規範 化,不具有公因子)的比,其範圍由底層的整數類型所限定。如果這些值超出了它們的邊界,就會發生溢出,結果將會是未定義的。

有理數類是一個模板,允許程序員控制其溢出行為。如果存在一個無限精度的整數類型,那麼基於它的有理數將不會溢出,並且將提供所有情形 下的精確計算。

對整數類型的要求

有理數類型帶有單個模板類型參數 I. 它是有理數類型的 底層整數類型。C++實現所提供的任何內建整數類型均可用作 I 的值。也可以使用用戶自定義的類型,但是用戶必須清楚,rational 類的性能特徵是高度依賴於其底層整數類型的性能特徵的(通常會是複雜的情形 - 更多的說明請見 性 能 一節)。註:如果 boost 庫以後提供了一個無限精度的整數類型,則該類型也可以用作 rational 類的底層整數類型。

一個用戶自定義類型要用作有理數類型的底層整數類型,就必須符合以下概念。

此外,I 必須是一個 類似於整數 的類型,即對於類型 I 的任意兩個值 n 和 m,以下表達式必須有效,並具有 "預期" 的語義。

I 必須具有 零值單元值。並可以 分別用 I(0)I(1) 生成。註:這 並不意味著 I 必須可以從整數隱式轉換 - 有顯式轉換構造函數就可以了。

I 可以是一個無符號類型。這種情況下,所生成的 rational 類型也將是無符號的。減法的溢出行為將不會導致負的結果,其行為是不可預知的。

std::numeric_limits<I> 的特化必須存在(並且在需要使用 boost::rational<I> 之前可見)。它的 is_specialized 靜態數據成員的值必須為 true 且它的 its is_signed 靜態數據成員的值必須是正確的。

接口

工具函數

以下兩個工具函數可能被提供,它們可以用於 boost::rational<> 類模板 可使用的任意類型

gcd(n, m) n 和 m 的最大公約數
lcm(n, m) n 和 m 的最小公倍數

這些函數現在將前轉調用在 Boost.Math 庫 中的對應函數。它們是否出現由 BOOST_CONTROL_RATIONAL_HAS_GCD 預處理器常數在編譯編譯期進行控制。

構造函數

有理數可以構造自零個、一個、或兩個整數;缺省構造函數表示零,從單個整數轉換則該整數代表分子而分母為1,從兩個整數構造則兩個整數 依次代表分子 和分母。整型參數的類型應該是 rational 的整數類型,或者可以隱式轉換為該類型。(當然,對於兩參數構造函數,各個轉換是獨立求值的) 。各個組件將被保存為規範化的形式。

這意味著以下語句是有效的:

 I n, d;
rational<I> zero;
rational<I> r1(n);
rational<I> r2(n, d);

單參數的構造函數並沒有被聲明為 explicit, 因此可以從底層整數類型隱式轉換為 rational 類型。

算術操作

定義了所有針對 rational 類的標準算術操作。包括有:
 + +=
- -=
* *=
/ /=
++ -- (前綴與後綴形式)
== !=
< >
<= >=

輸入與輸出

本庫提供了輸入與輸出操作符 <<>>. 有理數的外部表示方式為兩個以斜槓(/)分隔的整數。輸入時,形式必須精確為一個整數,後跟一個沒有空白符間 隔的斜槓,再後跟第二個整數(也是沒有空白符間隔)。整數的外部表示方式則由底層整數類型定義。

就地賦值

對於任意 rational<I> r, r.assign(n, m) 提供了 r = rational<I>(n, m); 的一個快速等價實現,不需要構造一個臨時變量。對於基於機器的整數類型的有理數類型,這可能是不必要的;但對於基於無限精度整數的 有理數類型,它就可以提高效率。

轉換

該類具有一個到未確定布爾類型(類似於成員指針)的轉換操作符。如果一個有理數表示為零,則該操作符將它轉換為 false, 反之則轉換為 true. 這個轉換允許 rational 被用作操作符 ?: 的第一個參數;或者是用作操作符 &&|| 的參數,而不會違反短路求值;或者是用作 do, if, while, 或 for 語句的條件;或者是用作 if, while, 或 for 語句的條件聲明。該類型被自然地使用,有關它的任何名字都保持私有,以防止任何不恰當的、當作非布爾類型的使用,如數字或指針類型,又或者是用作 switch 的條件。

rational 類型沒有其它的 隱式轉換。不過有一個顯式的類型轉換函數,rational_cast<T>(r). 它可以這樣用:

 rational r(22,7);
double nearly_pi = boost::rational_cast<double>(r);

如果源 rational 的分子或分母不能安全地轉型為相應的浮點類型,或者分子與分母的商不能正確求得(以 相應的浮點類型為目標),則 rational_cast<T> 函數的行為是未定義的。

實質上,所有被要求的轉換都有其存在的價值,且所有操作都是行為"敏感的"。如果沒有這樣的約束,那麼用戶自定義的獨立的轉換操作更為 合適。

實現說明:

rational_cast 函數的真正實現是

 template <typename Float, typename Int>
Float rational_cast(const rational<Int>& src)
{
return static_cast<Float>(src.numerator()) / src.denominator();
}
但是,不應依賴於這一實現來編寫程序,尤其是該實現現在已被廢除。(它要求在類型 FloatInt 之間的混合模式除法,與 整數類型的 要求 相反)

分子與分母

最後,提供了通過兩個成員函數 numerator()denominator() 訪問有理數的內部表示的方法。

這些函數允許用戶編碼實現任意所需的額外功能。尤其是在某些情形下,上述 rational_cast 操作可能是不恰當的 - 特別是在 rational類型是基於無限精度的整數類型時。這種情況下,一個特別編寫的、用戶自定義的到浮點類型的轉換將更為恰當。

性能

rational 類設計中的一個假設是,底層的整數類型應該行為"類似"於內建的整數類型。前面 整數類型的要求 一節中已經描述了這一假設的行為方面的要求。不過,除了行為上的假設外,還有對性能上的假設。

我們並沒有試圖對 rational 類提供操作性能的具體保證。雖然這樣的保證有可能提供(類似於許多標準庫的類所提供的性能保證),不過這樣的保證對於 rational 類的用戶而言並沒有重大意義。所以,本節將提供關於 rational 類的性能特徵的一個廣泛的討論。

以下列出在 <boost/rational.hpp> 中定義的基礎操作以及對它們的性能特性的非正式描述。請注意,這些描述是基於當前的實現的,有可能會被修改。

注意,這裡假設了 IntType 上的操作具有"正常的"性能特性 - 具體講,即最昂貴的操作是乘法、除法和取模,而加法和減法則代價明顯要低一些。還假設了構造(包括從整數 0 和 1 進行構造,以及複製構造)和賦值也相對低代價,儘管我們也在減少不必要的構造和複製上做了一些努力。我們還假設了比較(尤其是與零比較)是很低代價的。

不符合以上假設的整數類型不太適合作為 rational 類的底層整數類型。這樣將會導致性能急劇降低。

異常

有理數不能以零作為分母。(本庫不支持表示無限大或 NaN)。如果一個 rational 導致生成了零分母,則會拋出異常 boost::bad_rational (std::domain_error 的子類)。這只會發生在用戶試圖顯式地以零分母構造一個 rational,或者用零值去除一個 rational 時。

此外,如果對底層整數類型的操作會產生異常,異常將會被傳遞到對 rational 類的操作以外。不要做任意特定的假設 - 唯一安全的方法是假設任何可能由整數類型拋出的異常都會由任意的 rational 操作拋出。具體講,rational 的構造函數可能在規範化中以拋出來自於底層整數類型的異常作為結果。該規則的唯一例外是,rational 的析構函數只會在底層整數類型的析構函數拋出異常時(通常不會發生)拋出異常。

內部表示

註:這些信息僅供參考。不應該依賴於這些實現細節來編寫程序。

在內部,有理數被保存為一對 (分子, 分母) 的整數(其類型由 rational 類型的模板參數所指定)。有理數總是以完全規範化的形式(即 gcd(numerator,denominator) = 1, 且分母為正)來保存。

設計說明

最小實現

rational 類是遵循最小性原則來設計的。只提供了數字類型的最低要求的操作,以及以 numerator() 和 denominator() 成員函數訪問底層數據的方法。基於這些構件,就可以實現所需要的任意其它功能。

這個最小性原則的例外是提供了輸入/輸出操作符,以及 rational_cast. 前者通常不會引起爭論。但是,在很多情形下,rational_cast 並不是將 rational 轉換為浮點值的最佳方法(告別是有用戶自定義類型的時候)。這時候,可以實現一個用戶自定義的轉換函數。這個操作不需要命名為 rational_cast, 所以 rational_cast 函數沒有提供進行特化/重載的必要措施。

有限範圍的整數類型

rational 類被設計為可以與無限精度的整數類型一起使用。對於這樣的整數類型,rational 就總是精確的,不會出現精度損失、上溢出和下溢出等問題。

不幸的是,C++ 標準並沒有提供這樣的類(到目前為止,boost 也沒有)。因此,多數情況下 rational 類會與有限精度的整數類型合用,如內建的 int 類型。

當與有限精度的整數類型合用時,rational 類會遇到和浮點數類型同樣的很多精度問題。雖然這些精度問題好像不會影響到對 rational 類的一般的使用,但是用戶還是應該知道有這些問題。

以下通過一個簡單的示例來看一下這個與有限精度整數相關的問題,假設 C++ int 類型是一個32位的有符號表示。這種情形下,最小的正的 rational<int> 是 1/0x7FFFFFFF. 換句話說,rational<int> 表示法在零值附近的"粒度"大約是 4.66e-10. 在該表示法的範圍的另一端,最大的正的 rational<int> 是 0x7FFFFFFF/1, 而次大的 rational<int> 是 0x7FFFFFFE/1. 因此,在該表示的範圍的另一端,粒度為 1. 這種與大小相關的粒度也正是浮點表示法所具有的。不過,在使用 rational 類時好像"感覺上"沒那麼自然罷了。

用戶在使用基於有限精度整數類型的 rational 時,應該知道以上問題,並依此來編碼。

轉換自浮點數

本庫不提供從浮點數到有理數的轉換。曾經有不少這類轉換的要求被提出,但是通過在 boost list 上的廣泛討論,得到的結論是這個問題沒有 "最佳的解決方案"。本庫的用戶沒有理由不可以根據它們的特定要求來編寫它們自己的轉換函數,最終的結果是,沒有一個算法可以被作為 "標準"。

從浮點數進行轉換的關鍵問題是,如何處理浮點數操作中的精度損失。為了提供一個具體的例子,考慮以下代碼:

 // 這兩個值實際上可以是來自於用戶輸入,或來自於某些測量儀表
double x = 1.0;
double y = 3.0;

double z = x/y;

rational<I> r = rational_from_double(z);

根本問題是,rational r 應該具有什麼樣的精度?一個天真答案是 r 應該等於 1/3. 但是,它忽略了很多問題。

首先,z 並不精確等於 1/3. 因為浮點數表示法的限制,在任何常見的 double 類型的表示中,1/3 不可能在被精確地表示。那麼 r 可能是 z 的實際值的一個(精確)表示嗎?用戶會對 r 的值是 33333333333333331/100000000000000000 感到高興嗎?

在進一步討論以上問題前,我們需要考慮原始值 x 和 y 的精度。如果它們來自於某個模擬測量設備,那麼它們就不可能是無限精確的。在這種情況下,像上面這樣的 rational 表示就提供了比其它表示更好的精度。

以上這些意味著我們應該尋找某種 "最接近的簡單分數" 的形式。這樣的算法確實存在。不過,並不是所有應用程序都想這樣做。在其它情況下,轉換為 rational 的重點在於提供一個精確的表示,以防止在一系列計算中的精度損失。這時就要求一個完整的精度表示,而不管這個分數看起來是多麼 "不自然" 了。

由於這些相互矛盾的要求,很顯然不存在單個的解決方案可以滿足所有用戶。而且,相關的算法都比較複雜和特殊,最好的實現都應該對應用程 序的需求有好的理解。所有這些因素使得這樣一個函數不適合在一個通用庫中提供。

絕對值

起初,看起來用 abs(IntType) 來實現 abs(rational<IntType>) 是很合理的。不過,這樣做會帶來幾個問題。

第一個問題是,當 IntType 是一個位於用戶的名字空間中的用戶自定義類型時,為了查找 abs(IntType) 的適當實現,需要用到 Koenig 查找。目前還不是所有編譯器都能支持 Koenig 查找。對於這樣的編譯器,笨拙的處理方法是,需要 rational 類的用戶的配合才可以正常工作。

第二個問題更為嚴重,對於非標準的內建類型類型(如 long long__int64 這樣的64位類型),不能保證編譯器廠家提供了操作這些類型的內建 abs() 函數。這是一個實現質量的問題,不過在實際情況下,廠家對 long long 這樣的類型的支持還很彆扭。

這些問題的一個結果是,不應該依據 abs(IntType) 來實現 abs(rational<IntType>). 我們使用了一個簡單的內聯函數來實現 abs():

 template <typename IntType>
inline rational<IntType> abs(const rational<IntType>& r)
{
if (r.numerator() >= IntType(0))
return r;

return rational<IntType>(-r.numerator(), r.denominator());
}

相同的參數意味著,在需要 IntType 的絕對值的地方,計算將被內聯執行。

參考

歷史與鳴謝

In December, 1999, I implemented the initial version of the rational number class, and submitted it to the boost.org mailing list. Some discussion of the implementation took place on the mailing list. In particular, Andrew D. Jewell pointed out the importance of ensuring that the risk of overflow was minimised, and provided overflow-free implementations of most of the basic operations. The name rational_cast was suggested by Kevlin Henney. Ed Brey provided invaluable comments - not least in pointing out some fairly stupid typing errors in the original code!

David Abrahams contributed helpful feedback on the documentation.

A long discussion of the merits of providing a conversion from floating point to rational took place on the boost list in November 2000. Key contributors included Reggie Seagraves, Lutz Kettner and Daniel Frey (although most of the boost list seemed to get involved at one point or another!). Even though the end result was a decision not to implement anything, the discussion was very valuable in understanding the issues.

Stephen Silver contributed useful experience on using the rational class with a user-defined integer type.

Nickolay Mladenov provided the current implementation of operator+= and operator-=.

Discussion of the issues surrounding Koenig lookup and std::swap took place on the boost list in January 2001.

Daryle Walker provided a Boolean conversion operator, so that a rational can be used in the same Boolean contexts as the built-in numeric types, in December 2005.

Revised November 5, 2006

c Copyright Paul Moore 1999-2001; c Daryle Walker 2005. Permission to copy, use, modify, sell and distribute this document is granted provided this copyright notice appears in all copies. This document is provided "as is" without express or implied warranty, and with no claim as to its suitability for any purpose.