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

Question

--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 的差异，所以我认为这里没有 rounding/precision 错误。但我可能错了。

通常我只会使用 //，但我不能，因为目标平台不是运行 Lua 5.3，这是添加运算符的时间。

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

另请注意：当我将 Python 重写为 fiddle（使用 math.floor 和 //）时，同样的问题发生了。

Answer 1

Lua的数字是双精度的吧？一旦超过 2^52，整数表示中的差距就会越来越大。

568784642688024576 大于 2^58，因此您可能运行陷入其中的一些空白。如果是这样的话，那么它看起来 // 正确地解释了差距，而 floor 可能没有。

如果您的代码处理接近 2^64 的整数值很重要，那么可能值得寻找一个插件或允许您使用 64 位整数的东西。或者，如果您需要处理更大的数字，可能会有一个库或类似的东西来处理非常大的数字。

Answer 2

更准确的答案：

正如纸笔所示： 568784642688024576 / 5 = 113756928537604915.02

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

0100001101111001010000100101010100101110010000111001001100110011

十进制形式是：1.13756928537604912E17（注意 ...912 结尾）

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

0100001101111001010000100101010100101110010000111001001100110010

那么它等于：1.13756928537604896E17（...最后是 896！）

如果要将原始二进制数加一，像这样：

0100001101111001010000100101010100101110010000111001001100110100

那么等于：1.13756928537604928E17（...最后是 928！）

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

113756928537604896

113756928537604912（最接近实际商数）

113756928537604928

以上可以使用在线转换器验证，例如here.

所以教训是：

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

超出此答案的范围，但需要阅读真正理解其中的任何内容：

以上二进制数如何表示它们的十进制数？

简答：IEEE-754。如果您打算研究该标准文档，我祝您好运并多喝咖啡。

/和//的算法有什么区别？

也就是说，为什么//会得到我们上面想要的答案呢？

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

Different results with floor(a, b) and a // b

lua

floating-accuracy