DIV CSS 佈局教程網

您现在的位置: DIV+CSS佈局教程網 >> 網頁腳本 >  >> JavaScript入門知識 >> AJAX入門 >> AJAX詳解
SICP習題試解(1.7):誤差與更穩健的判斷方式
編輯:AJAX詳解     

本期主題

本文是《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之間的相對變化來判斷收斂,可有效緩解參數過大或過小時的誤差困擾。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved