共用方式為


本文章是由機器翻譯。

數值

測試 Microsoft 雲端數值中的數學函數

Stuart Brorson

假設您需要執行數學計算。例如,假設您需要知道的 34 ° 正弦值。你是做什麼工作的?您可能轉向計算機、 電腦或一些其他智慧設備。您的設備上鍵入"sin(34)",你得到的答案往往採用 16 十進位數位的精度。但是你怎麼知道你的答案是正確的呢?

我們太習慣于從我們沒有人認為有關答案是否正確的電子玩意兒獲得數學問題的答案 !幾乎每一個人總以為我們的機器給我們正確的答案。然而,對於軟體品質工程師小集,正確性不能想當然 ; 這份工作就是獲得正確的答案。本文介紹了如何測試新的 Microsoft 雲數位數學庫中的數學函數。

最科學和工程計算使用浮點運算。IEEE 標準化在 1985 年的浮點數學的基本工作原理。標準的一個關鍵特徵是它不承認了所有的數位可以表示電腦上。雖然實數集是無限的不可數名詞,IEEE 浮點數的集是一定有限和可數,因為浮點數字的數值表示形式使用固定的數量的位數。IEEE 浮點數的建設意味著它們也是理性的所以常用號碼,如 π 並不完全正確,表示和操作使用它們,如 sin(x),並不確切。

此外,不同于用整數,IEEE 浮點數字之間的間距是本地統一的但它隨對數增加的數量規模本身。中描述了這對數方面圖 1,實數行上顯示已運作其中的 IEEE 浮點數的統一塊位置。在圖中,由垂直線條表示有效大塊的浮點數 (嵌入式實數行中)。請注意,有效的浮點數之間的距離增加了對數為 x 的規模增加。兩個連續的浮點數字之間的距離通常稱為最精密單位在去年的地方 (汽油) 中,並作為調用內建函數提供 eps(x) 許多常見的數學程式中。間距的後果是變化的少數幾個接近于 0 已添加到相對較大的數位,如 1 時沒有影響。

The Floating-Point Number Grid Depicted Schematically
圖 1 的示意圖的浮點數字網格

除了編纂浮點數字的格式,IEEE 標準提供了有關如何準確地從最基本的數學運算返回必須嚴格指導。例如,IEEE 標準指定的從四個算數運算返回 (+、-,* 和 /) 必須"最佳四捨五入,"即返回的答案必須最接近 "數學上正確"的結果。雖然這項規定最初遇到了一些阻力,現在返回 best-rounded 的結果發生在硬體,顯示它已成為如何司空見慣。更有趣的是,IEEE 浮點規範還要求平方根函數返回 best-rounded 的結果。這是有趣的因為它打開了大門的兩個問題:"如何準確地可以非理性函數計算使用 IEEE 浮點表示形式?"和"如何您應該測試函數實現的準確性嗎?"

準確函數計算

哪些因素可以計算精度的?現實是我們應該想遇到不准確之處,舍可以發生在任何演算法中的步驟。這些錯誤可能複合,儘管有時他們也可能取消。在實踐中,演算法設計器必須學會包含數值計算的固有的不准確性和住在一起。

您可以單獨計算錯誤分為兩個類別的因素:

  1. 用於執行計算的演算法的相關因素。尤其是,這意味著演算法的穩定性本身和敏感,因此,一輪關閉錯誤。貧困、 不穩定的演算法往往會返回不太準確的結果,而一個良好、 穩定的演算法將返回更準確的結果。
  2. 函數本身固有的性質和其投入的域。計算使用 (而不是無限) 有限數量的雙邊投資條約時可實現的任何函數執行準確性的理論極限。原因是舍就像計算錯誤的來源和函數本身的行為確定此錯誤是放大還是減毒作為計算所得的輸入和輸出。例如,計算附近奇異函數的值,為零或快速振盪可能不太準確在這些點比計算的函數,在相同的輸入域緩慢而異。當談到這個內在的身心健康準確性,我們談到如何"也有條件"的功能是。

因此,測試精度的函數執行涉及驗證演算法返回準確的結果,理論上可能。通過在其輸入的每個函數的空調設立了理論上的可能性的限制。要把它放另一種方式,使用浮點數計算結果,引入了兩種可能的錯誤的來源:我們可以通過使用良好,避免的錯誤穩定演算法 (因數 1),和錯誤,是難以避免,因為它們相關函數的行為在其投入 (因數 2)。

