☰

随机数的问题

tag-icon • tag-icon tikz-pgf luatex
随机数的问题

下面我将要描述的问题目前还不是问题，但会在 TeX Live 2019 发布并且 LuaTeX 升级到 1.09 时出现。MikTeX 用户可能已经遇到过这个问题。它也会影响 Mac OS X 用户，因为他们的 C 标准库的随机数生成器与 glibc 的随机数生成器不同。

graphdrawing当我排版TikZ 手册中的一个示例时，它似乎在 LuaTeX 版本 1.07（TeX Live 2018）和 1.09（TeX Live 2019）之间镜像。为什么会发生这种情况？

\documentclass{article}
\usepackage{tikz}
\usetikzlibrary{decorations.pathmorphing,graphs,graphdrawing}
\usegdlibrary{force}
\begin{document}
\tikz [spring electrical layout, node distance=1.3cm,
       every edge/.style={
         decoration={coil, aspect=-.5, post length=1mm,
                     segment length=1mm, pre length=2mm},
         decorate, draw}]
{
  \foreach \i in {1,...,6}
    \node (node \i) [fill=blue!50, text=white, circle] {\i};

  \draw (node 1) edge (node 2)
        (node 2) edge (node 3)
                 edge (node 4)
        (node 3) edge (node 4)
                 edge (node 5)
                 edge (node 6);
}
\end{document}

左边是LuaTeX 1.07，右边是LuaTeX 1.09：

 

答案1

随机数的问题

您遇到的问题是由于与 LuaTeX 捆绑在一起的 Lua 版本升级所致。LuaTeX 1.07 使用 Lua 5.2，而 LuaTeX 1.09 使用 Lua 5.3。这有一些特殊的含义。

基于力的绘图算法首先以随机配置设置顶点。然后系统退火找到节点的最佳配置。为了避免陷入局部最小值或鞍点，每次迭代都会添加小的随机力。

您可能在上一段中注意到，“随机”一词出现了几次。这意味着该算法对随机数的选择非常敏感。然而，在版本 5.2 和 5.3 之间，Lua 更改了其默认随机数生成器 (RNG)。虽然Lua 5.2使用 C 标准库rand()功能，Lua 5.3使用 POSIXrandom()函数。因此，即使使用相同的种子，您也会得到完全不同的随机数。我相信这个问题只局限于 POSIX 兼容平台，如 Linux 或 Mac OS X。

$ lua5.2 -e "math.randomseed(42); print(math.random())"
0.32996420763897
$ lua5.3 -e "math.randomseed(42); print(math.random())"
0.32996420748532

这并不意味着你的图表会完全不同，因为分配随机数保持不变（均匀分布），只有它们的序列不同。这也是为什么图形仍然看起来如此相似并且只是看起来像镜像。

幸运的是，这个问题完全局限于弹簧电气布局，因为没有其他图形绘制算法使用随机数。

缓解措施

rand()纯 Lua 中glibc 的实现

另一个选择是在 Lua 5.3 中重新实现 Lua 5.2 随机数生成器。这当然不是一个好选择，应该避免，但原则上是可行的。

纯 C 和 Lua 实现可以在以下位置找到我的 GitHub Gist。

\documentclass{article}
\usepackage{luacode}
\begin{luacode*}

local ok, bit32 = pcall(require, "bit32")
if not ok then
    ok, bit32 = pcall(require, "bit")
end
if not ok then
    error("No bitwise operations available")
end

if _VERSION == "Lua 5.3" or type(jit) == "table" then
    local add -- https://stackoverflow.com/a/27030128
    add = function(a,b)
        if (bit32.bxor(b,0x0) == 0) then
            return a
        end
        return add(bit32.bxor(a,b), bit32.lshift(bit32.band(a,b),1))
    end

    local r = {}

    local ffffffff = bit32.bnot(0x00000000)
    local RAND_MAX = 2147483647

    local i = 0
    local rand = function()
        i = i % 344 + 1
        r[i] = add(r[(i - 32 + 344) % 344 + 1], r[(i - 4 + 344) % 344 + 1])
        local r = bit32.rshift(bit32.band(r[i], ffffffff), 1)
        return r
    end

    local srand = function(seed)
        -- can't seed with 0
        if seed == 0 then
            seed = 1
        end

        r[1] = seed
        for i = 2, 31 do
            --[[ (from stdlib/random_r.c) This does:
                    r[i] = (16807 * r[i - 1]) % 2147483647;
                but avoids overflowing 31 bits. ]]
            local hi = math.floor(r[i - 1] / 127773)
            local lo = r[i - 1] % 127773
            r[i] = bit32.band(16807 * lo - 2836 * hi, ffffffff)
        end
        for i = 32, 34 do
            r[i] = r[i-31]
        end
        for i = 35, 344 do
            r[i] = add(r[i-31], r[i-3])
        end
    end

    function math.random(l,u)
        local r = rand() / RAND_MAX
        if l and u then -- lower and upper limits
            assert(l <= u, "interval is empty")
            return math.floor(r*(u-l+1)) + l
        elseif l then -- only upper limit
            assert(1.0 <= u, "interval is empty")
            return math.floor(r*u) + 1.0
        else -- no arguments
            return r
        end
    end

    function math.randomseed(seed)
        if seed < 0 then
            srand(math.floor(seed))
        else
            srand(math.ceil(seed))
        end            
        rand() -- discard first value to avoid undesirable correlations
    end

    -- the default seed is 1
    srand(1)
