代码之家 › 专栏 › 技术社区 › Sarvadi

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

floating-accuracy lua

Sarvadi · 技术社区 · 7 年前

--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.floor 和 // )中。

2 回复 | 直到 7 年前

brianolive 7 年前

更准确的答案是:

如纸和铅笔所示: 568784642688024576 / 5 = 113756928537604915.02

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

0100001101111001010000100101010100101110010000111001001100110011

小数形式为: 1.13756928537604912E17 (注意…912结尾)

现在,如果将二进制表示法减少一,如下所示:

0100001101111001010000100101010100101110010000111001001100110010

那么它等于: 1.13756928537604896E17 (…最后是896!)

如果你愿意增加原始二进制数乘以1,如下所示:

0100001101111001010000100101010100101110010000111001001100110100

那么等于: 1.13756928537604928E17 (…最后是928!)

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

113756928537604896

113756928537604912 (最接近实际商)

113756928537604928

可以使用联机转换器验证上述内容,例如 here .

所以教训是:

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

超出了本答案的范围,但需要阅读 真正地 理解以下任何一点:

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

简短回答:IEEE-754如果你打算学习标准文件,我祝你好运,多喝点咖啡。

算法的区别是什么 / 和 // ?

换句话说,为什么 // 给我们上面想要的答案?

-1

AStarks 7 年前

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

568784642688024576大于2^58,因此您可能会遇到其中一些间隙如果是这样,那么看起来//正确地解释了间隙,而floor可能没有。

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