军团战棋英雄时代触发器之数学运算

军团战棋英雄时代触发器之数学运算如下：

军团的地图编辑器触发器系统是一门编程语言。

……开个玩笑，但它真能干很多奇怪的事情。

长文警告，胡言乱语警告

1. 乘法

触发器自身提供了加法和减法——即计数器A，“增加”，“使用计数器”，计数器B的效果，可以视作A+=B。

利用这个，就可以得到最初级的乘法运算：

令计数器X=0，调用“乘法器”B次，后者的内容则是令计数器X增加计数器A。

这样足够好吗？当然不。调用一个触发器的上限是500次，而根据设备运算能力的不同，有时达不到500次设备就会卡死，我们显然不希望得到错误的结果或干脆直接卡掉。

那么要怎么办呢？

乘法本质上是一些加法。我们重复了B次增加A的操作，使得总触发数量达到了B次。如果试图减少它，就必须增加每次令结果增加的数值。

一个很自然的想法是令每次增加的数值都“最有意义”——例如，我们将一个数乘以20，可以先算出其10倍，储存起来，再加上一次这个10倍，这样就只需要加两次了。很自然地这个思路最终会延展到——二进制。

我们来计算A乘以X。首先，我们把X化成二进制的序列，然后对于从1开始的每一个位，我们令A自加一次，当对应位是1的时候我们把这个临时结果加到最终结果中去。例如我们计算10*5，首先将5化作二进制序列101，然后对应这个我们先将结果增加10、然后乘数自加一次变为20，下一次对应位是0不加跳过，乘数继续自加为40，再下一次加成10+40=50，就得到了需要的积。由于自加和结果增加之间有一个判断，需要分开成两个触发器，每个各触发3次，以及，没错，将7序列化也需要一个触发器运行3次。我们在游戏初始化时储存1、2、4、8……等32个位的值，然后依次比较并相减就可以得到序列化的结果。

因此这样的计算中触发次数是9次。然而，当被乘的规模放大的时候，我们也只需要增加很少的次数。实际上，游戏计数器的上限是2147483647（2^31-1，32位符号整数的上限），因此每个循环实际上只有31次，就算步骤多一些，也不可能超过设备上限的。

以下是所用到触发器的详情：

初始化：游戏开始时触发，令A=1、I=0、调用“初始化位”31次；初始化位：令比特[I]=A，然后A增加A，然后I增加1。这个序列执行完毕后我们会得到比特0=1，比特1=2，比特2=4，一直到比特30=1073741824（下一个是-2147483648，不能多算，否则溢出会导致整个逻辑错误）。

乘法：计算A×X

（1）清理：令I=0、（X比特[I]=0、I增加1）31次；然后Y=0，将所需的计数器都清理干净。因为(2)的效果中没有“否则”，因此这里要给每一位预先清零。

（2）序列化：令I=30、（当前比特=比特[I]，（条件：X大于等于当前比特，效果：X减少当前比特，X比特[I]=1），I减少1）31次。

（3）加和：令I=0、（当前X比特=X比特[I]，（条件：X比特等于1，效果：Y增加A），A增加A，I增加1）31次。

最后，这个算法依旧是X那方只能计算正数，并且，A自加的时候要额外判断一下是否溢出，所以A最好也是正数。

我们这里用了两个临时变量当前比特，是因为目前触发器系统的bug，在条件栏里无法写[]。

2. 带余除法

作为乘法的逆运算，除法因为存在余数的干扰相对复杂那么一丁点……也不是很多。

通常我们计算A/X，可以令A分别减X，直到A

还是一样引入二进制，我们先记录X的1、2、4、8……倍是多少，然后用A从高到低挨个比较下来，就可以得到商的各个位值。最后用已存好的二进制位对应相加就得到了商数。

初始化同上。

除法：计算A/X=Y...A

（1）清理：Y=0，其他不用清理因为我们会用赋值覆盖掉。

