【TIS-100 攻略】第 13 关：乘法器

本文首发于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原创不易，转载请注明出处。

第 13 关《乘法器》（Signal Multiplier）关卡展示

本关要求向 OUT 口输出 IN.A 乘以 IN.B 的值。

根据乘法定义，A x B = A + A + ... + A，共 B 个 A 相加。或者 B + B + ... + B，共 A 个 B 相加也行。我们可以借用第 5 关《信号叠加器》的思想，让一个节点向最终输出节点传 A 次 B，输出节点首先初始化为 -999 的偏置量，然后将这么多次 B 的值累加起来。当上方的节点传完 A 次 B 后再突然传个 999，让输出节点发现自己的累加器变成了 0 或正数，这样输出节点就得到了没有偏置量的正确结果。代码如下：

左上角的节点把 IN.A 的值汇总到右边（mov up right）。

右上角的节点先将 IN.B 的值放入 bak 中（mov up acc, swp），再从左边接收 IN.A 的值放入 acc（mov left acc）。接下来我们开始执行【向下方发送 A 次 B 的任务】。这时候我们可以把 A 当作剩余次数计数器来用：每发送一个 B，就令 A 减 1，直到 A 减到 0 为止，改为发送最终的 -999。所以我们收到 A 后，检查 A 是否是 0。若 A 为 0，则跳到第 10 行去执行（jez a）。当 A 不为 0 时，说明 B 没有发送过足够多的次数，此时我们将 bak 里的 B 换出来发给下面，发完后再换回去（swp, mov acc down, swp）。每发送一次 B，就令 A 减 1（sub 1）并判断是否减到了 0。只要 A 未减到 0，我们就跳回第 5 行继续向下发送 B 值（jnz 5），直到 A 减到 0 后，向下发送一个 999，准备执行下一次任务（mov 999 down）。

中央节点纯传话（mov up down）。

下方节点首先将 acc 初始化为 -999（mov -999 acc），然后不断从上方接收值。每收到上方传来的一个值，就无脑累加到自己的 acc 里（add up），然后判定 acc 是否仍为负数。只要 acc 仍为负数，就跳回到第 2 行继续累加（jlz 2）；当 acc 变为 0 或正数后，就说明上方发送了最终的 +999 偏置修正量。我们直接将本次的正确答案发给下方的 OUT 端口即可（mov acc down）。

点击左下角的【RUN】，稍等片刻，便会弹出结算界面：

利用乘法交换律给程序加速

我们知道，A x B 既可以通过累加 A 次 B 得到，也可以通过累加 B 次 A 得到。那么我们可以事先比较一下 A 和 B 的大小，将其中较大的一方视为【操作数】，较小的一方视为【累加次数】。例如，当 A = 3, B = 8 时，我们最好选择计算 8 + 8 + 8，而不是 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3。具体到代码里，就是 acc 里存较小的数字，bak 里存较大的数字，上方的节点给下方发 acc 次 bak 后，再发一个 999。代码如下：

左上方的节点没啥好说的，将得到的 A 值给右边发送两遍（mov up acc, mov acc right, mov acc right）。我们现在已经很熟练了，找两者中的较大／较小值时，其中一方必然要将自己的数提供两遍。

右上方的节点首先将 B 存入 bak（mov up acc, sav），然后计算 B - A 的值（sub left）。若差值大于 0，则跳到第 9 行执行（jgz 9）。第 5~8 行仅当差值小于等于 0 时才会被执行：差值小于等于 0 时，说明 B 是较小的一方，A 是较大的一方。此时我们先发送较大的 A（mov left down），再发送较小的 B（swp, mov acc down, jmp 1）。第 9~11 行仅当差值大于 0 时才会被执行：差值大于 0 时，说明 A 是较小的一方，B 是较大的一方。此时我们正好反过来，先发送较大的 B（swp, mov acc down），再发送较小的 A（mov left down）。

中央节点首先收到的是较大的【操作数】，将其放入 bak（mov up acc, swp）；第二次收到的是较小的【累加次数】，将其放入 acc（mov up acc）。接下来的逻辑和上一版方案完全一样，向它的下方节点发送 acc 次 bak，最后发送一个 999。

最下方的节点的代码没有任何改动。点击左下角的【RUN】，稍等片刻，便会弹出结算界面：

至此，我们程序的运行时长缩短到了 992 周期。