algorithm - 傅里叶除法算法背后的逻辑是什么？

Question

来自维基百科：傅立叶除法。

这是相同的屏幕截图：（ 以全分辨率查看）

这个算法背后的逻辑是什么？

我知道它可以用来划分非常大的数字，但它究竟是如何工作的呢？

Answer 1

这似乎是长除法算法的巧妙变换。聪明的部分似乎是他们只对第一个“数字” a1 使用除法运算，并且通过在下一步中通过减去它们来避免必须以相同的方式使用其他 a(x)中间余数的乘积（对部分商）。

这可以有效地完成并且它总是有效的可能是因为“数字”（在这种情况下以 100 为底）不是真正的数字，并且可以合理地假设值都大于它们的底数（即超过 100 ) 甚至小于零。这允许在将每个“数字”应用于运算的时间上具有更大的灵活性，例如，将除数 (a(x>1)) 的次级数字的应用推迟到从前一步除以 a(1)，这反过来又允许将它们用作乘积减法，而不是除法运算。

Answer 2

这是一个非常聪明的算法。我无法想象 ol' JF 是如何设法得到它的，因为即使你知道它存在，也很难看到重复关系。在我看来，他正式制定了一种他用来做除法的方法——在数字计算器之前的时代，他一定已经手工完成了大量的计算，而且他可能更喜欢精确而不是使用计算尺，只是为了确定。

确实，在标准长除法算法的开始，人们可以隐约看到该方法的轮廓，但这是唯一的线索。你可以在没有看到它的情况下长时间地努力寻找这种重复。涉及的数字太多了——看这些关系会让人感到困惑。

通过研究标准乘法算法中的数据流可以获得另一种直觉。如果你把它写在计算机硬件中，你可以看到一个 8 位乘法单元的方阵将两个 32 位数字沿它们的底部和右侧排列，然后将数据向上和向左移动，从顶部边缘退出64 位答案中的数组。最左边的单元提供乘积的前两位（8 位）数字，使用被乘数的高位数字并从数组的其余部分向右进位。好的？好吧，想象一下反向运行的数组将沿顶部边缘的 64 位除数和一个 32 位除数作为输入，例如沿着数组的右手边缘。然后它沿底部边缘输出 32 位商（也需要生成余数......忘记它了）。

哇！那只是第一个数字输出。这只是一个开始。傅立叶的天才在于看到如何输入累加的余数，以将输入限制为三个（比如 8 位）数字，而修改后的每个单元的输出只有两个（比如 8 位）数字反向运行的乘法数组（我们现在可以称为除法数组）。

当然，这就是我们可以在计算机 ALU 中进行硬件除法的方式，无需微码。

至少，我认为这种方法适用于已经避开微码而有利于数十亿晶体管的地方。我不知道最新 CPU 的内部，但它们有晶体管要烧。