（2）X序列化：令I=0，（X倍数[I]=X，X增加X）31次；

（3）求商：令I=30，（当前X倍数=X倍数[I]，（条件：A大于等于当前X倍数，效果：A减少当前X倍数，Y增加比特[I]），I减少1）31次

3. 开根号

在开玩笑？并没有。

开根号有一种叫长除法的递推算法，本质上是和除法差不多的一个计算。它的原理是这样的：要开根号A，我们先进行试商得到一个初值X，并且保证X^2

我们接下来要试一个更接近的数值，比如X+D。

因为(X+D)^2=X^2+2XD+D^2，要求其小于A，我们注意到计算过几次后D会很小，这里扔掉平方项，演变成D<（A-X^2）/2X，每一位都是一个除法。

但其实还不用那么麻烦。记得我们刚用的的二进制大法吗？如果每次只前进一个二进制位，那么这个除法的商只可能是0或者1，这样它就退化成了一次比较，这个就方便多了。

我们引入一个已有商记录已开过根号的粗结果X，再引入一个位标记，当标记走到1的时候，X就是最接近的开平方结果，而A中剩下的数值则是余数。

那么怎么计算A-X^2呢？

我们这里注意到X每一次计算的时候它是2^I的倍数，那么它的平方就是4^I的倍数，如果我们将A直接序列化为四进制数，我们每次扔掉一位就OK了，不用计算这个差值。

这样优化的结果就变成如下的步骤：

初始化同上。

开平方：计算Sqr(A)=X

（1）清理：令I=0、（A比特[I]=0、I增加1）16次；二进制31位就是四进制16位。

（2）序列化：令I=30、（当前比特=比特[I]，（条件：A>当前比特，效果：A减少当前比特、A比特[I]增加1）调用3次，然后I减少2）

这里是直接一个商最多为3的简单除法，就嵌入式写在里面了。

（3）长除法：这里只写最终优化过的一个手顺，毕竟中间的列表计算和比较太复杂了，讲起来还得这文这么长。

要用到三个变量，先令X=0，Y=0，Z=0。

然后I=15，（Y增加Y，Y增加Y，Y增加A比特[I]，X增加X，Z=X，Z增加X，（条件：Y>Z，效果：X增加1，Y减少Z，Y减少1），然后I减少1）16次。

最终X中就是开平方的结果，Y中则是余数。

4. 伪随机数

其实这篇和开平方没关系，但因为是比上面几个基础计算更上一级的算法，就写在这里了。

军团自带有一个随机执行的功能，设置两个效果：X=0和X=1，随机其中1个效果，就得到一个随机的比特。

然而，如何得到一个随机序列，它具有一定的可预测性（例如不会连续为0很多次）、最重要的是保持反复游戏中结果不变呢？这里就需要使用伪随机数发生器了。

军团的机能能够实现的最理想的发生器是LCG（线性同余发生器），它的工作机制是：从上一个随机数R1，经过R2=(A*R1+C) mod M来得到下一个随机数。仔细选择参数，可以实现一个周期为M、范围为0到M-1的随机序列。而对于每个输入的相同的A1，这个序列都是相同的。

军团的计数器上限是32位整数，我们这里需要保证取到最大值M-1的时候A*M-1低于32位，否则虽然理论上可以计算，但我们的乘法器算不了啊。

所以这里M只能选择到20位，把剩下10位让给A。具体参数选择就不多讲了，我个人用的是R2=1033*R1+12345 mod 1048576。

这个R2实际上还有随机性不是很足的问题，不过我们可以去掉后5位，也就是除以32取商，这样得到0-32767之间的数字随机性会相对充分。进一步地我们可以让它除以我们需要的上限（比如100）再取余，这样会比固定上限灵活很多，而只增加不多的工作量。我们的种子R1则存储于内部计数器中不拿出来使用。

更多花活待下期（如果有的话）补充。

以上就是军团战棋英雄时代触发器之数学运算相关内容。