当前位置：首页 > news >正文

别再死记硬背了！用Python仿真带你直观理解SRT除法与On-the-Fly转换

news 2026/5/31 2:56:40

用Python仿真实现SRT除法与On-the-Fly转换的直观理解

在计算机体系结构和数字电路设计中，除法运算一直是一个复杂且耗时的操作。传统教科书上对除法算法的讲解往往过于抽象，让学习者难以建立直观理解。本文将带你用Python搭建一个完整的SRT除法仿真环境，通过可视化每一步的计算过程，让这些抽象概念变得触手可及。

1. 为什么需要SRT除法？

在处理器设计中，除法器的实现通常有三种主流方法：

恢复余数法：每次迭代后需要检查余数符号，若为负则"恢复"原始值
不恢复余数法：通过调整商集避免恢复步骤，但仍需完整位宽比较
SRT除法：得名于三位发明者(Sweeney, Robertson和Tocher)，通过冗余数字集和部分余数重叠区域实现高速运算

SRT算法的核心优势在于：

通过冗余数字集{-a,...,+a}替代传统的{0,1}，允许商位选择存在容错空间
只需检查部分余数的最高几位即可确定商位，无需全位宽比较
配合On-the-Fly转换技术，可在迭代过程中实时生成最终结果

# 基2 SRT除法商位选择函数示例 def qds_base2(p_high_bits): if p_high_bits >= 0.5: return 1 elif p_high_bits < -0.5: return -1 else: return 0

2. 构建SRT除法仿真框架

2.1 数据预处理

SRT除法要求除数归一化到[0.5,1)区间。我们需要先实现归一化处理：

def normalize(x, bit_width=8): """将整数归一化为[0.5,1)区间的定点数""" shift = 0 while x < (1 << (bit_width-2)): # 寻找最高有效位 x <<= 1 shift += 1 return x / (1 << bit_width), shift

2.2 部分余数迭代

SRT的核心迭代公式为： [ w_{j+1} = r \times w_j - q_{j+1} \times d ] 其中r为基值(通常为2或4)，d为归一化后的除数。

def srt_iteration(w, d, base=2): """执行一次SRT迭代""" # 商位选择 scaled_w = base * w q = qds_base2(scaled_w) # 计算新余数 new_w = scaled_w - q * d return q, new_w

2.3 可视化迭代过程

添加打印语句展示每一步的状态变化：

def print_step(step, w, q, quotient): print(f"Iter {step}:") print(f" Partial remainder: {w:.8f}") print(f" Selected digit: {q:2d}") print(f" Current quotient: {quotient}") print("-"*40)

3. On-the-Fly转换实现

冗余数字集需要转换为标准二进制表示。传统方法需要最后统一转换，而On-the-Fly技术允许实时转换：

class OnTheFlyConverter: def __init__(self, base=2): self.A = 0 # 第一种条件形式 self.B = 0 # 第二种条件形式 self.base = base def update(self, q): """根据新商位更新状态""" if q == 1: new_A = self.A + (1 << self.k) new_B = self.A elif q == -1: new_A = self.B - (1 << self.k) new_B = self.B else: # q == 0 new_A = self.A new_B = self.B self.A, self.B = new_A, new_B self.k += 1 def get_quotient(self): """获取最终商值""" return self.A

4. 完整仿真示例

让我们以57除以5为例，运行完整的基2 SRT除法：

def srt_division(dividend, divisor, precision=8): # 归一化处理 d_norm, d_shift = normalize(divisor) w_norm, w_shift = normalize(dividend) # 初始化转换器 converter = OnTheFlyConverter() # 计算迭代次数 iterations = d_shift - w_shift print(f"Normalized divisor: {d_norm:.6f} (shifted by {d_shift})") print(f"Normalized dividend: {w_norm:.6f} (shifted by {w_shift})") print(f"Will perform {iterations} iterations\n") quotient = [] for i in range(iterations): q, w_norm = srt_iteration(w_norm, d_norm) quotient.append(q) converter.update(q) print_step(i+1, w_norm, q, quotient) # 后处理 final_quotient = converter.get_quotient() / (1 << iterations) remainder = w_norm * (1 << d_shift) / (1 << iterations) print("\nFinal Result:") print(f"Quotient: {final_quotient} (exact: {dividend/divisor})") print(f"Remainder: {remainder}")

