Lua 5.1中(a^x)%101映射唯一性校验函数异常问题咨询

问题描述 #

原代码用于校验值a通过公式(a^x) % 101对1到100的映射是否唯一，但在Lua 5.1中测试a=2时出现错误：计算2^65 % 101得到56，与2^12 % 101的结果重复，导致函数返回false。但实际2^65 % 101的正确值应为57，且2是模101的原根，本应生成1到100的所有唯一值，函数应返回true。

问题原因 #

这确实是Lua 5.1的数值类型特性导致的问题。Lua 5.1使用双精度浮点数存储所有数值，而双精度浮点数只能精确表示2^53以内的整数。2^65远超出这个范围，直接计算2^65会丢失精度，导致后续取模结果错误。

解决方法 #

不能直接计算大指数的幂再取模，要利用模运算的性质优化递推计算：(a * b) % m = [(a % m) * (b % m)] % m，每一步都对结果取模，避免数值过大触发浮点数精度丢失。

修改后的代码如下：

local function f(a)
    local found = {}
    local bijective = true
    local current = 1  -- 初始为a^0 % 101，用于递推a^1
    for x = 1, 100 do
        current = (current * a) % 101  -- 递推计算a^x % 101，避免大数值运算
        if found[current] then
            bijective = false
            break
        else
            found[current] = x
        end
    end
    return bijective
end

代码说明 #

• 用current变量保存上一步的模幂结果，每次循环通过current * a % 101得到当前a^x % 101的结果，所有计算值都保持在0-100之间，完全不会触发浮点数精度问题。
• 测试a=2时，该函数会正确返回true，符合预期。

内容的提问来源于stack exchange，提问作者Nifim