如何證明我的Double.toString算法對所有值都是正確的？

我正在對Java的慢速Double.toString算法進行優化。我已經成功地重寫了Float.toString（並且速度提高了400％以上）。測試Float.toString的算法很簡單，因爲我可以在煮沸雞蛋的時間內迭代拋出所有可能的值（從Integer.MIN_VALUE到Integer.MAX_VALUE）。如何證明我的Double.toString算法對所有值都是正確的？

但是，以同樣的方式測試Double.toString以獲得準確性將需要我從Long.MIN_VALUE迭代到Long.MAX_VALUE。我可以在所有線程上開始這個測試，並在我的餘生中運行它，我敢打賭它不會完成。

要清楚的是，當我測試這個算法時，我只是把我的結果字符串和調用String.equals對java.lang.Double.toString（double d）的結果。如果它們匹配，我將轉到下一個值。

我對算法的改進主要包括消除不必要的精度。當計算Double.toString時，它使用特殊類型的BigInteger類來執行此操作。但是，我發現通過調整微不足道的位，我仍然可以獲得相同的結果，並且性能顯着提高。

我認爲我可以將所有值修改爲不超過128位（修剪位用一個偏移量替換）而不會失敗我的測試，但是如何在不迭代每個值的情況下證明這一點？

我猜我在問什麼：原始算法的創建者如何知道他們的算法是正確的，而沒有測試每個可能的輸入？

來源

2017-03-03 HesNotTheStig

當你說'我打賭它不會完成'時，你是對的，因爲浮點數表示實數，0到1之間實際上有一個**無限**數量。爲了更精確地在任何兩個實數之間存在**無限**其他實數的數量。 –

這樣做的另一個結果是浮點數永遠不能正確表示所有實數，只是適合它的那些。只有**非重要**位，如果存儲在浮點中的當前值只有在0之後的那麼幾個數字，那麼它們適合在那裏並且可以以二進制方式表示。 0。1例如不能以二進制方式呈現，因爲它是1/10。 –

出於實用目的，在Java中有2^64個可能的輸入到Double.toString。其中一些解析爲相同的值（NaN）。一半是消極的。有負值和正值無窮，負值和正值爲零。少數可以使用稍微修改的Long.toString算法來解決。然而，大多數是通過找到值b和s以使得（b/s）* 10^decExp =雙倍值來計算的。根據需要估算和調整小數指數。 – HesNotTheStig

我不是......完全確定他們做到了。

你可以看一下對Double#toString書面the OpenJDK 8和OpenJDK 9測試，並沒有得到多少...滿意從中：

/* 
* Copyright (c) 2009, Oracle and/or its affiliates. All rights reserved. 
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 
* 
* This code is free software; you can redistribute it and/or modify it 
* under the terms of the GNU General Public License version 2 only, as 
* published by the Free Software Foundation. 
* 
* This code is distributed in the hope that it will be useful, but WITHOUT 
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 
* version 2 for more details (a copy is included in the LICENSE file that 
* accompanied this code). 
* 
* You should have received a copy of the GNU General Public License version 
* 2 along with this work; if not, write to the Free Software Foundation, 
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 
* 
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 
* or visit www.oracle.com if you need additional information or have any 
* questions. 
*/ 

/* 
* @test 
* @bug 4428022 
* @summary Tests for Double.toString 
* @author Andrew Haley <[email protected]> 
*/ 

public class ToString { 

    public static void main(String args[]) { 
     if (!Double.toString(0.001).equals("0.001")) 
      throw new RuntimeException("Double.toString(0.001) is not \"0.001\""); 
     if (!Double.toString(0.002).equals("0.002")) 
      throw new RuntimeException("Double.toString(0.001) is not \"0.002\""); 
    } 
}

實際上，他們所正在做的是測試案件;如果toString方法正確識別"0.001"和"0.002"令人滿意地返回。

這可能有一個事實，即浮點數是在處理這些類型的分數，這對於任何試圖將一個雙重轉換爲以那種方式串一個體面的嚴峻考驗出了名的不好做;他們只是簡單地創建了一個測試來涵蓋基礎知識。

從那個你會;我鼓勵你在想要測試的東西上考慮一下。由此看來，只有邊緣情況纔會被捕獲;你可能希望通過你自己的優化來擴展它。

雖然......將這些測試（以更好的方式，介意你）添加到你自己的套件中也不會是最糟糕的想法。自09年以來他們一直沒有變化。

來源

2017-03-03 21:40:08 Makoto

哇......這就是他們所測試的全部？我可以向你保證會有更多的測試用例比這個更有效。例如，我知道算法中有（至少）4個或5個主要子情況完全不同地處理計算。如何對所有這些情況進行測試？這不是特別有信心，知道它有多少測試。 – HesNotTheStig

呃，不，我不會想象你在看到這個字面上是* it *來測試'Double＃toString'後會有很高的信心。回答您的後續問題：直接測試這些組件。考慮每個組件設計要處理的每個案例，並對這些案例進行測試。 – Makoto

如何證明我的Double.toString算法對所有值都是正確的？

回答

相關問題