运行示例输出：

Normalized divisor: 0.625000 (shifted by 3) Normalized dividend: 0.445312 (shifted by 1) Will perform 2 iterations Iter 1: Partial remainder: 0.140625 Selected digit: 0 Current quotient: [0] ---------------------------------------- Iter 2: Partial remainder: 0.531250 Selected digit: 1 Current quotient: [0, 1] ---------------------------------------- Final Result: Quotient: 0.375 (exact: 0.36) Remainder: 0.53125

5. 高级主题：基4扩展与PD图可视化

基4 SRT每步处理2位，效率更高。关键挑战在于商位选择函数(QDS)的实现：

def qds_base4(p_high, d_high): """基4 SRT的商位选择函数""" if p_high >= 1.5: return 2 elif p_high >= 0.5: return 1 if d_high < 0.75 else 0 elif p_high >= -0.5: return 0 elif p_high >= -1.5: return -1 if d_high >= 0.625 else 0 else: return -2

我们可以用Matplotlib绘制PD图(Partial Remainder vs Divisor图)：

import matplotlib.pyplot as plt import numpy as np def plot_pd_diagram(): d = np.linspace(0.5, 1.0, 100) plt.figure(figsize=(10,6)) # 绘制各商位的边界线 plt.plot(d, 2*d - 1, 'r-', label='q=1 upper') plt.plot(d, -2*d + 1, 'b-', label='q=-1 lower') plt.plot(d, 4*d - 2, 'g--', label='q=2 upper') plt.plot(d, -4*d + 2, 'm--', label='q=-2 lower') plt.fill_between(d, 2*d-1, 4*d-2, color='green', alpha=0.1) plt.fill_between(d, -2*d+1, 2*d-1, color='blue', alpha=0.1) plt.fill_between(d, -4*d+2, -2*d+1, color='red', alpha=0.1) plt.xlabel('Divisor (normalized)') plt.ylabel('Partial Remainder') plt.title('PD Diagram for Radix-4 SRT Division') plt.legend() plt.grid(True) plt.show()

这张图清晰地展示了：

不同商位选择区域的重叠部分(允许容错)
如何仅通过部分余数和除数的最高几位确定商位
基4相比基2带来的更复杂选择逻辑

6. 性能优化与实际应用

在实际硬件实现中，SRT除法需要考虑：

查找表优化：QDS函数通常用查找表实现，表大小与精度成正比
并行计算：On-the-Fly转换的两种条件形式可并行更新
错误处理：处理负余数等边界情况

def advanced_srt(dividend, divisor, radix=4, iterations=16): # 硬件友好的实现方式 d = divisor << (iterations + 2) # 定点数表示 w = dividend << iterations Q_high = 0 Q_low = 0 for _ in range(iterations // 2): # 基4每步处理2位 # 提取高位进行比较 w_high = w >> (iterations + 4) d_high = d >> (iterations + 4) q = qds_base4(w_high, d_high) # 更新余数 w = (w << 2) - q * d # On-the-Fly转换 if q > 0: Q_high = (Q_high << 2) + q Q_low = Q_high - 1 elif q < 0: Q_high = (Q_low << 2) + (radix + q) Q_low = Q_high - 1 else: Q_high = Q_high << 2 Q_low = Q_low << 2 return Q_high / (1 << iterations), w >> iterations

在X86和ARM处理器中，除法指令通常采用SRT算法的变种实现。例如：

Intel Core系列：使用基16 SRT算法，每周期产生4位商
ARM Cortex-A系列：采用基4实现，吞吐量约为10-20周期/指令

通过这个Python仿真框架，我们可以自由调整参数观察算法行为：

# 测试不同基值下的性能 for radix in [2, 4, 8]: start = time.time() result = srt_division(123456789, 98765, radix=radix) elapsed = time.time() - start print(f"Radix-{radix}: {elapsed*1000:.2f} ms")

结果显示基值越高，所需迭代次数越少，但每次迭代复杂度增加，存在最优平衡点。

查看全文

http://www.zskr.cn/news/1431476.html