每日精学 149｜逐位恢复整数平方根

雷达 · 通信 · 电子战　/　基础精学 149

逐位平方根算法利用平方增量检验从高位到低位构造整数根，结果与余数共同给出精确的向下取整证明。

01
模型与符号

被开方数A为非负16位无符号整数，输出

使用足够宽平方比较中间量。

02
从模型到公式

输出判据

整数平方根由

唯一确定。令 R=A−q²，等价条件为

因此根和余数可独立验证，无需依赖浮点开方。

候选增量

若当前根为q，尝试设置尚未处理的二进制位b，则

候选增量不超过剩余量时接受该位，否则恢复原根；随后令b减半。

从高位到低位

16位A的根不超过255，故从 b=128 开始，按128、64、32、16、8、4、2、1依次检验。每步保留不超过真实根的最大已定前缀，结束后下一整数无法再被接受，因而满足上述夹逼。

输出还可用于固定点：若A表示 x2^2F，则

余数判据给出的完整正确性条件

整数平方根不仅要检查输出平方不超过输入，还需排除输出偏小。令

、r=A−q²，正确结果等价于

因为 (q+1)²−q²=2q+1。

这给出不依赖浮点开方的整数自检判据。对于十六位无符号输入，有

输入端口虽然使用有符号容器，算法明确把低十六位解释为无符号被开方数，因此码型全一表示六万五千五百三十五，而不是负一。

若先进行有符号扩展再开方，将改变问题定义；输出根和余数的位宽也应分别按各自范围规划。

03
物理含义

根位的接受条件使用整数平方差，因此能够输出严格正确的下界，适合需要确定舍入方向的幅度与归一化模块。

04
固定参数算例

枚举全部0至65535输入，使用逐位算法验证根夹逼与余数界，检查完全平方数及其相邻整数。

图 1　逐位恢复整数平方根的理论关系与固定参数验证

表中数值和图中曲线由 MATLAB 实际运行得到，随机种子为 20261068；运行版本与完整结果另存为独立文件。

05
数字实现的边界

RTL对16位无符号输入a展开8次候选平方比较，输出整数根与余数；输入a按位解释为无符号，输出使用64位。固定次数循环可综合为组合逻辑加输出寄存器，未声称该直展结构是面积最优实现。

RTL 采用同步有效信号和异步低有效复位；空拍保持状态且输出无效。除另有说明外，输入为16位有符号整数，结果为64位有符号整数，测试范围内不截断或饱和。

输出在采样时钟上升沿更新。自检覆盖连续样本、空拍和复位；未进行器件布局布线、时序收敛或功耗验证。

独立自检程序已在 Icarus Verilog 13.0 中实际运行并通过。该结果不包含器件综合、静态时序分析或板级测试。

06
适用范围

整数平方根可用于功率到幅度的转换和固定点归一化。根与余数提供可独立核查的整数证明，适合对舍入方向有严格要求的通路。若幅度分辨率不足，可在平方值中增加偶数个小数位，再执行相同整数算法。

07
工程上需要注意

组合展开路径较长，实际高速设计可按位流水或迭代复用。

负数不在实整数平方根定义域内。

输入小数位为奇数时必须先调整尺度。

内容依据：每日精学第 149 课《逐位恢复整数平方根》。图表沿用原课固定参数数值结果，属于数值验证，不代表设备实测。