本文是《Structure and Interpretation of Computer Programs》(電腦程序的構造和解釋)第1.7題的試解。第一部分屬於理解題,探討good-enough?這個判斷函式在參數過大或過小時都會產生的誤差問題;第二部分則是編程,給出一個更穩健的實作。
函式good-enough?在參數值較大或較小時,都會產生誤差問題。
其一,正常的計算本就會產生誤差。比如1/3是無限循環小數,有無數個有效位,而在電腦或任何機械式計算中,分配給每個數字的儲存空間都是有限的,因此捨入誤差在所難免。在一般計算中,由於電腦提供了相當多的儲存位,低位次上需捨入的量級往往極小,多數情況下不影響結果。
其二,當運算結果很大時,小數點左邊位數很多,捨入與非捨入的分界位置就可能很高,誤差也就跟著變大。設想一個最簡單的模型:共有10個有效位,那麼1.234567890123會被捨入為1.234567890,捨入誤差為0.000000000123;但同樣有效位的1234567890123則會被捨入為1234567890000,捨入誤差高達123。也就是說,所有1234567890xxx在儲存後只能得到相同結果。因此在good-enough?的定義中,當參數很大時,自動的捨入誤差已經相當大,絕對誤差很大的數也可能被捨入為相同值,從而誤判為good-enough。
其三,當參數很小時同樣會出問題,只是此時低位的捨入誤差絕對值很小。問題在於:在一個固定的絕對誤差標準(例如本題的 < 0.001)下,如果參數本身的量級夠小,這個絕對誤差所允許的相對誤差就可能大到驚人。例如good-enough? 0.00001 0.0000000001會通過測試,而比準確值大了10倍的0.0001也一樣能通過——因為0.0001 × 0.0001 與 0.0000000001 的差同樣小於0.001。與第二種情況不同,這裡的判斷嚴格符合程式邏輯,並非自動捨入所致,但結果卻毫無意義。更棘手的是,無論我們把誤差標準定得多小,總存在足夠小的參數讓這種絕對誤差標準失去意義。
由此可見:首先,在誤差相關的計算中應盡量避免過大的運算數。相較於比較(square guess)與x,改為比較guess與(/ x guess)含義相近,但後者的運算數量級遠小於前者。其次,絕對誤差在許多情況下是有問題的,改用相對誤差控制顯然能解決第三種情況,也能在某些時候降低運算數的量級、改善第二種情況。
以下以「比較相鄰兩次猜測值的相對變化」來取代原本以絕對差值的判斷,讓good-enough?更為穩健:
(define (average x y)
(/ (+ x y) 2))
(define (improve guess x)
(average guess (/ x guess)))
(define (good-enough? oldguess guess)
(< (abs (/ (- guess oldguess) guess)) 0.001))
(define (sqrt-iter oldguess guess x)
(if (good-enough? oldguess guess)
guess
(sqrt-iter guess (improve guess x) x)))
(define (sqrt x)
(sqrt-iter 0.1 1.0 x))
> (sqrt 2) 1.4142135623746899 > (sqrt 9) 3.000000001396984
相較於原版只比較guess平方與x的絕對差,這裡改用guess與舊guess之間的相對變化來判斷收斂,可有效緩解參數過大或過小時的誤差困擾。