在數值分析的空調概念量化由所謂"條件數,"函數對在其投入變化的敏感性的措施。根據正在審議 (例如,投入,標量與矩陣等等數) 函數的確切性質,有大量的複雜運算式的條件數。最簡單的情況是可微函數的一個變數,如 1 / xx 2sin(x) 或任何其他您可能遇到的高中代數函數。在這種簡單例子中函數的條件數 f 由於:

Equation 1 方程 1

我們會將此作為方程 1 晚。始終,標記法作為 f'(x) 函數的導數是指。大條件數 (Kf >> 1) 指示到相對擾動的高靈敏度,而小的條件數目 (Kf < = 1) 指示的功能是對擾動相對不敏感。直覺上,你可以看到,如果函數具有奇異性 — — 即,該函數吹起來,如 1 / x 附近 x = 0 — — 衍生品將捕獲此效果,並返回大條件數。

例如,請考慮該函數種 = 1/(1-x)。此函數顯然遇難後 (即,變成無限) 在 x = 1。衍生品是 f'(x) = 1 /(1-x) 2。這插入公式 1 和消除條款給此函數的條件數:

條件數 K f (x) 轉到無窮大周圍 x = 1,意味著涉及此函數計算將敏感的進位誤差等擾動時 x 達 1.因為 吹起來的 x → 1,此行為預期。此外,條件數 Kf (x) 轉至 0 時 x 是接近于 0。這表明使用此函數的計算將無動於衷擾動時 x → 0。這是直觀的有意義,因為 趨向于 1 時一個常量值 x 比 1 小得多。

測試功能精度

那麼什麼呢數學功能看起來像一個實際測試?假設我們要測試我們的標量函數的實現 y = 種,其中 x 是輸入和 y 是返回的輸出值。鑒於一個浮點值,輸入 x,測試需要三個專案:

  1. 由下測試,該函數計算的值 y計算 = f計算 (x)
  2. "數學上真正的"結果。假定我們有 oracle 能夠告訴我們,確切、 數學上正確的答案。然後輪到該值最近的浮點值 (因此,它可以表示電腦上)。調用此值 ytrue = ftrue (x)
  3. 測試的寬容。對於一些函數,此誤差可以是 0,這意味著,ycomputed 是完全相同的數學上真正的價值,ytrue 作為。例如,浮點規範任務功能 sqrt () 返回在於給出確切的答案最接近的浮點值 (即 best-rounded)。然而,在一般情況下,我們不能指望所有職能,以其精確值 best-rounded 逼近的回報率。因此,測試公差必須納入有關多少錯誤允許在從返回的資訊。公差可能取決於該函數的詳細資訊的說明,以及輸入的確切值 x

這些成分,與我們的函數實現的準確性被視為可接受 (也就是說,通過我們測試) 如果

|y computed - y true | < tol (f ; x)

凡公差取決於兩個輸入值後 x 和函數 f 本身的行為。

話說,這個方程表示該函數通過了測試,是否返回的值不同于"真實"的值按量小於測試公差 (允許錯誤)。請注意,|y computed - y true |是絕對錯誤的計算。

通過創建大量的躺在該函數,通過下測試函數運行這些值的輸入域中輸入值執行功能測試,在此形式主義和比較函數輸出 ybest-rounded (數學上真) 值,計算 ytrue。應選擇輸入的值來覆蓋該函數的有效的輸入域的所有有關部分。

在這一點上,測試人員有兩個問題需要回答:函數的"真實"的結果是什麼?又是一個合理的容差嗎?

回答第一個問題,所要做的最簡單的事情是要使用"無限精度"數學套裝軟體創建用於測試的輸入/輸出對。此套裝程式不會使用 32 位或 64 位浮點數計算值。相反,它使用的數值表示形式 — — 或更好,一種符號表示 — — 的一個數位,可運載能力計算任意大的數,通過計算速度而計算的位數。幾個商用數學套裝軟體實現無限精度數學。此外,許多無限精度數學庫可以插入到共同的語言。在現代的速度使用無限精度數學的能力是最近的創新,並使這種類型的測試方便。這些資源的任何足以創建用於測試函數的浮點實現所謂的"金值"對。

