如何在mc里打造一个计算器[7] -- 开平方

2022-04-03 03:34 作者:nyasyamorina 0人读过 | 我要投稿

没想到吧, 这个系列居然会更新.

话不多说就直接开始正文罢.

首先说明一下平方的显而易见的规律: 无论在多少进制下, n 位整数平方后最多为 2n 位; 并且如果整数以 m 个 0 结尾的话, 平方后会以 2m 个 0 结尾. 这里说明对一个数字开平方, 可以把数字分割成一串 2 个数字组成的列表再进行后续计算.

上面说到的第 2 点提供了一个从高位开始计算逐渐逼近答案的方法:

考虑数字 7, 它的平方是 49, 而 8 的平方是 64, 那么 4900 开方是 70, 6400 开方是 80, 而区间 [4900, 6400) 里所有数字的开方都是 7x.xx, 而后续的位可以使用类似的方法逐位算得.

用 207936 做例子: 1) 首先看到 20, 小于 20 最大的完全平方数是 16, 也就是说 207936 开方的第一位是 4. 2) 然后看到 2079, 设 2079 是一个数字的平方, 由上一步可以设这个数字是 40+a, 那么得到方程 (10×4+a)² = 2079, 解得 a=5.596⋯, 因为这里 a 必为整数, 所以对 a 向下取整得 5. 3) 最后看到 207936, 因为这是 6 位数, 所以开方后是 3 位, 由上面两部得到前两位是 45, 那么又可以列出方程 (10×45+b)² = 207936, 这里可以直接解得 b=6, 于是得出 207936 开方为 456.

在二进制里也是类似的, 用 25 做例子, 25 的二进制为 011001 (需要用 0 补充到偶数长度): 01) 看到 01, 开方即为 1. 10) 看到 0110, 列出方程 (10×1+a)¹⁰=0110 (二进制下), 解得 a=0.011⋯, 也就是 a 取 0. 11) 类似地可以列出方程 (10×10+b)¹⁰=011001 (二进制下) 解得, b=1, 也就是说 011001 开方为 101.

剩下的问题就是如何用硬件计算上述过程里的方程了.

为了方便, 记某一步需要"看到"的数字为 x₁, 开方后前面已知的数字为 y₀, z = x₁ - 100×y₀¹⁰ 和需要求的位为 a. 以上面二进制例子的第二步为例, x₁=0110, y₀=1, z=0010.

那么方程可以写为 (10×y₀+a)¹⁰=x₁, 展开括号为 100×y₀¹⁰ + 100×y₀×a + a¹⁰ = x₁, 使用上述约定可以化为 100×y₀×a + a¹⁰ = z. 因为 a 只能取 0 或 1, 所以当 z ≥ 100×y₀×1 + 1¹⁰ = 100×y₀+1 时 a 取 1, 否则 a 取 0.

当已知这步的 z 时, 如果 a = 1, 那么下一步 z = 100×(z - (100×y₀+1)) + p, 否则 z = 100×z + p, 这里 p 为下一步比上一步需要"多看"的部分. 比如上面二进制例子的第二步的 p=10. 并且使用加法器可以直接同时求得 a 和 z - (100×y₀+1) (a 为加法器的进位输出).

特殊地, 开始计算的第一步可以看作 y₀=0 和上一步 z=0 的特殊情况, 所以只需要不断迭代这个步骤就可以求出数字的开方. 另外, 这个算法对小数也适用, 所以控制迭代次数就可以以任意精度求得结果. 实际上, 最后一步剩下的 z 可以用作判断绝对误差, 不过这就是另外一个话题了 (主要是应该不会有人在意).

下面是模拟硬件算法的 julia 函数, quotient 是 y₀, remainder 是 z, carry 是 a.