lua - 2^65 模 101 错误答案

Question

此代码使用公式 (a^x) % 101

检查值 a 是否唯一映射到值 1 到 100

local function f(a)
    found = {}
    bijective = true

    for x = 1, 100 do
        value = (a^x) % 101
        if found[value] then
            bijective = false
            break
        else
            found[value] = x
        end
    end

    return bijective
end

但是并没有产生预期的结果。它将 2^65 % 101 映射到 56，这与 2^12 % 101 产生的值匹配，我得到一个错误的结果，但是 的正确值2^65 % 101 是 57，实际上 2 应该产生所有唯一值，从而产生真实结果。

上面描述的错误是在 Lua 5.1 上特有的，这只是 Lua 的数字输入的怪癖吗？有没有办法让这个功能在5.1中正常运行？

Answer 1

The error described above is specifically on Lua 5.1, is this just a quirk of Lua's number typing? Is there a way to make this function work correctly in 5.1?

首先，这不是 Lua 的数字输入问题，因为 2^65 是 2 的(相当小的)幂，可以用 double 精确表示，因为它使用指数尾数表示法。尾数可以简单地设置为全零(前导 1 是隐式的)并且指数必须设置为 65(+ 偏移量)。

我在不同的 Lua 版本上试过这个，PUC Lua 5.1 和 5.2 以及 LuaJIT 都有问题； Lua 5.3(可能还有更高版本)都可以。有趣的是，使用 math.fmod(2^65, 101) 在旧的 Lua 版本上返回正确的结果但是 2^65 % 101 没有(它返回 0 代替)。

这让我很吃惊，所以我查阅了 Lua 5.1 的源代码。这是 math.fmod 的实现:

#include <math.h>

...

static int math_fmod (lua_State *L) {
  lua_pushnumber(L, fmod(luaL_checknumber(L, 1), luaL_checknumber(L, 2)));
  return 1;
}

这也是唯一使用 math.h 中的 fmod 的地方。另一方面，% 运算符是按照引用手册中的文档实现的:

#define luai_nummod(a,b)    ((a) - floor((a)/(b))*(b)) 

在 src/luaconf.h 中。您可以简单地将其重新定义为 fmod(a,b) 来解决您的问题。事实上，Lua 5.4 做了类似的事情，甚至在其源代码中提供了详尽的解释!

/*
** modulo: defined as 'a - floor(a/b)*b'; the direct computation
** using this definition has several problems with rounding errors,
** so it is better to use 'fmod'. 'fmod' gives the result of
** 'a - trunc(a/b)*b', and therefore must be corrected when
** 'trunc(a/b) ~= floor(a/b)'. That happens when the division has a
** non-integer negative result: non-integer result is equivalent to
** a non-zero remainder 'm'; negative result is equivalent to 'a' and
** 'b' with different signs, or 'm' and 'b' with different signs
** (as the result 'm' of 'fmod' has the same sign of 'a').
*/
#if !defined(luai_nummod)
#define luai_nummod(L,a,b,m)  \
  { (void)L; (m) = l_mathop(fmod)(a,b); \
    if (((m) > 0) ? (b) < 0 : ((m) < 0 && (b) > 0)) (m) += (b); }
#endif

---

Is there a way to make this function work correctly in 5.1?

是的:最简单的方法是使用 fmod。这可能适用于这些特定数字，因为由于基数为 2 且指数适度较小，它们仍然适合 double ，但它在一般情况下不起作用。更好的方法是利用模块化算法来保持中间结果较小，永远不要存储明显大于 101^2 的数字，因为 (a * b) % c == (a % c) * (b % c).

local function f(a)
    found = {}
    bijective = true

    local value = 1
    for _ = 1, 100 do
        value = (value * a) % 101 -- a^x % 101
        if found[value] then
            bijective = false
            break
        else
            found[value] = x
        end
    end

    return bijective
end