47 KiB
史莱姆区块搜索：从 CPU 枚举到种子解析求解
本文从单个区块的判定开始，依次介绍 CPU 枚举、CUDA 并行、坐标项复用，再推导当前 bench/slime-bench 搜索算法的数学原理。前四个版本说明如何让同一批检查执行得更快；后面的算法利用 Random 的结构，减少需要检查的候选。
当前算法的核心思路是：先用输出奇偶筛掉不可能的低位，再成组排除不可能的中间位，最后通过区间求交求出高位。 给定一个位置，找出让指定区域全部成为史莱姆区块的世界种子；给定位置范围，就对范围内各位置执行这套搜索。
候选生成要求每格“首次随机输出能被 10 整除”。最终执行完整 Java 判断，保证输出的种子确实满足要求；当前入口仍可能漏掉依赖拒绝重抽的解，具体边界见第 14 节。
正文给出一般性的公式和推导；引用块中的“贯穿案例”统一使用同一个实心 5×5 窗口，在有效种子归一化一节引入后逐步展开。性能表引用已有实验，分别注明任务与计时范围。算法固定常量、位数与枚举范围属于一般性内容，符号与常量集中列在文末总表。
0. 史莱姆区块的判定流程
本文研究的是 Java 版的史莱姆区块判定。一个区块在水平方向覆盖 16\times16 个方块；下面的 (x,z) 都是区块坐标，不是方块坐标。
判定由世界种子和区块坐标共同决定：先计算坐标项 $T(x,z)$，与世界种子组合后初始化 Random，再调用 nextInt(10)。返回 0 就是史莱姆区块，返回 1 到 9 则不是。
先看直接使用 Random 的版本：
import java.util.Random;
boolean isSlimeChunk(long worldSeed, int x, int z) {
long coordinateTerm = (long) (x * x * 4987142)
+ (long) (x * 5947611)
+ (long) (z * z) * 4392871L
+ (long) (z * 389711);
long randomSeed = (worldSeed + coordinateTerm) ^ 987234911L;
return new Random(randomSeed).nextInt(10) == 0;
}
再展开 Random 内部的过程：初始化 48 位状态，按“乘 $A$、加 11、保留低 48 位”更新，取高 31 位，再取余得到 0 到 9；极少数输出需要拒绝重抽。下面的版本与上面的判定等价：
boolean isSlimeChunk(long worldSeed, int x, int z) {
final long A = 0x5DEECE66DL;
final long mask48 = (1L << 48) - 1; // 低 48 位全为 1
// 先计算坐标项 T(x, z)，保留原公式的 int 溢出行为。
long coordinateTerm = (long) (x * x * 4987142)
+ (long) (x * 5947611)
+ (long) (z * z) * 4392871L
+ (long) (z * 389711);
// 1. 史莱姆公式先做一次 XOR，Random 初始化再做一次 XOR。
long randomSeed = (worldSeed + coordinateTerm) ^ 987234911L;
long u = (randomSeed ^ A) & mask48;
// 合并写法：u = ((worldSeed + coordinateTerm) ^ C) & mask48
// 其中 C = 987234911L ^ A。
while (true) {
// 2. 更新状态：乘 A、加 11，只保留低 48 位。
long v = (A * u + 11) & mask48;
// 3. 丢掉低 17 位，取高 31 位。
int q = (int) (v >>> 17);
// 4. 取余，并检查这次输出是否可以接受。
int value = q % 10;
if ((long) q - value + 9 <= 0x7FFFFFFFL) {
return value == 0;
}
// 本次输出被拒绝，从刚得到的状态继续取数。
u = v;
}
}
代码中的 ^ 是按位异或，& mask48 保留低 48 位，>>> 17 取高 31 位。
后文沿用代码中的符号：A 是固定乘数，C 是两次 XOR 合并后的常量；$u$、v 是更新前后的状态，q 是原始输出。
坐标项与 Java 整数回绕
坐标 (x,z) 指区块坐标。先用一个记号表示 Java 有符号 32 位整数回绕：
J_{32}(\xi)=((\xi+2^{31})\bmod2^{32})-2^{31}.它表示乘法溢出后保留低 32 位，再按有符号数解释。
本文的 mod 一律取非负余数。模 2^n 相当于只保留低 n 位，其中 n 表示保留的位数。
原始坐标项是：
T(x,z)=J_{32}(4987142x^2)+J_{32}(5947611x)
+4392871J_{32}(z^2)+J_{32}(389711z).
X 的平方与系数相乘后才转换为 long；Z 的平方在乘系数前就转换为 long。因此不能把它随意改成没有回绕的二次多项式。
相同种子与坐标总会得到相同结果。 单个区块成为史莱姆区块的概率约为 $1/10$，相邻区块却不能直接视为独立。本项目反向利用这些关系，搜索让给定窗口内所有区块都返回 0 的世界种子。
1. CPU：按种子枚举位置
最直接的方法是枚举世界种子和区块坐标，调用第 0 节的判定函数。要找一片全部满足要求的区域，就检查该位置及其周围各格；只要一格失败，这个候选便可提前退出：
for worldSeed in seeds:
for (x, z) in positions:
allSlime = true
for (dx, dz) in requiredOffsets:
if not isSlimeChunk(worldSeed, x + dx, z + dz):
allSlime = false
break
if allSlime:
record(worldSeed, x, z)
requiredOffsets 列出待检查区域内各格相对 (x, z) 的偏移。break 只结束当前区域的逐格检查，随后继续检查下一个位置。
CPU 多线程把种子区间分给不同工作线程。每个线程拿到一批种子，逐个扫描同一张坐标地图；不同候选之间互不依赖，适合并行处理。
这一步的主要成本是候选太多。即使绝大多数候选在前几格就失败，也仍要逐个访问“种子数 × 位置数”这么多种组合。
早期入口是根目录的 slime.cpp。用于受控比较的教学版本是 01_cpu.cpp，它与下面的 CUDA 版本使用相同的 Java 算术、搜索边界及完整命中记录规则。
2. CUDA：每个线程负责一个种子
第一版 CUDA 保留上面的循环结构，让一个 GPU 线程负责一个种子，在线程内部扫描整个坐标矩形：
GPU thread(worldSeed):
for (x, z) in positions:
check and record this candidate
GPU 可以同时安排大量这样的任务。这里的 thread 是执行一份任务的线程，block 是一组线程，kernel 是 GPU 执行的函数。把种子分给更多线程，便能同时检查更多候选。
这一版改变了执行硬件，搜索的候选集合保持一致，每个线程仍要完成一整张地图的扫描。早期实现见 slime.cu，统一比较所用的版本见 02_cuda_seed.cuh。
实测对照 A：CPU 与按种子分工的 CUDA。 同样搜索 65536 个种子、257×257 个候选位置，目标都是实心 5×5；两版完整命中列表相同。
版本 搜索时间中位数 CPU，16 个逻辑线程 3550.398 ms CUDA，每线程一个种子 111.110 ms 约加速 31.95 倍。CPU 时间包含线程创建、搜索与结果收集；GPU 使用 scan 时间，含清零、同步及回传，不含一次性的上下文创建和显存分配。GPU 为 RTX 3060 Laptop，详细记录见 BENCHMARK.md。
3. CUDA：固定坐标，在线程内遍历种子
还可以交换两层循环的分工：让一个工作单元固定一个坐标，在线程内部遍历种子。实现使用 grid-stride loop，一个线程完成当前坐标后，还可能继续处理其他坐标。
之前：thread(worldSeed) -> 扫描全部坐标
之后：thread(x, z) -> 遍历全部种子
这样，位置数量也能提供并行任务。种子较少、地图很大时，尤其能避免只有少量线程各自承担很长的扫描循环。
坐标固定后，还能复用与种子无关的计算。将第 0 节的坐标项按变量分组：
F(x)=J_{32}(4987142x^2)+J_{32}(5947611x),G(z)=4392871J_{32}(z^2)+J_{32}(389711z),T(x,z)=F(x)+G(z).F 只依赖 X，G 只依赖 Z，拆分后仍严格保留原来的整数回绕规则。每个线程先算出待检查区域需要的全部 X 项和 Z 项，再遍历种子，反复使用这些结果。
这一版见 03_cuda_position.cuh。它还按图案大小展开模板，便于编译器处理私有轴项与检查循环。因此下面的实测同时包含分工调整、坐标项复用和编译期展开的效果。
实测对照 B：在更大的地图上比较两种分工。 同样搜索 65536 个种子、4097×4097 个位置、实心 5×5，重新测量 02 与 03：
版本 GPU kernel 时间中位数 02，每线程一个种子 31598.539 ms 03，固定坐标并复用轴项 17600.387 ms 约加速 1.795 倍，完整 GPU 命中列表相同。独立 CPU 核对其中的 257×257 范围，所有 GPU 命中再用独立 Java 算术核验。这组地图大于 A 组，两组之间不计算速度比。
交换分工能否获益，还取决于任务规模、寄存器用量和调度成本。两版仍检查相同的种子与位置组合，也都保留逐格提前退出。
4. Outer sum：相邻线程共享坐标轴项
上一版的轴项只供当前线程使用。相邻位置需要的 X、Z 坐标大量重叠，还可以让相邻线程共享它们。
由于 F 只依赖 X、G 只依赖 Z，完整坐标项满足：
T(x,z)=F(x)+G(z).把所有 X 项排成一列、Z 项排成一行，每个交点就是对应两项之和。这种“每个横轴项加上每个纵轴项”就是 outer sum。能拆分的是进入 Random 之前的坐标项，最终的史莱姆判定仍要逐格执行。
04_cuda_outer_sum.cuh 让一个 block 处理 16×16 个候选位置。每条轴需要的项数为“16 ＋ 目标区域的边长 − 1”，这些项放入 shared memory，供整个 block 使用。
当目标为 5×5 时，每条轴需要 20 个项，总共 40 个轴项计算，就能供这块区域的线程复用。后续的轴项相加、Random 运算和图案检查仍然需要执行；节省的是重复的坐标多项式计算。
实测对照 C：线程私有轴项与 block 共享轴项。 固定一个种子，扫描 8193×8193 个位置，目标仍为实心 5×5；重新测量 03，再与 04 比较：
版本 GPU kernel 时间中位数 03，线程私有轴项 2.715 ms 04，outer sum 共享轴项 1.598 ms 约加速 1.698 倍，完整命中列表相同。这是 100 轮交替测量的中位数。该组只搜索一个种子，不能与 B 组跨任务计算加速比。
CPU、按种子分工、按坐标分工和 outer sum 这四个版本，都在加快同一类枚举检查。接下来转向另一个问题：利用 Random 的确定性，提前判断哪些种子不可能成功，并直接求出部分未知位。
outer sum 的共享轴项实现属于这段演进中的教学版本。当前 bench 仍逐格计算完整坐标项；后面的数学推导会利用 T=F+G 的恒等式，但没有把这段 block 共享实现接入最终搜索入口。
5. Random 状态更新与 48 位等价关系
Random 状态更新与首次输出
设 w 是世界种子的低 48 位。合并史莱姆公式和 Random 初始化里的两次 XOR：
A=\mathtt{0x5DEECE66D},\qquad
C=A\mathbin{\mathrm{xor}}987234911=\mathtt{0x5E434E432}.
对单个区块 $(x,z)$，首次输出由三步得到：
u=((w+T(x,z))\mathbin{\mathrm{xor}}C)\bmod2^{48},v=(Au+11)\bmod2^{48},q=v\gg17.u 是初始化状态，v 是推进一次后的状态，q 是取出状态高 31 位得到的整数，范围为 $0\le q<2^{31}$。右移 17 位就是丢掉低 17 位。
如果首次输出被接受，nextInt(10) 返回 $q\bmod10$；返回 0 表示史莱姆区块。因此首次输出分支的候选条件是 $q\equiv0\pmod{10}$。
世界种子的 48 位等价关系
Random 初始化只保留低 48 位。世界种子相差 2^{48} 的整数倍，在相同坐标上就得到相同的完整 Random 序列，包括重抽。因此可以先搜索 $w\in[0,2^{48})$；一个 w 对应 64 位世界种子的 2^{16} 种高位取值。
这只是史莱姆判断等价，不能据此说整个 Minecraft 世界相同。
6. 有效种子归一化
从有效种子反推世界种子
先只看一个固定区块 $(x,z)$。上节的公式中，世界种子与坐标项总是以 w+T(x,z) 的形式出现。把这个和记为有效种子：
s=(w+T(x,z))\bmod2^{48}.于是初始化状态可以直接写成：
u=(s\mathbin{\mathrm{xor}}C)\bmod2^{48}.对固定坐标，T(x,z) 已知。我们可以先寻找满足输出条件的 $s$，再反推世界种子：
w=(s-T(x,z))\bmod2^{48}.这是一一对应的换元，本身不删掉任何候选。它把搜索顺序改成了“先求有效种子，再减去坐标项恢复世界种子”。
从单个区块扩展到窗口
实际要找的是让一整片区块同时满足条件的世界种子。因此指定一个窗口，取最小 X、最小 Z 的格子为锚点，并把刚才定义 s 时使用的 (x,z) 选在这个锚点上。
贯穿案例：固定一个实心 5×5 窗口。
全文都搜索锚点
(51069,419124)的窗口：$x=51069,\ldots,51073$，$z=419124,\ldots,419128$，要求全部 25 格都是史莱姆区块。按 X 方向先编号：$i=5\Delta z+\Delta x$，其中 $\Delta x,\Delta z\in{0,1,2,3,4}$。
z\backslash x51069 51070 51071 51072 51073 419124 0（锚点） 1 2 3 4 419125 5 6 7 8 9 419126 10 11 12 13 14 419127 15 16 17 18 19 419128 20 21 22 23 24 接下来计算各格相对锚点的坐标项差，再跟随一个低位根及其中一组中间位，最终恢复完整种子。局部展示两三格时，格子仍取自这张表；是否满足窗口要求，始终以全部 25 格为准。
各格相对锚点的坐标项
窗口内各格共享同一个 $w$，但坐标项不同。既然 s 已经吸收了锚点的坐标项，计算其他格子时，只需再补上“该格坐标项减去锚点坐标项”的差。把这个差记为 $d_i$，称为相对坐标项。
为简写公式，将第 i 格的坐标项记为 $T_i$，锚点编号为 0，坐标项就是 $T_0$。这样：
s=(w+T_0)\bmod2^{48},\qquad d_i=(T_i-T_0)\bmod2^{48}.锚点满足 $d_0=0$，各格则满足：
w+T_i\equiv s+d_i\pmod{2^{48}}.给状态和输出也加上格子下标后，每格统一按以下公式计算：
u_i=((s+d_i)\mathbin{\mathrm{xor}}C)\bmod2^{48},v_i=(Au_i+11)\bmod2^{48},\qquad q_i=v_i\gg17.搜索目标就是找到同一个 $s$，让窗口内所有格子都满足首次输出条件。求到后仍按原来的逆变换恢复：
w=(s-T_0)\bmod2^{48}.这就是以锚点为基准的有效种子归一化。它也让不同位置的低位条件可以按坐标类复用，具体见第 8 节。
贯穿案例：锚点的整数回绕。 锚点
x=51069的第一项在不考虑溢出时为 $4987142\times51069^2=13006679591179062$。按 Java 的 32 位整数计算，结果是 $J_{32}(13006679591179062)=-1799531722$。这个回绕值才参与后面的坐标项求和。
贯穿案例：前两格的坐标项。 将锚点和右邻格坐标代入，得到：
T_0=T(51069,419124)=-1883366190470623,T_1=T(51070,419124)=-1883363608967202.后面所有相对坐标项都从同一组 25 个
T_i计算。
贯穿案例：把锚点吸收到有效种子里。 由上面的坐标项：
s=(w-1883366190470623)\bmod2^{48},d_0=0,\qquad d_1=T_1-T_0=2581503421.因而右邻格统一从
s+2581503421初始化。现在 $w$、s都还未知，下一步先求s的低 18 位。
7. 基于输出奇偶的低 18 位筛选
把待求的有效种子拆成：
高 13 位 h | 中间 17 位 m | 低 18 位 p
s=p+2^{18}m+2^{35}h,0\le p<2^{18},\quad0\le m<2^{17},\quad0\le h<2^{13}.一个数能被 10 整除，必须先是偶数。$q_i=v_i\gg17$，所以 q_i 的最低位就是 v_i 的第 17 位，位编号从 0 开始。
加法、乘法和逐位 XOR 的低 18 位只依赖输入的低 18 位，高位不会反过来影响低位。因此只用 p 就能判断所有格子的首次输出奇偶：计算状态的低 18 位，并要求每格都满足下面的条件：
[A((p+d_i)\mathbin{\mathrm{xor}}C)+11]\bmod2^{18}<2^{17}.
这里可以先用完整整数做加法、XOR 和乘法，最后统一取模：这些运算的低 18 位只依赖输入的低 18 位，所以不必对 p+d_i 和 C 分别取模。末尾的模 2^{18} 仍需保留，条件检查的是状态低 18 位，而不是完整整数的大小。
小于 2^{17} 就表示第 17 位为 0。某格不满足，该 p 对应的全部中间位、高位都可以直接排除。
实际执行时枚举 $p=0,1,\ldots,262143$，通过所有格子的 p 保存为低位根，也就是代码里的 root。单格恰好保留一半，因为加法、XOR、奇数乘法在模 2^{18} 下都是一一对应的变换。
这一步保证首次输出都是偶数，还没有保证能被 5 整除。每根仍有 2^{17}=131072 种中间位，随后继续筛选和求解。不同坐标的根数可能不同，不能假设各格条件互相独立、每加一格都恰好减半。
实测案例：5×5 窗口的低位候选数量。
锚点
(51069,419124)的实心 5×5 窗口，最后保留 84 个低位根，约占原来 262144 个取值的 0.032%。归一化改变根的具体编号，但不改变根的数量。每根补上全部中间位后，一共需要考虑：
84\times131072=11010048种低 35 位取值。84 和 11010048 是这个具体窗口的结果，不是所有位置的固定候选数量。
后面跟随其中的 $p=218767$。代入筛选式，前两格的状态低 18 位分别是 59524、80305，都小于 $2^{17}=131072$；其余 23 格也通过。先保留这个根，再搜索它对应的全部中间位；此时尚不知道哪个
m,h会成功。
8. 坐标类周期与低位根复用
对固定窗口形状，第 i 格相对锚点的偏移记为 $(\alpha_i,\beta_i)$。由坐标项的可分离性：
d_i=F(x+\alpha_i)-F(x)+G(z+\beta_i)-G(z)\pmod{2^{48}}.低位筛选只看 $d_i\bmod2^{18}$。Java 回绕与符号扩展不会改变低 18 位，所以推导这部分时可以直接在模 2^{18} 下展开多项式：
\begin{aligned}
d_i\equiv{}&4987142(2x\alpha_i+\alpha_i^2)+5947611\alpha_i\
&+4392871(2z\beta_i+\beta_i^2)+389711\beta_i\pmod{2^{18}}.
\end{aligned}
将锚点 X 增加 $2^{16}=65536$，相对项的变化为：
2\cdot4987142\cdot2^{16}\alpha_i.4987142 是偶数，所以变化是 2^{18} 的整数倍。将 Z 增加 $2^{17}=131072$，变化为：
2\cdot4392871\cdot2^{17}\beta_i,也必然是 2^{18} 的整数倍。因此可用：
(x\bmod65536,\ z\bmod131072)作为坐标类。同类位置所有 d_i 的低 18 位相同，有效种子的完整低位根列表也相同。
程序为每个未缓存的类筛一次根，再把列表用于该类具体位置。无根类的具体位置直接跳过；有根位置才生成后续任务。缓存有大小上限。
共享的是低位根，不是最终种子。完整 d_i 的高位仍可能不同，后面的中间位、高位条件需要为每个具体位置分别计算。这一步属于有效种子低位筛选的复用，没有另加一轮固定世界种子的坐标余数对过滤。
9. 高 13 位引起的输出共同平移
先固定 $p,m$。用 q_i(h) 表示高位取 h 时的首次输出，并定义基准输出：
\bar q_i=q_i(0).横线表示固定低 35 位、取 h=0 时的基准值，不表示平均值。再记：
\ell=p+2^{18}m,\qquad s=\ell+2^{35}h.选择在第 35 位拆分，是因为 $C<2^{35}$，XOR 只翻转低 35 位，不碰高 13 位。
这里不能忽略坐标加法的进位。将 h=0 时的输入写成：
(\ell+d_i)\bmod2^{48}=\lambda_i+2^{35}\kappa_i,其中 $0\le \lambda_i<2^{35}$、$0\le \kappa_i<8192$。\kappa_i 已包含坐标项及其进位。加上 2^{35}h 后，\lambda_i 不变，高位变成 $(\kappa_i+h)\bmod8192$。
因为 XOR 不动这段高位，初始化状态满足：
u_i(h)=(u_i(0)+2^{35}h)\bmod2^{48}.乘 A 并加 11 后，先把状态更新公式完整写出：
\begin{aligned}
v_i(h)
&=(Au_i(h)+11)\bmod2^{48}\
&=(Au_i(0)+Ah,2^{35}+11)\bmod2^{48}.
\end{aligned}
而 h=0 时的基准状态已经是：
v_i(0)=(Au_i(0)+11)\bmod2^{48}.所以 11 已经包含在 v_i(0) 里面，代入后才简写成：
v_i(h)=(v_i(0)+Ah\,2^{35})\bmod2^{48}.这里比较的是两种高位取值带来的变化：两边都加同一个 11，因此变化量只有 $Ah,2^{35}$；状态本身仍包含加 11 的结果。
新增量是 2^{35} 的整数倍，不会改变右移时丢掉的低 17 位，所以：
q_i(h)=(\bar q_i+Ah\,2^{18})\bmod2^{31}.所有格子的输出都加上同一个量，再在 2^{31} 处回绕。 这让我们既能提前检查格子之间的输出差，又能解析求高位。
贯穿案例：同一窗口的共同平移。 后面会筛出 $p=218767,m=40302$。固定这两段时，前两格的基准输出为 $\bar q_0=227860608$、$\bar q_1=1920935636$。若高位取 $h=2995$，共同增量取模后为：
Ah\,2^{18}\bmod2^{31}=886833152.因而 $q_0=1114693760$，$q_1=(1920935636+886833152)\bmod2^{31}=660285140$。右邻格发生了回绕，锚点没有，但两格都遵循同一个平移公式。这里先展示这条关系；第 13 节再说明这些中间位和高位如何得到。
这条关系来自 XOR 常量与未知高位分处不同位域，不能理解为一般 XOR 具有加法线性。若切在第 34 位，C 仍会翻转未知部分的一位，上面的平移推导就不成立。
10. 基于输出差的低 35 位过滤
共同平移会改变各格输出，却不改变它们的模差。固定位置、低位根 p 和中间位 m 后，模差与高位 h 无关。定义：
\delta_i=(\bar q_i-\bar q_0)\bmod2^{31}.如果存在某个高位 $h$，使两格最终输出都是 10 的倍数，那么它们的直接差也是 10 的倍数。若差非负，模差除以 10 余 0；若差为负，取模需要加上 $2^{31}$，而：
2^{31}\bmod10=8.所以必要条件是：
\delta_i\bmod10\in\{0,8\}.贯穿案例：右邻格的模输出差。 沿用上一节的 $p,m,h$，两格的实际输出差为负：
q_1-q_0=660285140-1114693760=-454408620.加上
2^{31}后得到 $\delta_1=1693075028$，除以 10 余 8，因此通过差过滤。若反向相减，正差454408620除以 10 余 0。用基准输出计算也得到 $(1920935636-227860608)\bmod2^{31}=1693075028$。这正是“不必先知道 $h$，也能检查模差”的意义；其余 23 格仍要分别检查。
模差的余数不属于 ${0,8}$，就可以断定当前低 35 位无论怎样补高位都不会成功。
通过所有差条件仍不代表存在共同高位，因为这些条件没有决定每格的回绕情况是否能同时满足。还要做第 13 节的区间求交。
当前实现用第 12 节的组 mask 执行这个筛选，结果与逐个检查差条件完全相同。
实测案例：输出差过滤的幸存数量。
锚点
(51069,419124)的实心 5×5 窗口，在 11010048 种低 35 位中，只有 36 种通过全部输出差条件。
11. 每个低位根的公共项预计算
先看单个中间位怎样快速算出 $\bar q_i$。固定位置和根 $p$，令：
\sigma_i=p+d_i,\qquad \eta_i=\sigma_i\bmod2^{18},\qquad \gamma_i=\lfloor \sigma_i/2^{18}\rfloor.加入中间位后，输入就是：
\ell+d_i=\eta_i+2^{18}(\gamma_i+m).令 $E=C\gg18=\mathtt{0x1790d}$。XOR 可按位拆开：
(\ell+d_i)\mathbin{\mathrm{xor}}C
=(\eta_i\mathbin{\mathrm{xor}}(C\bmod2^{18}))
+2^{18}((\gamma_i+m)\mathbin{\mathrm{xor}}E).
这里只是低 18 位与高位分别做 XOR，不是把 XOR 分配到加法上。超出 48 位的部分最终取模即可。
把低位推进带来的贡献记为：
\omega_i=\left\lfloor\frac{A(\eta_i\mathbin{\mathrm{xor}}(C\bmod2^{18}))+11}{2^{17}}\right\rfloor.于是首次输出精确等于：
\bar q_i(m)=[\omega_i+2A((\gamma_i+m)\mathbin{\mathrm{xor}}E)]\bmod2^{31}.\gamma_i,\omega_i 都不依赖 $m$，每个 (位置, 根) 只需准备一次。后面重复使用它们，减少 131072 个中间位里的重复计算。
实现只需要最终结果的低 31 位，可以把公共项存为 32 位无符号整数，用 32 位回绕计算再保留低 31 位。这与公式中的模运算等价，也减少重复的 64 位乘法。
\gamma_i 表示固定根下的输入高位，\omega_i 表示低位计算产生的输出贡献；它们都会随位置和根改变，但不随中间位 m 改变。
贯穿案例：为根
p=218767准备公共项。 前两格的值为：
格子 id_i\eta_i\gamma_i\omega_i0 0 218767 0 46624833586 1 2581503421 128076 9848 13419656886 这些值算一次即可用于这个根的全部中间位。代入 $m=40302$，有 $(40302\mathbin{\mathrm{xor}}96525)=124003$、$((9848+40302)\mathbin{\mathrm{xor}}96525)=113387$，从而：
\bar q_0=[46624833586+2A\times124003]\bmod2^{31}=227860608,\bar q_1=[13419656886+2A\times113387]\bmod2^{31}=1920935636.
\omega_i是中间贡献项，可以超过 $2^{31}$；最终的\bar q_i才取模到 31 位输出范围内。
12. 中间位的 16 候选成组筛选
中间位分组规则
E=\mathtt{0x1790d} 的第 4～7 位恰好全是 0。让 m 的这四位变化，其余位固定，就得到一组 16 个值：
m_j=\mathrm{base}+16j,\qquad j=0,\ldots,15.base 的第 4～7 位必须是 0。全部中间位可以无遗漏、无重复地分成 8192 组：
\mathrm{base}=256\lfloor g/16\rfloor+(g\bmod16),\qquad g=0,\ldots,8191.贯穿案例：包含
m=40302的那一组。 固定根仍为 $p=218767$。取 $g=2526$，得到 $\mathrm{base}=40206$，整组为：m_j=40206+16j=40206,40222,\ldots,40446.其中
j=6对应 $m=40302$。这一组的低四位都为 14，第 4～7 位依次取遍 0～15，其余位相同。
组内输出差的分段常量性质
这里的“一段”是针对某个格子 i 而言：在一组候选中，\gamma_i+m_j 没有跨过 256 边界的连续部分。不同格子的 \gamma_i 不同，分界位置也可能不同。下面分步说明这一段中的输出差为什么不变。
输入只在四个 bit 上变化。 从候选 j 换到 $j+1$，中间位增加 16：
m_{j+1}=m_j+16.给一个整数加 16，不会改变它的低四位。如果没有跨过 256 的边界，第 8 位及以上也不变；变化只发生在第 4～7 位。这四位在 E 中全是 0，因此 XOR 不会翻转它们。其余位经过 XOR 后虽然可能改变，但在同一段内仍是固定的。
所以，在两个候选同属这一段的前提下，XOR 后的整数也恰好增加 16：
((\gamma_i+m_{j+1})\mathbin{\mathrm{xor}}E)
=((\gamma_i+m_j)\mathbin{\mathrm{xor}}E)+16.
这里的等式需要“不跨边界”这个前提；一般情况下，XOR 后的增量不一定等于 XOR 前的增量。
该格的输出每次增加同一个量。 将上式代入预计算后的输出公式：
\bar q_i(m_j)=[\omega_i+2A((\gamma_i+m_j)\mathbin{\mathrm{xor}}E)]\bmod2^{31}.\omega_i 不随 j 改变，XOR 后的输入每次增加 16，所以输出满足：
\bar q_i(m_{j+1})\equiv \bar q_i(m_j)+32A \pmod{2^{31}}.也就是输出每次都加 $2A\times16=32A$，再取模。
锚点输出也增加同一个量。 锚点 $d_0=0$，所以 $\gamma_0=0$，它的输入就是 $m_j$。base 的第 4～7 位为 0，整组只是将这四位依次取遍，因此锚点输入在整组内都不跨 256 边界。对锚点同样有：
\bar q_0(m_{j+1})\equiv \bar q_0(m_j)+32A \pmod{2^{31}}.相减时，两个增量抵消。 回到我们实际要筛选的模输出差：
\begin{aligned}
\delta_i(m_{j+1})
&\equiv \bar q_i(m_{j+1})-\bar q_0(m_{j+1})\
&\equiv [\bar q_i(m_j)+32A]-[\bar q_0(m_j)+32A]\
&\equiv \bar q_i(m_j)-\bar q_0(m_j)\
&\equiv \delta_i(m_j) \pmod{2^{31}}.
\end{aligned}
两边的 \delta_i 都取 [0,2^{31}) 内的非负余数，因此同余也就意味着数值相等。同一段里，各格输出都在变化，但该格与锚点的输出增加得一样快，所以两者的模差保持不变。 即使其中一个输出先在 2^{31} 处回绕，取模后的差仍然相同。
跨边界时，差值可能切换。 当 \gamma_i+m_j 跨过 256 边界，第 8 位及以上发生进位，这些位可能被 XOR 翻转。跨界那一步的输出增量不再保证为 $32A$，因此模输出差可能改变。跨界之后，输入又只在第 4～7 位变化，差值便再次保持不变。
一组的跨度只有 $16\times15=240<256$，每格最多跨一次边界。因此，这一格的整组模输出差最多有两个值：边界前一个，边界后一个；也可能两个值相同，或者整组没有跨界。
贯穿案例：右邻格在同一组中的两段差值。 仍用 $\mathrm{base}=40206$。由预计算表，右邻格 $\gamma_1=9848$，锚点 $\gamma_0=0$，且 $E=96525$：
jm_j9848+m_j锚点 XOR 后 右邻格 XOR 后 XOR 后两输入之差 0 40206 50054 123907 113291 −10616 1 40222 50070 123923 113307 −10616 7 40318 50166 124019 113403 −10616 8 40334 50182 124035 113931 −10104 15 40446 50294 124147 114043 −10104
j=0,\ldots,7时，两列 XOR 结果每步都增加 16，差固定为 $-10616$。从j=7到 8，右邻格输入跨过 256 的整数倍 $50176$，该格 XOR 结果增加 528，锚点仍只增加 16，所以差切换为 $-10104$；之后又保持不变。表格最后一列仍是输入差。代入输出公式，才得到真正要筛选的模输出差：
$$\delta_1(m_j)=\begin{cases} (13419656886-46624833586-2A\times10616)\bmod2^{31}=1693075028,&j=0,\ldots,7,\ (13419656886-46624833586-2A\times10104)\bmod2^{31}=411302484,&j=8,\ldots,15. \end{cases}
前段除以 10 余 8，通过；后段余 4，淘汰。仅检查右邻格，就能一次保留前 8 个、排除后 8 个中间位。
16 位掩码的构造与求交
只需算出组首、组尾与锚点的模差，并找到进位分界，就知道整组哪些 j 满足余 0 或 8。
设 $\mathrm{offset}_i=(\mathrm{base}+\gamma_i)\bmod256$，第一个跨边界的索引是：
\mathrm{cut}_i=\left\lceil\frac{256-\mathrm{offset}_i}{16}\right\rceil.\mathrm{cut}_i 的范围为 1～16。j<\mathrm{cut}_i 使用前段差值，j\ge \mathrm{cut}_i 使用后段差值；\mathrm{cut}_i=16 表示组内没有跨边界。
程序用一个 16 位 mask 表示通过情况：第 j 位为 1，表示 m_j 还可能成功。每格构造允许 mask，再逐格按位 AND；变成 0 就整组退出。
贯穿案例：同一组的掩码逐步求交。 右邻格允许 $j=0,\ldots,7$，掩码为
0x00ff。继续检查窗口内各格，挑出会进一步缩小结果的几步：
检查的格子 该格允许的 j该格掩码 累计交集 i=10～7 0x00ff0～7 i=32～15 0xfffc2～7 i=43～15 0xfff83～7 i=84～15 0xfff04～7 i=96～15 0xffc06、7 表中略去的格子也都参与检查，但没有继续缩小累计交集。检查完全部 25 格，最终 mask 是
0x00c0，只剩 $m_6=40302$、$m_7=40318$。下一节先沿m=40302求高位；40318也会走相同流程。
最后仅对 mask 中剩余的 m_j 求解高位。
这一步仍覆盖全部 131072 个中间位。它把逐候选差检查改成每根 8192 个组任务，每组工作量更大，不能直接说速度提升了 16 倍。
13. 高 13 位的区间求解
对组筛选留下的一个 $m$，固定 $\ell=p+2^{18}m$，计算各格 h=0 时的输出并拆分：
\bar q_i=r_i+2^{18}b_i,\qquad 0\le r_i<2^{18},\quad0\le b_i<8192.r_i 是输出的低 18 位，b_i 是输出的高 13 位；它们都是已知数。种子的高位 h 仍是未知数。由共同平移关系：
q_i(h)=r_i+2^{18}[(b_i+Ah)\bmod8192].高位换元与模逆恢复
令：
\theta=Ah\bmod8192.A 是奇数，与 8192=2^{13} 互质，所以乘 A 只是重新排列 8192 个取值，既不重复也不遗漏。具体的逆元是：
A\bmod8192=1645,\qquad1645\times4965\equiv1\pmod{8192}.因此求到 \theta 后，可以恢复：
h=4965\theta\bmod8192.单格的区间与同余条件
记 $\phi_i=(b_i+\theta)\bmod8192$。低位筛选已保证 r_i 为偶数，只需再满足模 5 条件。因为 $2^{18}\equiv-1\pmod5$：
q_i=r_i+2^{18}\phi_i\equiv r_i-\phi_i\pmod5.所以要 $\phi_i\equiv r_i\pmod5$。b_i+\theta 最多回绕一次，回绕点为 $\tau_i=8192-b_i$：
\theta 的范围 |
\phi_i 的值 |
要求 |
|---|---|---|
[0,\tau_i) |
b_i+\theta |
\theta\equiv r_i-b_i\pmod5 |
[\tau_i,8192) |
b_i+\theta-8192 |
\theta\equiv r_i-b_i+2\pmod5 |
第二条多出 2，是因为 $8192\bmod5=2$。区间 [\mathrm{lo},\mathrm{hi}) 包含下界、不包含上界；若 $b_i=0$，第二条为空。
多格条件的区间求交
从锚点的两条条件开始。对后续格子，余数相同的区间可以求交：
[\mathrm{lo},\mathrm{hi})\cap[\mathrm{lo}',\mathrm{hi}')=[\max(\mathrm{lo},\mathrm{lo}'),\min(\mathrm{hi},\mathrm{hi}')).余数不匹配就删除。每格的两个余数相差 2，对一个既定余数最多只有一段能匹配，所以求交不会继续分裂，始终最多保留两条。
区间非空还不够，里面必须有满足模 5 条件的整数。
对于余数 $\rho\in{0,1,2,3,4}$，第一个满足条件的数是：
\theta_{\min}=\mathrm{lo}+((\rho-\mathrm{lo})\bmod5).若 $\theta_{\min}\ge \mathrm{hi}$，也删除这一条。两条都被删掉，就立即判定这组低 35 位没有解。
最后按 \theta_{\min},\theta_{\min}+5,\ldots<\mathrm{hi} 枚举实际解，换回 $h$。整个过程无需先收集并排序所有格子的回绕点，也无需逐个尝试 8192 种高位。
贯穿案例的高位求解与种子恢复
贯穿案例：从
m=40302求出高位。 固定 $p=218767,m=40302$，前两格的输出拆分为：
格子 \bar q_ir_ib_i回绕点 \tau_i0 227860608 57472 869 7323 1 1920935636 206548 7327 865 代入单格条件，锚点要求：
[0,7323)中 $\theta\bmod5=3$，或[7323,8192)中 $\theta\bmod5=0$。右邻格要求：[0,865)中 $\theta\bmod5=1$，或[865,8192)中 $\theta\bmod5=3$。只有余数相同的两段能求交，因此前两格共同留下 $[865,7323)$，余数为 3。继续加入窗口内其余格子，区间逐步缩小：
已检查到的格子 保留区间 \theta\bmod5i=1[865,7323)3 i=2[865,3544)3 i=3[3202,3544)3 i=13[3202,3506)3 i=19[3382,3506)3 i=22[3382,3440)3 全部 25 格 [3382,3440)3 其余步骤不再缩小区间。第一个同余解为 $\theta_{\min}=3382+((3-3382)\bmod5)=3383$，所以这一条低 35 位候选共有 12 个高位解：
\theta=3383,3388,\ldots,3438.取第一个 $\theta=3383$，得到：
h=4965\times3383\bmod8192=2995,s=218767+2^{18}\times40302+2^{35}\times2995=102917981558415,w=(s-T_0)\bmod2^{48}=15959335054446.前两格此时 $\phi_0=4252$、$\phi_1=2518$，输出为 $q_0=1114693760$、$q_1=660285140$，都能被 10 整除。这与第 9、10 节预先展示的数值一致；下一节再核验整个 5×5。
14. 种子恢复、精确验证与覆盖边界
对每个高位解拼出：
s=p+2^{18}m+2^{35}h.先用 s 和相对坐标项 d_i 逐格执行完整 nextInt(10) 判断。通过后再恢复世界种子：
w=(s-T_0)\bmod2^{48}.完整判断与单次取模有一个差别：Java 为避免取模偏差，会拒绝首次输出的最后 8 个值，即：
q\ge2^{31}-8=2147483640,并继续推进状态、重新取输出，可能不止重抽一次。
因此，首次输出虽能被 10 整除，也可能被拒绝后重抽失败；准确验证会剔除它。反过来，首次输出不满足模 10 条件，却可能在拒绝后重抽成功；这类种子可能在候选阶段已被淘汰，验证不能补回。
所以当前算法保证记录的种子正确，但不保证找齐完整 Java 语义下的所有解。独立拒绝补扫尚未接入 bench，不属于本文的算法步骤。
贯穿案例：核验完整 5×5。 将刚恢复的
w=15959335054446代入第 0 节代码，25 格首次原始输出q_i如下：
z\backslash x51069 51070 51071 51072 51073 419124 1114693760 660285140 2105382940 47575410 1796905160 419125 2074383590 1410817530 1734889590 2009625200 440710690 419126 1664890290 537178720 1699969350 2115254790 688097620 419127 1842255790 1387847170 1302453480 1264531310 344660 419128 1757217670 204531470 2132545510 1606583470 569937090 每个数都能被 10 整除，并且都小于拒绝区间起点 $2147483640$，因此全部被接受，
nextInt(10)都返回 0。这个世界种子确实让所选窗口的 25 格全是史莱姆区块。
15. 完整执行流程与 GPU 任务划分
前文为了先说明成组筛选的依据，提前推导了高位平移；程序并不需要先枚举高位。实际执行顺序如下：
- 遍历给定范围内的锚点，计算坐标类键。
- 对未缓存的类生成全部低 18 位根；同类位置复用列表，无根位置跳过。
- 对有根的具体位置计算完整相对项 $d_i$，展开
(位置, 根)任务。 - 每个任务预计算 $\gamma_i,\omega_i$，供所有中间位使用。
- 将中间位分为 8192 组，用输出差的 16 位 mask 筛选；只保留幸存的 $m$。
- 每个幸存
m用区间求交求 $\theta$，再恢复高位 $h$。 - 拼出 $s$，完整验证，恢复并记录 $w$。
GPU 的搜索线程对应一个 (位置, 根, 中间位组)，线程内处理 mask 中的幸存者。多卡分配锚点批次，各自维护有限的类根缓存。这些并行安排不改变数学条件。
各步骤省掉的工作不同：归一化统一输入；low18 排除整片种子；类缓存避免重复筛根；公共项避免重复算术；组 mask 共用差过滤；区间求交代替高位穷举；最终验证保证输出符合原始判断。
16. 候选数量与优化效果
实测案例：已知窗口的候选数量链。
已知锚点 $(51069,419124)$、实心 5×5 的候选数量链是：
262144\text{ 个低位取值}\longrightarrow84\text{ 个根}\longrightarrow11010048\text{ 种低 35 位}\longrightarrow36\text{ 个差过滤幸存者}\longrightarrow24\text{ 个最终世界种子低 48 位结果。}36 统计的是低 35 位候选，24 统计的是最终完整种子。本案例中，36 个差过滤幸存者的低位根都是 $p=218767$；只有 $m=40302$、
40318能继续求出高位，各产生 12 个解，共 24 个。前文沿第一条分支的第一个解展开，其余 23 个结果也经过相同验证。
实测案例：同一个 5×5 窗口的性能对照。 以下只列已有报告中锚点
(51069,419124)的测量，本次没有重跑 GPU 性能基准：
优化 同窗口搜索时间 对照效果 输出差过滤＋区间求交 63.750 → 约 0.324 ms 相对旧回绕事件排序版本约 197 倍 公共项预计算 0.323584 → 0.268288 ms 约 1.21 倍 在预计算基础上增加组 mask 0.268288 → 0.156672 ms 再约 1.71 倍；后两项合计约 2.07 倍 这里统计搜索阶段，不含筛根、初始化和传输；后两行包括每轮公共项准备。首行与后两行来自不同轮次的对照实验，不能把倍数连乘成实测整体加速。
类根复用优化的是跨位置的批次任务，单个固定窗口不足以测量其复用收益，因此这里不混入另一批坐标的数值。批次性能及适用条件见批次流程报告。
代码对应关系：原始算术与验证在 solver_core.hpp；区间求交在 upper_interval.hpp；类缓存、公共项准备、组 mask 和 GPU 调度在 slime_bench.cu。
数量与实测来源：成组筛选报告、批次流程报告、输出差与区间对照报告。历史 CPU/GPU 与 outer sum 演进仍见视频工程，不作为当前算法的额外步骤。
17. 符号与常量总表
全文每个符号只承担一种含义，区间端点统一写成 $\mathrm{lo},\mathrm{hi}$。下标 i 表示格子，i=0 表示锚点；下标 j 表示组内候选。以下列出一般推导使用的符号，贯穿案例中的具体赋值不属于固定定义。
种子、坐标与随机输出
| 符号 | 含义与定义 | 取值范围或说明 |
|---|---|---|
x,z |
区块坐标；相对坐标推导中为锚点坐标 | Java 有符号 32 位整数 |
i |
窗口内格子编号 | 0 为锚点 |
\alpha_i,\beta_i |
第 i 格相对锚点的 X、Z 偏移 |
由窗口形状确定 |
J_{32}(\xi) |
将整数 \xi 回绕为有符号 32 位整数 |
$[-2^{31},2^{31})$；\xi 仅表示该函数的整数输入 |
F(x),G(z) |
坐标项的横轴部分、纵轴部分 | 严格保留 Java 回绕规则 |
T(x,z),T_i |
完整坐标项；T_i 是第 i 格的坐标项 |
$T=F+G$；T_0 为锚点坐标项 |
d_i |
相对坐标项，(T_i-T_0)\bmod2^{48} |
$[0,2^{48})$，d_0=0 |
w |
世界种子的低 48 位，最终输出 | [0,2^{48}) |
s |
归一化有效种子，(w+T_0)\bmod2^{48} |
$[0,2^{48})$；搜索对象 |
p |
有效种子的低 18 位；通过筛选后称为根 root |
[0,2^{18}) |
m |
有效种子的中间 17 位 | [0,2^{17}) |
h |
有效种子的高 13 位 | $[0,2^{13})$；s=p+2^{18}m+2^{35}h |
\ell |
有效种子的低 35 位，p+2^{18}m |
[0,2^{35}) |
$u,v$；u_i,v_i |
Random 初始化状态、推进一次后的状态 | $[0,2^{48})$；下标 i 指定窗口格子，参数 (h) 表示随高位变化 |
$q$；q_i |
首次 31 位输出，$v\gg17$；带下标时为 v_i\gg17 |
$[0,2^{31})$；q_i(h) 表示高位为 h 时的输出 |
\bar q_i |
固定低 35 位、取 h=0 时的首次输出 |
$\bar q_i=q_i(0)$；横线表示基准值，不表示平均值 |
\bar q_i(m) |
固定位置与根、随中间位 m 变化的首次输出 |
同样取 h=0 |
$\delta_i$、\delta_i(m_j) |
第 i 格与锚点的模输出差；带参数时明确指定中间位候选 |
$(\bar q_i-\bar q_0)\bmod2^{31}$；随位置、p,m 变化，与 h 无关 |
公共项、分组与高位求解
| 符号 | 含义与定义 | 取值范围或说明 |
|---|---|---|
\lambda_i,\kappa_i |
(\ell+d_i)\bmod2^{48} 的低 35 位、高 13 位 |
输入拆分为 $\lambda_i+2^{35}\kappa_i$；包含坐标加法进位 |
\sigma_i |
固定根后，p+d_i 的完整整数和 |
用于预计算 |
\eta_i |
\sigma_i 的低 18 位，\sigma_i\bmod2^{18} |
$[0,2^{18})$；固定根后用于公共项预计算 |
\gamma_i |
\sigma_i 除以 2^{18} 的商 |
$\lfloor \sigma_i/2^{18}\rfloor$；每根固定 |
\omega_i |
低 18 位输入经状态更新、右移后的公共贡献 | 第 11 节定义；位置和根固定后不随 m 变化 |
g |
中间位组编号 | 0,\ldots,8191 |
\mathrm{base} |
一组中间位的起始值 | 256\lfloor g/16\rfloor+(g\bmod16) |
j |
组内候选编号，也是 mask 的 bit 编号 | 0,\ldots,15 |
m_j |
组内第 j 个中间位候选 |
\mathrm{base}+16j |
\mathrm{offset}_i |
某格组首输入的低 8 位 | (\mathrm{base}+\gamma_i)\bmod256 |
\mathrm{cut}_i |
某格组内首次跨越 256 边界的索引 | $\lceil(256-\mathrm{offset}_i)/16\rceil$；1～16，16 表示组内不跨界 |
| mask | 组内 16 个候选的允许掩码 | 第 j 位为 1 表示 m_j 尚未被淘汰 |
r_i,b_i |
\bar q_i 的低 18 位、高 13 位 |
$\bar q_i=r_i+2^{18}b_i$；都由当前低 35 位确定 |
\theta |
高位换元，Ah\bmod8192 |
$[0,8192)$；由 h=4965\theta\bmod8192 恢复 |
\phi_i |
换元后的输出高 13 位 | (b_i+\theta)\bmod8192 |
\tau_i |
第 i 格输出高位的回绕点 |
$8192-b_i$，范围 1～8192 |
\mathrm{lo},\mathrm{hi} |
当前保留区间的下界、上界 | $[\mathrm{lo},\mathrm{hi})$；仅用于高位换元 \theta 的区间 |
\mathrm{lo}',\mathrm{hi}' |
与当前区间求交的另一段区间端点 | 撇号表示另一段区间；仍然只表示端点 |
\rho |
区间要求的模 5 余数 | 0,1,2,3,4 |
\theta_{\min} |
区间中第一个满足余数要求的整数 | $\mathrm{lo}+((\rho-\mathrm{lo})\bmod5)$；若不小于 $\mathrm{hi}$，则无解 |
算法固定常量与记号
| 常量或记号 | 数值或含义 | 用途 |
|---|---|---|
A |
\mathtt{0x5DEECE66D} |
Java Random 状态更新的乘数 |
| 加数 | 11 | Java Random 状态更新的固定加数 |
| 史莱姆 XOR 常量 | 987234911 | 原始史莱姆公式的 XOR 常量 |
C |
A\mathbin{\mathrm{xor}}987234911=\mathtt{0x5E434E432} |
合并后的初始化 XOR 常量；只占低 35 位 |
E |
C\gg18=\mathtt{0x1790d} |
公共项公式中的 XOR 常量；第 4～7 位为 0 |
| 坐标系数 | 4987142、5947611、4392871、389711 | 分别对应 X 平方、X 一次、Z 平方、Z 一次项 |
| 1645、4965 | A\bmod8192 及其模 8192 逆元 |
两者乘积模 8192 为 1 |
2^{18}=262144 |
低位取值总数；也是输出低位拆分的模数 | 由算法位数决定，与具体窗口无关 |
2^{17}=131072 |
每个根对应的中间位取值总数 | 分为 8192 组，每组 16 个 |
2^{13}=8192 |
高位取值总数；也是换元 \theta 的模数 |
与具体窗口无关 |
2^{31}-8=2147483640 |
nextInt(10) 拒绝区间的起点 |
精确验证处理重抽 |
n |
模 2^n 运算保留的位数 |
一般性位数记号，不是组内分界 |
$\bmod$、\equiv |
非负取余、同余关系 | 模 2^n 等价于保留低 n 位 |
$\mathrm{xor}$、\gg |
按位异或、右移 | 本文随机状态和输出均按非负整数解释 |
[\mathrm{lo},\mathrm{hi}) |
含下界、不含上界的区间 | 枚举整数时要求 \mathrm{lo}\le \theta<\mathrm{hi} |