棘手的双精度

阅读其他语言: English Español 한국어 Português

Repost icon

本文是对我朋友Maksim Pelevin所写的原文章的翻译。 如果你习惯阅读俄语,你可能会在他的博客中找到更多有趣的文章。

你已经知道这个:

double 数据类型不是很精确

让我们通过解决一个CodeWars上的问题来加深这一理解。

问题描述

在 CodeWars 上描述的任务如下:

你的任务是建造一座由 n 个立方体堆叠而成的建筑。 底部的立方体体积为 n^3, 上面的立方体体积为 (n-1)^3, 以此类推,直到顶部,体积为 1^3

给定建筑的总体积 m,你能找到需要建造的立方体数量 n 吗? 即 n^3 + (n-1)^3 + … + 1^3 = m,如果这样的 n 存在,则返回该整数,否则返回 -1

简单解决方案

使用循环的最直接解决方案可能是这样的:

public static long findNb(long m) {
    long n = 0, totalVolume = 0;
    while (totalVolume < m) {
        totalVolume += ++n * n * n;
    }
    return totalVolume == m ? n : -1;
}

数学解法

大学时我学过数列及其求和方法, 因此我尝试提供一个数学解法。

我不再记得那些公式,但幸运的是, Wolfram Alpha 在这里可以帮助我们。 为了得到公式,我们运行以下查询:n^3, n = 1 到 k


结果显示:

让我们将 m 替换为等式的左边,然后应用平方根性质 并两边同时乘以二。简化后得到:

编写代码

根据上述方程,以下是用Java编写的解法:

public static long findNb(long m) {
    double res = Math.sqrt(m);
    double d = 1 + 8 * res;
    double n = (Math.sqrt(d) - 1) / 2;
    return n - Math.floor(n) == 0 ? (long) n : -1;
}

结果

事实证明,此代码对于部分测试数据返回了错误结果。 这种不一致性在传递例如 1646842954019151682L 作为输入时可见。

在Java中计算平方根时,可能无法获得完全准确的结果。让我们看看:

System.out.println(String.format("%.30f", Math.sqrt(1646842954019151682L)));
// output 1283293791.000000000000000000000000000000
// correct 1283293791.00000000038962239473657673134031176401122912...

显然,输出与正确答案不同。到此为止!

结论

技术上最正确且可能最快的解决方案并不总是最佳选择。 对于熟练的开发者来说这可能不足为奇,但对于编程新手来说,他们可能会为此类错误困惑一段时间。

如果你想知道如何修复数学解法中的问题,一种方法是使用 BigDecimal 。这段代码通过了所有测试:

public static long findNb(long m) {
    MathContext mc = new MathContext(64);
    BigDecimal res = BigDecimal.valueOf(m).sqrt(mc);
    BigDecimal d = res.multiply(BigDecimal.valueOf(8)).add(BigDecimal.ONE);
    BigDecimal n = d.sqrt(mc).subtract(BigDecimal.ONE).divide(BigDecimal.valueOf(2));
    return Objects.equals(n, n.setScale(0, RoundingMode.FLOOR)) ? n.longValue() : -1;
}

… 还有一个小彩蛋:你能猜出下面哪个是 true ,哪个是 false 吗?

(1646842954019151681L == 1646842954019151682D)
(1646842954019151681L == (long) 1646842954019151682D)
all posts ->