63 lines
2.6 KiB
Markdown
63 lines
2.6 KiB
Markdown
# Outer sum 为什么成立
|
||
|
||
这里分离的是送入 Random 之前的坐标项。把有符号 32 位回绕写成
|
||
|
||
$$
|
||
J_{32}(a)=((a+2^{31})\bmod 2^{32})-2^{31}.
|
||
$$
|
||
|
||
按原式中 int 乘法、long 转换的实际位置，坐标项是
|
||
|
||
$$
|
||
T(x,z)=J_{32}(4987142x^2)+J_{32}(5947611x)
|
||
+4392871J_{32}(z^2)+J_{32}(389711z).
|
||
$$
|
||
|
||
尤其要注意 Z 的平方在乘 4392871 **之前**就转换成 long；X 的平方与 4987142 相乘则仍在 int 中进行。不能统一改成无限精度的二次多项式，也不能把各个 $J_{32}$ 随意移到整个和的外面。
|
||
|
||
定义
|
||
|
||
$$
|
||
\begin{aligned}
|
||
F(x)&=J_{32}(4987142x^2)+J_{32}(5947611x),\\
|
||
G(z)&=4392871J_{32}(z^2)+J_{32}(389711z).
|
||
\end{aligned}
|
||
$$
|
||
|
||
前两项只依赖 X，后两项只依赖 Z；没有混合项。只是对原来的加和项分组，便得到精确恒等式
|
||
|
||
$$T(x,z)=F(x)+G(z).$$
|
||
|
||
这对应 `common.hpp` 的 `xTerm`、`zTerm` 和 `term`；C++ 实现用无符号运算显式模拟回绕与符号扩展。
|
||
|
||
选取 $m$ 个 X 坐标、$n$ 个 Z 坐标，记列向量
|
||
|
||
$$
|
||
\mathbf X=(F(x_0),\ldots,F(x_{m-1}))^{\mathsf T},\qquad
|
||
\mathbf Z=(G(z_0),\ldots,G(z_{n-1}))^{\mathsf T}.
|
||
$$
|
||
|
||
每个格子的坐标输入是 $T_{ij}=X_i+Z_j$。用全 1 向量表达“复制”，就得到
|
||
|
||
$$
|
||
\mathbf T=\mathbf X\mathbf 1_n^{\mathsf T}
|
||
+\mathbf 1_m\mathbf Z^{\mathsf T}.
|
||
$$
|
||
|
||
第一个矩阵的每列都是 X，第二个矩阵的每行都是 Z 的转置。它们形状均为 $m\times n$，逐项相加就是 outer sum。式中的两个复制操作可以各写成一次外积；最终坐标表不是 $\mathbf X\mathbf Z^{\mathsf T}$ 那种相乘的表。
|
||
|
||
这是数学表示，GPU 不需要真的分配两个复制矩阵或完整的 T 矩阵；实现只保存两条轴，在检查某格时取出对应的两个轴项相加。
|
||
|
||
例如，X 为 2、5，Z 为 10、20、30：
|
||
|
||
$$
|
||
\begin{pmatrix}2&2&2\\5&5&5\end{pmatrix}
|
||
+\begin{pmatrix}10&20&30\\10&20&30\end{pmatrix}
|
||
=\begin{pmatrix}12&22&32\\15&25&35\end{pmatrix}.
|
||
$$
|
||
|
||
这些数只用于演示，不是实测坐标项。计算轴函数需要 $m+n$ 次，而不是在每个格子分别重复算 F、G；构造全部格子仍需 $mn$ 次相加，检查全部格子仍需相应的 Random 判断。
|
||
|
||
实际 16×16 锚点 tile 检查 5×5 图案，需要沿每条轴包含 halo 的 20 个项，共 40 个轴项。40 个轴项只解决预计算，不能说 40 次计算就完成了全部搜索。
|
||
|
||
最后，`seed + T` 之后还有 XOR、LCG、移位、取模及可能的拒绝重抽。不能把横轴的随机数结果和纵轴的随机数结果直接相加得到二维结果，也不能据此断言最终 slime 布尔图案可分离。
|