使用 floor(a, b) 和 a // b 产生不同的结果

--这个函数与主题无关,但是我为了完整性而包含它
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)
    --当 a = 568784642688024576, b = 5 时,这个断言会失败
    --左边给出113756928537604915(正确),而右边给出113756928537604912(错误)
    assert(a // b == math.floor(a / b))
    --所以,在这里,我不能使用 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("模逆元 (%d) 不能产生 1(e = %d,mod = %d)", x, e, mod))
    end
    return x
end

modularinverse(5, 568784642688024576)

对于 a = 5b = 568784642688024576extendedgcd 函数中的断言会失败。我不是浮点精度的专家,但是两者之间有3的差别,因此我不认为这里存在四舍五入/精度错误。但我可能错了。

通常我会使用 //,但我不能这样做,因为目标平台不运行 Lua 5.3,这是运算符被添加的版本。

我缺少什么?如何使用 floor,或者还有其他方法吗?

还要注意的是:当我用 Python 重新编写时(使用 math.floor//),遇到了同样的问题。

点赞
用户9851554
用户9851554

Lua 的数字是双精度的,对吧?一旦超过 2^52,整数表示中就会出现越来越大的间隙。

568784642688024576 比 2^58 还要大,所以你可能会遇到一些间隙。如果是这种情况的话,那么 // 应该可以正确处理间隙,而 floor 可能不行。

如果你的代码需要处理接近 2^64 的整数值,那么可能值得寻找一个插件或者类似的东西,让你可以使用 64 位整数。或者如果你需要处理更大的数,可能会有一些用于处理非常大的数字的库或者其他东西。

2018-07-22 02:18:43
用户4403144
用户4403144

一个更精确的答案:

用纸和笔可以看出: 568784642688024576 / 5 = 113756928537604915.02

这个商作为双精度数的最精确的二进制表示是:

0100001101111001010000100101010100101110010000111001001100110011

它的十进制表示是:1.13756928537604912E17 (注意结尾是...912)

现在,如果你把这个二进制表示减去1,像这样:

0100001101111001010000100101010100101110010000111001001100110010

那么它就等于:1.13756928537604896E17 (结尾是...896!)

如果你把原始二进制数字增加1,像这样:

0100001101111001010000100101010100101110010000111001001100110100

那么它就等于:1.13756928537604928E17(结尾是...928!)

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

113756928537604896

113756928537604912 (最接近实际商)

113756928537604928

可以使用在线转换器(如 这里)验证上述内容。

教训是:

整数除法将给出正确的答案(即商的整数部分)。向下取整浮点数除法依赖于数字的二进制表示,这并不总是精确的。

超出此答案的范围,但需要阅读才能真正理解其中任何一个问题:

上述二进制数如何表示它们的十进制等价物?

  • 简短的回答:IEEE-754。如果你打算研究这个标准文档,祝你好运和大量咖啡。

///之间的算法差异是什么?

  • 换句话说,为什么//会给我们上面想要的答案?
2018-07-22 14:45:03