时间戳

首页 > 解决方案 > floor(a, b) 和 a // b 的结果不同

lua - floor(a, b) 和 a // b 的结果不同

问题描述

--this function isn't relevant, but I included it for completeness
function gcd(a, b)
    local temp
    while b > 0 do
        temp = a % b
        a = b
        b = temp
    end
    return a
end

function extendedgcd(a, b)
    if b == 0 then
        return 1, 0, a
    end
    local x, y, d = extendedgcd(b, a % b)
    --this assertion fails for a = 568784642688024576, b = 5
    --left side gives 113756928537604915 (correct), while right side gives 113756928537604912 (wrong)
    assert(a // b == math.floor(a / b))
    --so here, I can't use math.floor
    return y, x - a // b * y, d
end

function modularinverse(e, mod)
    if gcd(e, mod) > 1 then
        return nil
    end
    local x, _, _ = extendedgcd(e, mod)
    if x < 0 then
        x = x % mod
    end
    if x * e % mod ~= 1 then
        error(string.format("Modular inverse (%d) doesn't produce 1 (e = %d, mod = %d)", x, e, mod))
    end
    return x
end

modularinverse(5, 568784642688024576)

对于a = 5和b = 568784642688024576，中的断言extendedgcd失败。我不是 FP 精度方面的专家，但两者之间的差异为 3，所以我认为这里不存在舍入/精度错误。但我可能错了。

通常我只会使用//，但我不能，因为目标平台没有运行 Lua 5.3，这是添加操作员的时候。

我错过了什么？我如何使它与 一起工作floor，或者有其他方法吗？

另外值得注意的是：当我用 Python 重写它来摆弄（使用math.floorand //）时，也发生了同样的问题。

标签： luafloating-accuracy

解决方案

更准确的答案：

正如纸和铅笔将显示的那样： 568784642688024576 / 5 = 113756928537604915.02

该商作为双精度数的最准确二进制表示是：

0100001101111001010000100101010100101110010000111001001100110011

其中，十进制是：（1.13756928537604912E17注意 ...912 结尾）

现在，如果将二进制表示减一，如下所示：

0100001101111001010000100101010100101110010000111001001100110010

然后它等于：（1.13756928537604896E17最后...896！）

如果要将原始二进制数加一，如下所示：

0100001101111001010000100101010100101110010000111001001100110100

然后等于：（1.13756928537604928E17最后...928！）

因此，这些数字有精确的双精度二进制表示：

113756928537604896

113756928537604912（最接近实际商数）

113756928537604928

以上可以使用在线转换器进行验证，例如这里。

所以教训是：

整数除法将给出正确答案（即商的整数部分）。地板浮点除法依赖于数字的二进制表示，这并不总是精确的。

在此答案的范围之外，但需要阅读才能真正理解其中的任何内容：

上述二进制数如何表示它们的十进制等值？

  • 简短回答：IEEE-754。如果您打算研究该标准文件，我祝您好运和喝咖啡。

/和之间的算法区别是什么//？

  • 换句话说，为什么//上面得到了我们想要的答案？

推荐阅读