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

Question

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

以下是同样的屏幕截图： (查看完整分辨率)

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

我知道它可以用于除以非常大的数字，但它究竟是如何工作的？

- Lazer

---

这段内容与编程无关，您可能在数学论坛上获得更好的结果。事实上，在计算机中执行除法时，您不会使用像这样的算法（我认为…）。但我发现有趣的是，“Fourier division”的第三个谷歌搜索结果是“ESPN Search: fourier division”。 - Kip

尝试在sosmath.com论坛上提问。 - Sam Becker

FYI：算法=与编程有关。 - RBarryYoung

@Kip，这是计算机用来分割大数的算法。 - Lazer

Answer 1

这是一个非常聪明的算法。我无法想象老JF是如何掌握这个算法的，因为即使你知道它的存在，递归关系也非常难以看出。在我看来，他形式化了一种他用来手算除法的方法——在数字计算器出现之前，他必须手算大量的计算，而且他可能更喜欢精确计算而不是使用滑尺。

的确，人们可以在标准长除法算法的开头模糊地看到该方法的轮廓，但那是唯一的线索。你可能需要长时间搜索才能找到这个递归关系。涉及到很多数字，看起来很混乱。

通过研究标准乘法算法中数据的流动，还可以获得另一种直觉。如果你将其写成计算机硬件形式，你会发现一个8位乘法单元的方形阵列会将两个32位数字沿着它们的底部和右侧排列，并将数据向上和向左移动，在阵列的顶部边缘输出一个64位答案。最上面最左边的单元使用乘数的顶部数字和来自其右侧阵列的进位，提供了产品的顶部两个（8位）数字。好了？那么，想象一下这个阵列倒着运行，以便将64位被除数沿着顶部边缘和32位除数（比如沿右边缘）作为输入。然后它在底部边缘输出32位商（还需要生成余数..暂时不要考虑）。

现在，阵列中的最上面左边的单元从阵列的顶部接收被除数的前两位数字，从阵列的右边接收除数的顶部数字，并向下（进入阵列）发出商的顶部数字（并从底部退出），并向右（进入阵列）发出余数。

哇！这只是第一个数字输出。这才刚刚开始。傅里叶的天才在于看到了如何输入累积余数，以便将输入限制在仅三个（比如8位）数字，并且对于反转运行的修改乘法阵列中的每个单元，输出仅为两个（比如8位）数字（我们现在可以称之为除法阵列）。

当然，这就是我们如何在硬件中进行除法运算，无需微码，在计算机ALU中。至少，在微码被避免使用而更多的晶体管被使用的情况下，我认为这种方法被使用。我不知道最新CPU的内部情况，但它们有很多晶体管可以使用。

- Peter Breuer

Answer 2

这似乎是长除法算法的巧妙变换。其中巧妙之处似乎在于只使用第一个“数字”a1进行除法运算，并通过在下一步将它们减去（对偏余数）的积来避免以同样的方式使用其他a(x)。这可以有效地完成，并且总是有效的，可能是因为“数字”（在此情况下为基数100）不是真正的数字，并且可以合法地承担大于其基数（即超过100）甚至小于零的值。这使得在操作的每个“数字”应用时间上具有更大的灵活性，例如推迟除数的次要数字（a(x>1))的应用，直到从前一步的a(1)除法中创建了部分商，这反过来又允许将它们作为产品减法而不是除法运算应用。

- RBarryYoung