java - 如何证明我的 Double.toString 算法对于所有值都是正确的？

Question

关闭。这个问题是 opinion-based 。目前不接受答案。

---

想要改进这个问题吗？更新问题，以便 editing this post 可以用事实和引文来回答它。 .

已关闭 6 年前。

Improve this question

我正在致力于优化 Java 出了名的慢的 Double.toString 算法。我已经成功重写了 Float.toString(速度提高了 400% 以上)。测试 Float.toString 的算法很容易，因为我可以在煮鸡蛋所需的时间内迭代抛出所有可能的值(从 Integer.MIN_VALUE 到 Integer.MAX_VALUE)。

但是，以相同的方式测试 Double.toString 的准确性将需要我从 Long.MIN_VALUE 迭代到 Long.MAX_VALUE。我可以在所有线程上开始这个测试，并在我的余生中运行它，我敢打赌它不会完成。

需要明确的是，当我测试这个算法时，我只是简单地获取结果字符串并根据 java.lang.Double.toString(double d) 的结果调用 String.equals 。如果它们匹配，我就会转到下一个值。

我对算法的改进主要涉及消除不必要的精度。当计算 Double.toString 时，它使用一种特殊的 BigInteger 类来执行此操作。但是，我发现通过修剪无关紧要的位，我仍然可以获得相同的结果，并且性能显着提高。

我认为我可以将所有值修剪到不超过 128 位(用偏移量替换修剪后的位)而不会导致测试失败，但是如何在不迭代每个值的情况下证明这一点？

我想我要问的是:原始算法的创建者如何在不测试每个可能的输入的情况下绝对确定他们的算法是正确的？

Answer 1

我……完全确定他们做到了。

您可以查看the OpenJDK 8和 OpenJDK 9为 Double#toString 编写的测试，并没有得到太多......满意:

/*
 * 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 <aph@redhat.com>
 */

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" 并令人满意地返回。

这可能与 float 在处理这类分数方面出了名的糟糕有关，这对于任何试图将 double 转换为字符串的东西来说都是一个不错的严格测试以这种方式；很可能他们只是创建了一个测试来涵盖基础知识。

从中获取你想要的；我鼓励您仔细思考一下您还想测试什么。由此看来，似乎只捕获了边缘情况；您可能想通过自己的优化来扩展它。

尽管...将这些测试(请注意，以更好的方式)添加到您自己的套件中也不是最糟糕的主意。自 09 年以来，它们一直没有改变。