MIPS：除法算法（除 IEEE-754 格式的有效数字）对最后 4-5 位 (LSB) 给出错误答案
MIPS: Division algorithm (Dividing significands of IEEE-754 format) gives incorrect answer for the last 4-5 bits (LSB)
对于除数>被除数的情况，计算出的尾数最后4-5个最低有效位给出了错误的结果。
我正在尝试除以两个 IEEE-754 浮点数的 significands/mantissa。我用过这个除法算法
当除数>被除数时，尾数归一化，但最后 4-5 位仍然不正确。
除法算法：#将除数尾数（$a0）除以除数尾数（$a1）进行 25 次迭代#
#Returns $v0 中的商值#
addi $sp, $sp, -12 #Decrement in $sp (Stack Pointer)
sw $s0, 0($sp) #Pushing $s0 into Stack
sw $ra, 4($sp) #Pushing $ra into Stack (Function Call Exists)
sw $s1,8($sp) #Pushing $s1 into stack
move $t0, $a0 #$t0 = Mantissa of Dividend/Remainder
move $t1, $a1 #$t1 = Mantissa of Divisor
add $s0, [=10=], [=10=] #$s0 = Initialization
add $v1, [=10=], [=10=] #$v1 = 0 (Displacement of Decimal Point Initialized)
addi $s1,[=10=],1 #$s1 = 1 (initialize loop variable to 1)
add $t3,[=10=],33
loop:
beq $t1, [=10=], check #If Divisor = 0, Branch to check
sub $t0, $t0, $t1 #Dividend = Dividend - Divisor
sll $s0, $s0, 1 #Quotient Register Shifted Left by 1-bit
slt $t2, $t0, [=10=]
bne $t2, [=10=], else #If Dividend < 0, Branch to else
addi $s0, $s0, 1 #Setting Quotient LSb to 1
j out
else: add $t0, $t0, $t1 #Restoring Dividend Original Value
out: srl $t1, $t1, 1 #Divisor Register Shifted Right by 1-bit
j loop
check: slt $t2, $a0, $a1 #If Dividend < Divisor, Call Function 'Normalization'
beq $t2, [=10=], exit #If Dividend > Divisor, Branch to exit
move $a0, $s0 #$a0 = Quotient
jal Normalization #Function Call
j return
exit: move $v0, $s0 #$v0 = Calculated Mantissa
return: lw $ra, 4($sp) #Restoring $ra
lw $s0, 0($sp) #Restoring $s0
lw $s1, 8($sp) #restoring $s1
addi $sp, $sp, 8 #Increment in $sp (Stack Pointer)
jr $ra #Return
归一化：#归一化尾数（在$a0中）并计算小数点移动的小数位#
#Returns:
# i) $v0 = 归一化尾数 #
# ii) $v1 = 小数位数#
lui $t0, 0x40 #$t0 = 0x40 (1 at 23rd-bit)
addi $t2, [=11=], 1 #$t2 = 1 (Initialization)
loop2: and $t1, $a0, $t0 #Extracting 23rd-bit of Mantissa
bne $t1, [=11=], else2 #If 23rd-bit = 1; Branch to else2
addi $t2, $t2, 1 #Increment in Count of Decimal Places Moved
sll $a0, $a0, 1 #Mantissa Shifted Left (To Extract Next Bit)
j loop2
else2: sll $a0, $a0, 1 #Setting 24th-bit = 1 (Implied)
move $v0, $a0 #$v0 = Normalized Mantissa
move $v1, $t2 #$v1 = Displacement of Decimal Point
jr $ra #Return
比如我预计2.75/6.355的输出是00111110110111011000111011001110但实际输出是00111110110111011000111011010110.
你的算法不正确。
恢复 division 的正确算法是
qu=0
rem=dividend
repeat N times
rem = rem - divisor
if rem < 0
rem = rem + divisor
qu = (qu<<1)
else
qu = (qu<<1) + 1
end
rem = rem << 1
end
而你的是
qu=0
rem=dividend
repeat N times
rem = rem - divisor
if rem < 0
rem = rem + divisor
qu = (qu<<1)
else
qu = (qu<<1) + 1
end
divisor = divisor >> 1 // instead of left shift remainder
end
由于算法只依赖于divisor和rem的比较，所以看起来相当于右移divisor或左移rem。但事实并非如此。
当右移 divisor 时，您丢失了 divisor 的最低有效位。
这可能会影响比较，从而影响商数。
如果你打印余数，你会发现它有很大的影响，它的值可能与正确结果相差 2 倍。
余数乘以2好像很危险，可能会溢出。但是如果我们看一下算法，我们可以看到它不会发生。
最初 dividend 和 divisor 是一些 FP 的尾数，因此 1 ≤ divisor，dividend < 2 并且同样适用于最初是 a 的 rem dividend 的副本。请注意，这意味着 rem<2*div
现在，我们进行第一个计算步骤
⚫ 如果 rem < div，那么我们将它乘以 2，并且 rem(=2*rem)<2*div.
⚫ 如果 rem ≥ div，那么我们计算 rem−div 并将其乘以 2.
由于最初 rem < 2*div，rem(=2*(rem− div))<2*(2*div− div)，并且 属性 rem<2*div 仍然成立。
所以在每一步我们总是有 属性 rem<2*div 并且，假设 2*div 可以编码，这确保 rem 永远不会溢出。
在实现方面，您可以将这些数字编码在整数寄存器的 24 LSB 上。基本上已经足够了，因为精度保持不变。
在您的实现中，您循环了 32 次。如果想把结果写成IEEE尾数，那是没用的，可以减少迭代次数。循环
就足够了
24倍（尾数大小）
+ 1（如果 dividend < divisor，第一位将为 0，但第二位保证为 1）
如果要对结果进行舍入，则必须执行两个额外的步骤来获取舍入位和保护位。经过这两个计算步骤，如果余数≠0，则将粘性位设置为1，否则将其设置为0。然后按照通常的规则进行舍入。
我。以您开始的形式描述除法算法本身（据我所知，汇编代码也是如此）缺少主要部分。在准备 运行 除法循环时，当您在每次迭代中将除数右移 1 位时，您最初应该尽可能将其左移并且有用。
让我用十进制数解释一下：假设您在 6 位机器中将 10001 除以 73（所以这是 010001 除以 000073）。您应该将 73 向左移动，直到它停止以适合（因此最大移动为 4，移动的除数为 730000）或它的最高有效位 (MSD) 位置高于股息的 MSD（因此，我们可以停在 73000）。那么，循环就是运行和
- shifted_divisor = 73000，移位 = 3
- shifted_divisor = 7300，移位 = 2
- shifted_divisor = 730，移位 = 1
- shifted_divisor = 73，移位 = 0
（十进制时，每次移位都要嵌套循环减法；二进制则不需要。）
如果您将 73 右移更多，您将丢失除数中的有效数字，因此最终的商将大于精确的一个。
您可以无条件地将最大宽度左除数移位（730000，shift=4），但这会浪费CPU个周期。如果CPU有CountLeadingZeros操作，可以节省时间
二．第二个主要时刻是你正在划分从 floating-point 数字中得到的尾数。这意味着，在两个标准化数字的最典型情况下，被除数和除数的 MSB 将相同，您将只得到商的 2 个变体 - 0 和 1。（对于 IEEE binary32，这是设置了第 23 位并且股息和除数都在 8388608..16777215 范围内。）
要得到更多的实数，你必须进行长除法。 （请参阅下文以了解更经济的方法；现在，只需与教科书除法进行比较。）对于 IEEE binary32，这意味着在最后舍入之前至少获得 27 个商数（24 个结果尾数 + 守卫 + 舍入 + 粘性）。如上所述，将被除数左移 27 位，然后在 28 个周期内继续将 51 位被除数除以 24 位除数。
@AlainMerigot 描述的版本与我描述的基本相同 - 您仍然计算 (dividend<<quotient_width)/divisor，但方式不太明显。如果 left-shift 余数除以 1，这可能与 right-shift 除数除以 1 相同，前提是没有数据丢失。因此，第一次迭代（第 0 次）比较相等的位置并提供结果的 MSB，但此时它位于第 0 位；然后，您 "activate" 在每次迭代中多一点余数。这允许避免 double-word 操作。在这个算法中，如果你需要最后的余数，它应该通过按迭代次数右移来恢复；但是浮动除法本身不需要它。
但是：为了使其正常工作，您应该从一开始就正确对齐股息和除数。在十进制示例中，这意味着您不应该以 divident=10001, divisor=73 开始，而应该以 dividend=10001, divisor=73000 开始。如果在获取整数值之前对源尾数进行了归一化，则自动满足。否则，需要额外的努力，它们实际上与我描述的教科书除法的除数转换相同。 （看起来这就是为什么英特尔 CPUs 几十年来一直遭受无限非规范处理时间的困扰；））
对于除数>被除数的情况，计算出的尾数最后4-5个最低有效位给出了错误的结果。
我正在尝试除以两个 IEEE-754 浮点数的 significands/mantissa。我用过这个除法算法
当除数>被除数时，尾数归一化，但最后 4-5 位仍然不正确。
除法算法：#将除数尾数（$a0）除以除数尾数（$a1）进行 25 次迭代# #Returns $v0 中的商值#
addi $sp, $sp, -12 #Decrement in $sp (Stack Pointer)
sw $s0, 0($sp) #Pushing $s0 into Stack
sw $ra, 4($sp) #Pushing $ra into Stack (Function Call Exists)
sw $s1,8($sp) #Pushing $s1 into stack
move $t0, $a0 #$t0 = Mantissa of Dividend/Remainder
move $t1, $a1 #$t1 = Mantissa of Divisor
add $s0, [=10=], [=10=] #$s0 = Initialization
add $v1, [=10=], [=10=] #$v1 = 0 (Displacement of Decimal Point Initialized)
addi $s1,[=10=],1 #$s1 = 1 (initialize loop variable to 1)
add $t3,[=10=],33
loop:
beq $t1, [=10=], check #If Divisor = 0, Branch to check
sub $t0, $t0, $t1 #Dividend = Dividend - Divisor
sll $s0, $s0, 1 #Quotient Register Shifted Left by 1-bit
slt $t2, $t0, [=10=]
bne $t2, [=10=], else #If Dividend < 0, Branch to else
addi $s0, $s0, 1 #Setting Quotient LSb to 1
j out
else: add $t0, $t0, $t1 #Restoring Dividend Original Value
out: srl $t1, $t1, 1 #Divisor Register Shifted Right by 1-bit
j loop
check: slt $t2, $a0, $a1 #If Dividend < Divisor, Call Function 'Normalization'
beq $t2, [=10=], exit #If Dividend > Divisor, Branch to exit
move $a0, $s0 #$a0 = Quotient
jal Normalization #Function Call
j return
exit: move $v0, $s0 #$v0 = Calculated Mantissa
return: lw $ra, 4($sp) #Restoring $ra
lw $s0, 0($sp) #Restoring $s0
lw $s1, 8($sp) #restoring $s1
addi $sp, $sp, 8 #Increment in $sp (Stack Pointer)
jr $ra #Return
归一化：#归一化尾数（在$a0中）并计算小数点移动的小数位# #Returns: # i) $v0 = 归一化尾数 # # ii) $v1 = 小数位数#
lui $t0, 0x40 #$t0 = 0x40 (1 at 23rd-bit)
addi $t2, [=11=], 1 #$t2 = 1 (Initialization)
loop2: and $t1, $a0, $t0 #Extracting 23rd-bit of Mantissa
bne $t1, [=11=], else2 #If 23rd-bit = 1; Branch to else2
addi $t2, $t2, 1 #Increment in Count of Decimal Places Moved
sll $a0, $a0, 1 #Mantissa Shifted Left (To Extract Next Bit)
j loop2
else2: sll $a0, $a0, 1 #Setting 24th-bit = 1 (Implied)
move $v0, $a0 #$v0 = Normalized Mantissa
move $v1, $t2 #$v1 = Displacement of Decimal Point
jr $ra #Return
比如我预计2.75/6.355的输出是00111110110111011000111011001110但实际输出是00111110110111011000111011010110.
你的算法不正确。
恢复 division 的正确算法是
qu=0
rem=dividend
repeat N times
rem = rem - divisor
if rem < 0
rem = rem + divisor
qu = (qu<<1)
else
qu = (qu<<1) + 1
end
rem = rem << 1
end
而你的是
qu=0
rem=dividend
repeat N times
rem = rem - divisor
if rem < 0
rem = rem + divisor
qu = (qu<<1)
else
qu = (qu<<1) + 1
end
divisor = divisor >> 1 // instead of left shift remainder
end
由于算法只依赖于divisor和rem的比较，所以看起来相当于右移divisor或左移rem。但事实并非如此。
当右移 divisor 时，您丢失了 divisor 的最低有效位。
这可能会影响比较，从而影响商数。
如果你打印余数，你会发现它有很大的影响，它的值可能与正确结果相差 2 倍。
余数乘以2好像很危险，可能会溢出。但是如果我们看一下算法，我们可以看到它不会发生。
最初 dividend 和 divisor 是一些 FP 的尾数，因此 1 ≤ divisor，dividend < 2 并且同样适用于最初是 a 的 rem dividend 的副本。请注意，这意味着 rem<2*div
现在，我们进行第一个计算步骤
⚫ 如果 rem < div，那么我们将它乘以 2，并且 rem(=2*rem)<2*div.
⚫ 如果 rem ≥ div，那么我们计算 rem−div 并将其乘以 2.
由于最初 rem < 2*div，rem(=2*(rem− div))<2*(2*div− div)，并且 属性 rem<2*div 仍然成立。
所以在每一步我们总是有 属性 rem<2*div 并且，假设 2*div 可以编码，这确保 rem 永远不会溢出。
在实现方面，您可以将这些数字编码在整数寄存器的 24 LSB 上。基本上已经足够了，因为精度保持不变。
在您的实现中，您循环了 32 次。如果想把结果写成IEEE尾数，那是没用的，可以减少迭代次数。循环
就足够了
24倍（尾数大小）
+ 1（如果 dividend < divisor，第一位将为 0，但第二位保证为 1）
如果要对结果进行舍入，则必须执行两个额外的步骤来获取舍入位和保护位。经过这两个计算步骤，如果余数≠0，则将粘性位设置为1，否则将其设置为0。然后按照通常的规则进行舍入。
我。以您开始的形式描述除法算法本身（据我所知，汇编代码也是如此）缺少主要部分。在准备 运行 除法循环时，当您在每次迭代中将除数右移 1 位时，您最初应该尽可能将其左移并且有用。
让我用十进制数解释一下：假设您在 6 位机器中将 10001 除以 73（所以这是 010001 除以 000073）。您应该将 73 向左移动，直到它停止以适合（因此最大移动为 4，移动的除数为 730000）或它的最高有效位 (MSD) 位置高于股息的 MSD（因此，我们可以停在 73000）。那么，循环就是运行和
- shifted_divisor = 73000，移位 = 3
- shifted_divisor = 7300，移位 = 2
- shifted_divisor = 730，移位 = 1
- shifted_divisor = 73，移位 = 0
（十进制时，每次移位都要嵌套循环减法；二进制则不需要。）
如果您将 73 右移更多，您将丢失除数中的有效数字，因此最终的商将大于精确的一个。
您可以无条件地将最大宽度左除数移位（730000，shift=4），但这会浪费CPU个周期。如果CPU有CountLeadingZeros操作，可以节省时间
二．第二个主要时刻是你正在划分从 floating-point 数字中得到的尾数。这意味着，在两个标准化数字的最典型情况下，被除数和除数的 MSB 将相同，您将只得到商的 2 个变体 - 0 和 1。（对于 IEEE binary32，这是设置了第 23 位并且股息和除数都在 8388608..16777215 范围内。）
要得到更多的实数，你必须进行长除法。 （请参阅下文以了解更经济的方法；现在，只需与教科书除法进行比较。）对于 IEEE binary32，这意味着在最后舍入之前至少获得 27 个商数（24 个结果尾数 + 守卫 + 舍入 + 粘性）。如上所述，将被除数左移 27 位，然后在 28 个周期内继续将 51 位被除数除以 24 位除数。
@AlainMerigot 描述的版本与我描述的基本相同 - 您仍然计算 (dividend<<quotient_width)/divisor，但方式不太明显。如果 left-shift 余数除以 1，这可能与 right-shift 除数除以 1 相同，前提是没有数据丢失。因此，第一次迭代（第 0 次）比较相等的位置并提供结果的 MSB，但此时它位于第 0 位；然后，您 "activate" 在每次迭代中多一点余数。这允许避免 double-word 操作。在这个算法中，如果你需要最后的余数，它应该通过按迭代次数右移来恢复；但是浮动除法本身不需要它。
但是：为了使其正常工作，您应该从一开始就正确对齐股息和除数。在十进制示例中，这意味着您不应该以 divident=10001, divisor=73 开始，而应该以 dividend=10001, divisor=73000 开始。如果在获取整数值之前对源尾数进行了归一化，则自动满足。否则，需要额外的努力，它们实际上与我描述的教科书除法的除数转换相同。 （看起来这就是为什么英特尔 CPUs 几十年来一直遭受无限非规范处理时间的困扰；））