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

计算机算术5-整形除法

1.1 基础知识

  1. 英文简写
    以Z/D = (Q, R)为例
    Z = numerator (dividend),分子,被除数
    D = denominator (divisor),分母,除数
    Q = quotient,商
    R = Remainder,余数
  2. 基础算法
    s(j+1)=s(j)−q(k−j)dr(k−j) s^{(j+1)} = s^{(j)} - q_{(k-j)}dr^{(k-j)} s(j+1)=s(j)q(kj)dr(kj)
    其中s(0)=zs^{(0)} = zs(0)=z; k 表示商的位数,sjs^jsj表示部分余数,为了让后续推导顺利进行,这里给sjs^jsj乘上一个rjr^jrj, 上式变为:
    s(j+1)=rs(j)−qk−jdrks^{(j+1)} = rs^{(j)} - q_{k-j}dr^k s(j+1)=rs(j)qkjdrk
  3. robertson图
    下一次余数和当前余数的关系图, 也即s(j+1)和rs(j)s^{(j+1)} 和rs^{(j)}s(j+1)rs(j)的关系图, 核心目的是用来选商的。

在这里插入图片描述

但如上图所示,这样比较大小进行选商太复杂了,如果边界是个常数就好了

1.2 基本分类

  1. 恢复余数除法(Restoring Remainder)、不恢复余数除法(Non-redstoring Remaind)、SRT除法(SRT Division)等算法。
  2. 牛顿迭代法、Goldschmidt算法等算法。

上面两类的区别是,第一类每次迭代都可确定1位的商,并且是基于加法的,即通过加法操作迭代来收敛结果,称作加性归一化的(additive normalization)。

第二类的收敛速度是平方级的,例如可能第i次能收敛n bit的商,第i+1次就能收敛2n bit的商了,这类算法是基于乘法操作的,即通过乘法操作来收敛结果,称作乘性归一化的(multiplicative normalization)。

2. 基本算法

2.1 恢复余数除法-慢速除法

慢速算法通过循环等式,对余数R进行迭代:
Rj+1=B∗Rj−qn−(j+1)∗D R_{j+1} = B * R_j - q_{n-(j+1)}*D Rj+1=BRjqn(j+1)D
其中RjR_jRj是第j个部分余数, B是基;qn−(j+1)q_{n-(j+1)}qn(j+1)是商的第n-(j+1)位,例如第一次迭代(j=0)产生qn−1q_{n-1}qn1,商的最高位。n是商的位数,D是除数.
其中R=RnR_nRn, N = R0R_0R0, 将上面递归计算式带入得到
Rn=2nN−QDR_n = 2^nN-QDRn=2nNQD
恢复余数除法的操作是先更新余数,如果余数小于0,则表明更新余数上的商是错误的,所以我们选择正确的商,并将余数恢复到正数(R+D)
截屏2025-08-05 21.51.07.png

2.2 不恢复余数除法

不恢复余数除法使用数集{-1, 1}, 在这种算法下,每位数字的基是{-1,1}, 而非{0, 1}, 例如-3 = 4’b-111-1.
不恢复余数法的操作是先判断余数大小,如果余数大于0,更新R=2*R-D;如果余数小于0;更新R=2R+D

R := N
D := D << n            -- R and D need twice the word width of N and Q
for i = n − 1 .. 0 do  -- for example 31..0 for 32 bitsif R >= 0 thenq(i) := +1R := 2 * R − Delseq(i) := −1R := 2 * R + Dend if
end
-- Note: N=numerator, D=denominator, n=#bits, R=partial remainder, q(i)=bit #i of quotient.

由于这种方法得到的结果是非标准形式,因此需要对商在最后一步进行转化。转化方式如下:
例如: Q = 111(-1)1(-1)1(-1)
则P = 11101010, N=00010101
Q = P-M = 11010101
最后还需要判断一次余数的正负,如果最后一次余数为负,则Q= Q-1

if R < 0 thenQ := Q − 1R := R + D  -- Needed only if the remainder is of interest.
end if

3. 小结

  1. 除法分为恢复余数除法和不恢复余数除法,两者的基都是非冗余基,其中不恢复余数除法的基可以为负数,因此需要对商进行转换
  2. 在进行除法运算时,我们会先将除数(d)进行左移,使得除数和被除数进行对齐,最后将余数进行右移。

参考链接:
https://www.cnblogs.com/devindd/articles/17633558.html

http://www.lryc.cn/news/610554.html

相关文章:

  • 代码训练营DAY53 第十一章:图论part04
  • bpf系统调用及示例
  • K8S 性能瓶颈排查
  • CVE-2017-8291源码分析与漏洞复现(PIL远程命令执行漏洞)
  • 软件测试中,pytest 框架如何运行上传失败的测试用例?
  • docker国内镜像源列表
  • 软件测试中,pytest 如何运行多个文件或整个目录?
  • Python入门Day15:面向对象进阶(类变量,继承,封装,多态)
  • springboot + maven 使用资源占位符实现动态加载配置文件
  • Modstart 请求出现 Access to XMLHttpRequest at ‘xx‘
  • imx6ull-驱动开发篇9——设备树下的 LED 驱动实验
  • ubuntu的压缩工具zip的安装和使用
  • 【C++】类和对象1
  • 力扣106:从中序与后序遍历序列构造二叉树
  • 「PromptPilot 大模型智能提示词平台」—— PromptPilot × 豆包大模型 1.6:客户投诉邮件高效回复智能提示词解决方案
  • 工业级 CAN 与以太网桥梁:串口服务器CAN通讯转换器深度解析(上)
  • 【科研绘图系列】R语言绘制误差棒图
  • 姜 第四章 线性方程组
  • shmget等共享内存系统调用及示例
  • uniapp 类似popover气泡下拉框组件
  • Maven和Gradle在构建项目上的区别
  • uniapp Android App集成支付宝的扫码组件mPaaS
  • Linux驱动25 --- RkMedia音频API使用增加 USB 音视频设备
  • Linux驱动24 --- RkMedia 视频 API 使用
  • 技术文章推荐|解析 ESA 零售交易方案(技术分析+案例拆解)
  • 基于k8s环境下的pulsar常用命令(下)
  • JavaWeb02——基础标签及样式(黑马视频笔记)
  • 203.移除链表元素 707.设计链表 206.反转链表
  • 8.5 位|归并|递归
  • 腾讯云CodeBuddy AI IDE+CloudBase AI ToolKit打造理财小助手网页