放在一起 — — 獲取測試公差

一旦我們有金色的價值觀,我們需要回答的其他問題:什麼是合理的測試容忍?獲取正確的測試公差是關鍵的元件的測試。如果公差是不切實際地小,功能從未將傳遞及其檢測、 即使最佳演算法用於計算它。另一方面,如果測試容忍太大,這意味著允許的誤差是大於它需要,該函數會通過測試,即使該演算法有故障。

先前定義的條件數是確定可接受錯誤允許在功能測試的關鍵。可以重新排列的條件數的運算式來讀取:

Equation 2 方程 2

我們會將此作為方程 2 晚。如果我們確定 ∆x 作為一個浮點數和下一步之間的距離,此運算式告訴我們多少輸出的 將跳隨著我們從一個浮點數 x 它的鄰居, x + ∆x。傳統上,電腦數位領域花費的 ∆x 函數 eps(x),任何兩個連續的浮點數字之間的間距。請注意,因為網格間距為非常數 (見圖 1), eps(x) 是一個函數的 x。(如前面所提到,一個浮點數和其最近的鄰居之間的距離也與有關無鉛汽油 — — 由最低有效位代表的規模。)

接下來,我們要求我們的測試中的輸出錯誤 y計算 -y為 true,則將低於一些多跳的。也就是說,我們問這個問題,在 C 是一個常量:

憑直覺,此運算式捕獲以下想法:如果 x 在浮點網格上,在輸出中的變化使得一步應不大於方程 2。準確的函數將通過僅條件數,從派生並沒有更多的金額更改它的輸出。因此,輸出計算期間發生的擾動應小於造成邁出一步浮點網格上的變化。該常量 C 是"蒙混因素"。很明顯,作為 C 的增加,允許的公差與它會增加。我們因此可以作為允許功能錯誤解釋此常數,在理論上的最低。在實際測試中, C 採用 1 和 10,我們將解釋為允許錯誤,表示在 ULPs 之間的整數值。

最後,使用條件數的定義,我們可以重新排列的方程公開測試寬容的方式:

|y計算 -ytrue | ≤ C | f'(x) | eps(x) = 公差

這是我們所需的測試 — — 它是必須滿足的準確執行的函數的運算式 進行任何輸入 x。換句話說,這是用來驗證標量數學函數的運算式。請注意此運算式應舉行為所有有效的輸入值 true x

解決最後一個問題是,"什麼是正確的值的 C ,在測試中使用?"因為我們解釋 C 的無鉛汽油,允許的錯誤數為 C 是訂單 1 的整數。我們設置 C 入手初始 C 值 (通常為 10) 和運行測試。如果測試通過,減少 C 1 和運行測試再測試。重複此過程,降低 C 值之前,則測試失敗。然後選擇的值 C ,最後允許要傳遞 (但始終保持人體迴圈來保證合理) 的測試。這一進程的目標是關閉 (同時仍然允許要通過測試的函數) 通過盡可能多的大門所以你可以放心,盡可能嚴格地測試函數。乖函數通常需要C 之間 1 和 3,但更複雜的函數的值可能需要較大 C 傳遞的值。我們發現需要很少的函數實現 C > 10 來傳遞,當我們找到需要的函數和 C > 10,它往往信號一次優的實現。

從一次軟體測試的角度 C 確定函數測試 (和測試通過),我們知道任何後續的測試失敗是因為東西在函數中執行已改變 — — 可能惡化的 (例如,回歸已經發生)。當然,權衡演算法設計中可能要求它是值得給予一些可寬延時間上 C 如果回歸很小 (例如,速度與準確性的權衡比較)。同樣,經過改進的演算法,這是值得,看看 C 可以進一步收緊。在任何情況下,軟體測試的一個作業將成為管理測試公差所開發軟體的其餘部分。

黃金的價值判斷和超越

