電腦代數與符號計算

精確有理數算術(exact rational arithmetic)

在計算機上把 1/3 加 1/6,你得到 0.5,一個恰好算得乾淨的數——但把 1/3 加 1/7,你得到 0.47619047...,一個已經有點錯的小數。精確有理數算術拒絕捨入:它把每個數都保存為分數,一個分子配一個分母,並把 1/3 + 1/7 算成恰好的 10/21。答案是一對整數,完美地等於真值,看不到任何小數。

一個有理數以兩個任意精度整數 p/q 保存,化為最簡且 q 為正。其算術就是你學過的分數規則,精確地執行:a/b + c/d = (a d + b c) / (b d),且 a/b 乘 c/d = (a c) / (b d),之後再把結果的分子分母同除以它們的最大公因數(用歐幾里得演算法算出)以約分。因為整數可以任意大,從不丟失任何資訊:一連串分數的加、乘、除,到最後產生唯一精確正確的分數。這是精確線性代數核心的數系,其中無分數版或有理數版的高斯消去法以完全精確的答案解 A x = b。

精確有理數在正確性必須密不透風時至關重要——驗證恆等式、精確解線性方程組,或任何災難性抵消會毀掉浮點數的場合。誠實的代價有兩面,而且是電腦代數的核心:分子與分母會隨著計算成長,有時呈爆炸性(表達式膨脹的教科書案例),而不斷的最大公因數約分也並非免費。所以精確有理數算術精準卻不可擴展;對大型系統而言,數值方法儘管帶著捨入誤差,通常仍是唯一務實的選擇。

精確計算 1/3 + 1/7。通分到 21:1/3 = 7/21,1/7 = 3/21,和為 10/21。10 與 21 的最大公因數為 1,所以 10/21 已是最簡分數。浮點數答案 0.47619047619047616 很接近卻不相等——它與 10/21 的差,正是日後抵消會放大的東西。

用最大公因數約分到最簡;結果恰好就是真正的分數。

把分數保持在最簡並非可有可無的整理——略過最大公因數約分,分子分母會膨脹得快得多,把一個可管理的計算變成不可管理的。即使已約分,精確有理數在一段漫長計算中仍可能嚴重膨脹。

又稱
exact fraction arithmeticrational number arithmetic精確分數運算有理數算術