end

\end{luacode*}
\usepackage{tikz}
\usetikzlibrary{decorations.pathmorphing,graphs,graphdrawing}
\usegdlibrary{force}
\begin{document}
\tikz [spring electrical layout, node distance=1.3cm,
       every edge/.style={
         decoration={coil, aspect=-.5, post length=1mm,
                     segment length=1mm, pre length=2mm},
         decorate, draw}]
{
  \foreach \i in {1,...,6}
    \node (node \i) [fill=blue!50, text=white, circle] {\i};

  \draw (node 1) edge (node 2)
        (node 2) edge (node 3)
                 edge (node 4)
        (node 3) edge (node 4)
                 edge (node 5)
                 edge (node 6);
}
\end{document}

此图像仍然不会完全相同。3 和 4 之间的线圈将具有不同的绕组数，但我不知道这是怎么回事。这可能是由于 Lua 5.3 引入了整数数据类型而导致的数值不精确的产物。

外部函数接口

rand()另一种方法是使用和srand()函数通过外部函数接口 (FFI) 访问它们来重新定义随机数生成器。但是，这需要。为了节省一些空间，我仅介绍将进入上一个示例的环境的--shell-escape块。luacode

local ffi = assert(require("ffi"))

ffi.cdef[[
int rand();
void srand(unsigned seed);
]]

if _VERSION == "Lua 5.3" then
    local RAND_MAX = 2^31 - 1

    function math.random(l,u)
        local r = ffi.C.rand() / RAND_MAX
        if l and u then -- lower and upper limits
            assert(l <= u, "interval is empty")
            return math.floor(r*(u-l+1)) + l
        elseif l then -- only upper limit
            assert(1.0 <= u, "interval is empty")
            return math.floor(r*u) + 1.0
        else -- no arguments
            return r
        end
    end

    function math.randomseed(seed)
        if seed < 0 then
            ffi.C.srand(math.floor(seed))
        else
            ffi.C.srand(math.ceil(seed))
        end            
        ffi.C.rand() -- discard first value to avoid undesirable correlations
    end
end

玩弄数字

如果您查看 Lua 5.2 和 Lua 5.3 如何获取随机数的源代码，您会发现它们看起来非常相似：

// Lua 5.2
lua_Number r = (lua_Number)(rand()%RAND_MAX) / (lua_Number)RAND_MAX;
// Lua 5.3
double r = (double)l_rand() * (1.0 / ((double)L_RANDMAX + 1.0));

如果rand()和l_rand()返回相同的数字，那么结果只会因乘以的因子而不同。换句话说，你可以通过简单的乘法从 Lua 5.3 中的结果获得 Lua 5.2 的结果：

r52 = r53 * (RAND_MAX + 1.0) / RAND_MAX

然后我们就可以简单地挂接math.random函数并像这样摆弄数字。为了节省一些空间，我仅介绍将进入luacode第一个示例的环境的块。

if _VERSION == "Lua 5.3" then
    local RAND_MAX = 2^31 - 1
    local random = math.random
    function math.random(l,u)
        local r = random() * (RAND_MAX + 1.0) / RAND_MAX
        if l and u then -- lower and upper limits
            assert(l <= u, "interval is empty")
            return math.floor(r*(u-l+1)) + l
        elseif l then -- only upper limit
            assert(1.0 <= u, "interval is empty")
            return math.floor(r*u) + 1.0
        else -- no arguments
            return r
        end
    end
end

在我的平台上，这确实有效，因为在 glibc 中，rand()只是 的别名random()，但我不认为这可以依赖，特别是在 BSD 上。

相关内容