在我們前面討論過的測試方法,我們使用預計算的輸入/輸出對散佈在整個輸入域下測試功能。我們稱這種類型的測試黃金價值測試,意味著無限精度測試 oracle 提供了已知的是高度精確的金色輸入/輸出對。對可以存儲在一個檔中,並讀入測試程式,它在執行時。作為黑框的方法來測試功能的準確性,這種做法很好工作。但是,其他類型的函數測試還提供驗證函數的行為的重要途徑。其他測試包括:

  • 特殊值測試:許多函數返回已知、 精確理論值的某些輸入,如 cos(0) = > 1, sin(π) => 0gamma(1/2) = √π,為例子。在特殊值測試中,已知固定的投入美聯儲向下測試,函數和函數返回到已知的結果進行比較。當然,如 π 無理數不會準確地在浮點網格上撒謊,因為浮點相近的對這些數位,必須測試和一個非零值,用於正弦和測試公差 (如前面計算) 用於驗證計算結果。
  • 標識測試:許多函數服從對某個已知的域,則所有輸入的身份。例如, (x) 偕 ^2 + cos (x) ^2 = = 1 所有輸入 x。另一個是 arcsin(x) = =-i 日誌 (我 * x + sqrt (1-x 2))。標識測試和特殊值測試之間的區別是標識測試是真正對任意輸入的而特別值測試只是如此為某一特定的輸入值。因此,標識測試驗證函數之間的關係。

你必須小心身份測試。一方面,一些恒等式是不好的條件。例如,中間結果可能會增長,即使最終的結果適度規模會很大。在這種情況下,在計算中的中間步驟期間發生的小的允許錯誤會導致雜散測試失敗。此外,許多功能 (例如,反三角函數) 是在複雜平面多值。身份的左邊和右邊雙方返回正確的值,躺在複平面中的不同黎曼工作表時,盲目使用標識測試可能會導致虛假測試失敗。測試人員必須認真起草身份測試,以避免這兩個問題。

  • 逆測試:這涉及到計算函陣列成及其逆和驗證結果相同的輸入的測試。例如,對於積極的 x 我們可以測試 log(exp(x)) = x。你可能認為這是一個特殊的身份測試、 案也的確如此。但是,因為這麼多的函數有逆 — — 和數學一致性要求一個函陣列成及其逆返回原始輸入 — — 我們使用一個不同的測試類別來驗證,其功能和其逆的行為相一致的方式。同樣也適用于標識測試 (如空調或返回躺在黎曼的不同工作表) 的解釋適用于逆測試。
  • 系列求和測試:幾乎所有的先驗函數對一些輸入域承認一系列擴張。在系列求和測試中,我們比較到測試中顯式總和系列所返回的值根據測試函數所返回的值。你可能認為作為一種標識測試系列求和。然而,走進創建良好系列求和測試的考慮因素是類似跨職能 (例如,穩定和趨同標準)。因此,我們認為這種類型的測試是在概念上不同的標識測試的。
  • 分式展開:此外可能對使用分式擴大已知域求的某些功能。當這種擴大存在時,它可能會聚比一系列筆要快得多。因此,對於某些函數,系列求和測試可能會替換分式擴張。
  • 測試 (也稱為基於模型的測試) 構造的值:在構造的值測試中,您創建測試本身內功能簡單、 可驗證正確執行。這種類型的測試一定不會適用于標量數學函數。然而,數學不錯包並不限於解析函數集。例如,考慮如地板、 天花板、 國防部、 向量的串聯運算子函數等。每個函數可能通過編寫實現使用電腦的基礎語言建構函式的代碼進行測試。例如,地板、 天花板和可能使用強制轉換運算子,將浮點值轉換為一個整數,然後將轉換結果建模功能的各種數位印章回浮點數 (帶一些簡單的數學執行以模仿正在審議函數的確切行為)。這種類型的一個好處是測試的模型執行通常微不足道,因此可通過檢查核實。
  • 錯誤偵測:這些測試確保不正確輸入返回清理錯誤使得程式師能夠清楚、 快速地瞭解問題得到妥善處理。例如,當在實數,工作 sqrt(x) 應返回有用的錯誤 (或NaN) 如果 x < 0.已知一些輸入的錯誤導致電腦崩潰,如果他們不處理不當,並測試員的工作是要確保這不會發生。

這些類型的測試的好處是正確性的它們提供使用僅本身的數學函數交叉檢查。因為這些方法使用數學自我一致性測試的基礎,他們"已知良好",並不依賴于使用協力廠商軟體的數值計算。

