任意精度與標準形式

拒絕捨入的數字

前一篇指南畫出了精確符號計算與近似數值計算之間的界線：數值的世界活在一個有限的浮點網格上，那裡 0.1 沒有精確的二進位形式，每一次運算都付出一點相對捨入誤差；符號的世界則堅持給出精確的答案。但精確需要一個基礎。如果一套電腦代數系統要宣稱某個答案精確到最後一位，它就不能把數字塞進一個 64 位元的盒子裡。它需要能隨真相所需而長大的數字。

任意精度算術就是答案。系統不把整數放進固定寬度，而是把一個整數存成一串機器字組——需要多少就用多少。整數 2^1000 大約有 302 個十進位數字；電腦代數系統握有其中的每一位，而不是一個捨入後的近似。把這樣的數字做加、乘、除，用的正是你手算時學過的那套小學演算法，只是改在一塊塊數字上進行，所以成本會隨數字的大小而增長，而不是固定在一次機器運算。

精確分數，不准捨入

大整數是基本構件；精確有理數算術則是建在其上的東西。一個有理數被存成一對任意精度整數，一個分子與一個分母，每一次運算都讓這一對保持精確。所以 1/3 就是這一對 (1, 3)——而不是數值世界只能將就的那個浮點幽靈 0.3333333333333333。把 1/3 + 1/6 加起來，你會剛好得到 1/2，浮點數則會在最後一位留下一抹淡淡的誤差污痕。

這裡有一個隱藏的代價，而它教給我們整個學科的核心張力。為了在每一步之後把分數保持在最簡形式，系統必須把分子與分母都除以它們的最大公因數，這正是你會在下一篇指南裡細看的 GCD 計算（對整數而言就是普通的歐幾里得演算法）。略過這個約分，一長串加法就會產生分子與分母膨脹到上千位的分數，即使最終答案是像 2/3 這麼整潔的東西。精確是用不斷增長的儲存空間換來的——這是糾纏整個層級的表達式膨脹的第一個悄然徵兆。

兩個表達式何時相同？

精確的數字解決了問題的一半。更難的一半是：符號答案是表達式，而同一個值可以披上千百種偽裝。(x + 1)^2 跟 x^2 + 2x + 1 是同一個東西嗎？當然是——但對電腦來說，一個是「和的平方」，另一個是「三項之和」；它們在記憶體裡的樹長得毫不相像。sin(x)^2 + cos(x)^2 等於 1 嗎？是的，但前提是系統知道一個三角恆等式。「這兩個表達式相等嗎？」這個最基本的問題，原來坐落在電腦代數的核心。

優雅的脫身之道是標準形式：一套大家講好的、用來書寫某一族相等表達式中每一個成員的唯一寫法。如果系統把每個多項式都改寫成依次數遞減、同類項合併的項之和——於是 (x + 1)^2 變成 x^2 + 2x + 1，而 x^2 + 2x + 1 原地不動——那麼兩個多項式相等恰好當且僅當它們的標準形式逐字相同。判斷相等就塌縮成一次簡單的比對。符號化簡這整門手藝，很大程度上就是把表達式拖進標準形式的手藝。

expression           canonical polynomial form
-----------           -------------------------
(x + 1)^2          -> x^2 + 2 x + 1
x^2 + 2 x + 1      -> x^2 + 2 x + 1      (already canonical)
(x + 1)(x - 1)     -> x^2 - 1

equal?  compare canonical forms term by term:
   x^2 + 2 x + 1   ==   x^2 + 2 x + 1     ->  YES, identical
   x^2 + 2 x + 1   ==   x^2 - 1           ->  NO, differ in two terms

標準形式讓判斷相等變成逐字比對——前提是兩邊都被改寫成同一套標準寫法。

為什麼完美的標準形式不可能存在

這裡有一個誠實而令人謙卑、卻很少有人告訴初學者的真相：對於足夠豐富的表達式，根本不可能存在標準形式。多項式很乖巧，但一旦你允許指數、對數、絕對值，以及常數 pi 自由地混在一起，一個著名的結果（Richardson 定理）證明了：判斷這樣一個表達式是否恆等於零，是不可判定的——沒有任何演算法能在有限時間內永遠正確回答。所以那個萬用的「化簡成標準形式」按鈕的夢想，在數學上是無法企及的，而不只是還沒被實作出來。

這就是為什麼每一套電腦代數系統都做了務實的妥協。對於那些可被證明存在標準形式的族——整數、有理數、多項式、有理函數——它就帶著標準形式；對於更狂野的一切，它則退而求其次，依靠一套正規形式與改寫規則的工具箱。正規形式保證任何真正為零的東西都會被回報為零（所以你絕不會得到一個假的「非零」），但它有時可能認不出兩個相等的東西其實相等。清楚你手上實際擁有的是哪一種保證，正是「信任一個 `simplify` 結果」與「被它悄悄誤導」之間的差別。

把它串起來：一個答案如何保持精確

在一個小小的計算裡，看這兩根支柱如何合作。假設你請系統把分數 1/2、1/3、1/6 加起來，並確認結果是 1。在幕後，任意精度整數承載分子與分母而不捨入，以 GCD 為基礎的約分讓每個中間分數保持在最簡形式，而標準形式讓最後的 6/6 被認出是整數 1，而不是被留成一個分數。沒有任何一步做近似；精確是從頭到尾貫通的。

把每個輸入精確地存起來：1/2、1/3、1/6 變成一對對的任意精度整數——看不到 0.5、0.333...、0.166...。
在共同分母上相加：3/6 + 2/6 + 1/6 = 6/6，所有算術都在精確整數上進行。
用 GCD 約分：gcd(6, 6) = 6，於是 6/6 塌縮成 1/1。
套用標準形式：分母為 1 的有理數寫成樸素的整數 1，於是與 1 是否相等，現在只是一次微不足道的逐字比對。

從這裡有兩條線索延伸到這個層級的其餘部分。中間那個約分步驟就是 GCD，下一篇指南會把它從整數拓寬到整個多項式，再用 Groebner 基拓寬到多項式構成的方程組。而每當你看到一個分數在約分前「膨脹」，你就看見了表達式膨脹的一絲端倪——精確中間結果無情的增長，它比任何巧妙的技巧都更能決定符號計算能走到哪裡、不能走到哪裡。精確是一份美好的保證；它的帳單以儲存與時間的形式到來。