傅氏除法的逻辑是什么?

这似乎是长除法算法的巧妙转换。聪明的部分似乎是,它们只对第一个“数字”a1使用除法运算,并且通过在下一步中从中间余数中减去它们的乘积(与部分商相乘),避免以同样的方式使用另一个a(x)。

这可能是有效的,并且它总是有效的,这可能是因为“数字”(基数100,在这种情况下)不是真的数字,并且可以合法地假设值大于基(大于100),甚至小于零。这允许在将每个“数字”应用于操作的时间上具有更大的灵活性,例如,将除数(a(x>1))的二级数字的应用推迟到从上一步骤的除法(1)创建部分商之后,这又允许它们作为乘积减法应用,而不是除法运算。

这是一个非常聪明的算法。我无法想象O'JF是如何获得它的,因为即使你知道它存在的时候,它的关系也是非常难以看到的。在我看来,他把他用来做除法的方法正式化了,他必须在数字计算器的年代之前用手工做大量的计算,而且他可能更喜欢精确地使用一个尺尺,这是可以肯定的。

的确,在标准长除法算法的开始,人们可以模糊地看到该方法的轮廓,但这是唯一的线索。你可以长时间地努力寻找这种复发,却看不到它。涉及的数字太多了,看看这些关系会让人感到困惑。

从研究标准乘法算法中的数据流中可以获得另一种直觉。如果你把它写在计算机硬件中,你可以看到一个8位乘法单元的正方形阵列,沿着它们的底部和右侧排列两个32位数字,并将数据向上和向左移动,以64位的答案出现在阵列的上边。最左上角的单元使用被乘数的前两位数字传递乘积的前两位(8位)数字,并从数组的其余部分向右进位。好啊?好吧,假设数组反向运行,将沿顶部边缘的64位divident和32位除数作为输入,例如沿数组的右侧边缘。然后它沿着下边缘输出32位商(还需要生成余数)。忘了给妈妈买吧)。现在数组中最左上角的单位从数组的顶部获取被除数的前两位,从数组的右侧获取除数的前两位,并将商的顶部数字向下发射到数组中(并从底部发射出去),将余数向右发射到数组中。

唷!这只是第一位数的输出。这只是个开始。傅立叶的天才在于观察如何在累加的剩余物中进食,以保持输入仅限于三(即8位)数字,在反向乘法的乘法数组中,每个单元只有两个(即8位)数字(我们现在可以称之为除法数组)。

当然,在计算机ALU中,我们可以在硬件上做除法,而不需要微码。

至少,我认为这种方法是用在微代码已经被抛弃,转而使用几十亿个晶体管的地方。我不知道最新CPU的内部,但它们有晶体管要烧。