驗證方法

欣賞的條件數公差優勢的一種方法是檢查用於驗證其輸入域中有奇異的標量數學函數的公差。例如,常見三角函數 tan 和棉被是奇異在無限的實數線沿線點。如果固定、 恒公差被用於精度驗證,這些函數將失敗,他們為輸入值接近奇異的測試或測試公差一定會有這麼大的測試不會有效。與條件數的公差,我們可以驗證的標量函數的內一小撮 ULPs 函數的整個輸入域上。示圖 2 是傳遞我們發現在資格的職能在 Microsoft 雲數位產品分發過程的無鉛汽油值的示例。也就是說,這些都無鉛汽油值相應的功能,通過其測試。

圖 2 傳遞無鉛汽油的值

功能 輸入的域 傳遞無鉛汽油 評論
Atan2 實數 1 兩個輸入、 四象限反正切值
嬰兒床 實數 3  
Coth 複雜的數位 3  
Cuberoot 實數 2  
Ellipe X 這種真實數位,0 ≤ x ≤ 1 4 橢圓積分 E
Ellipk X 這種真實數位,0 ≤ x ≤ 1 6 橢圓積分 K
Expm1 實數 3 -1 Exp(x)
伽馬 實數 3  
Log 實數 3  
Log 複雜的數位 3  
Log1p 實數 1 Log(1+x)
Log1p 複雜的數位 1 Log(1+x)
防擴散安全倡議 實數 6 防擴散安全倡議功能 — — 衍生的伽瑪函數
Sqrt 實數 0 IEEE 規範要求此以"最佳四捨五入"
實數 1  
雙曲正切 實數 4  
雙曲正切 複雜的數位 4  

從示例中得出結論, 圖 2 是特殊的功能實現使用精確到內少量的 ULPs 的演算法。最糟糕的情況提出了在圖 2 有錯誤少於 6 ULPs,它對應于 log10(2^6) = 1.8 錯誤號的順序最低位數位中的小數位數。為雙精度浮點,這對應于 1.3323e 相對誤差-015。

先進的測試

審查,嚴格的測試方法已成功應用在 Microsoft 雲數值型數學包中使用的演算法的驗證。使用該函數的條件數從派生的測試公差使我們能夠識別並正確不正確的函數的實現中,甚至當錯誤發生只在最後幾位數位的函數的返回。固定的測試公差不能提供也不會引起雜散失敗 (例如,近函數奇異) 的嚴格測試。我們測試所涉及的大部分使用的預計算使用無限精度數學套裝軟體的金色值輸入/輸出值,然後存儲在測試時讀取的檔。除了使用金值,我們也在使用各種不同的數學身份驗證我們的函數的行為我們函數實現上執行交叉檢查。

我們相信微軟雲計算數位的使用者可以使用其數學與統計庫函數的陣列並有信心使用先進的軟體測試的做法職能已被審核徹底。

有關詳細資訊,我們鼓勵您閱讀的浮點數學,"什麼每電腦科學家應該知道有關浮點算術,"這是可用在大衛 · 戈德堡的經典描述 bit.ly/vBhP9m 和其他網站。

Stuart Brorson 是微軟在麻塞諸塞州劍橋的 Microsoft 書呆子中心 他加入微軟公司收購互動式超級,開發軟體允許使用者運行數學時和矩陣運算在並行超級電腦上。為了好玩,Brorson 喜歡駭客電子和玩周圍波士頓愛爾蘭提琴。

Ben Moskowitz 是專門從事測試基於數學的專案在 Microsoft 微軟。他已經貢獻的雲數位和規劃求解基金會、 優化包和 2011 年榮獲 Visual Studio 燈塔獎的平臺版本。 下班,他花時間和他的妻子,照顧他們居住在城市的山羊。

Alan Edelman  教授數學和電腦科學與人工智慧實驗室在麻省劍橋麻省理工學院的一名成員 愛德曼教授贏得了眾多獎項數值分析、 平行計算和隨機矩陣理論的工作。他是互動式的超級計算的創始人、 是朱麗亞專案的創辦人之一、 學會了很多從 Velvel 格漢和大量參加了浮點數學問題數值數學聯合會.

由於以下的技術專家對本文的審閱: Paul Ringseth