傅立叶分裂算法背后的逻辑是什么？

Question

来自维基百科:傅立叶分部.

这是相同的截图: (以全分辨率查看)

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

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

Answer 1

这似乎是Long Division算法的巧妙转换.聪明的部分似乎是他们只使用第一个"数字"a1的除法运算,并且避免必须以相同的方式使用另一个a(x),通过减去它们在下一步中应用它们来自临时余数的产品(相对于部分商).

这可以有效地完成并且它始终有效可能是由于"数字"(在这种情况下为基数100)不是真实数字并且可以合法地假设两者都大于其基数(即,超过100)的事实. )甚至小于零.这允许在操作中应用每个"数字"的时间具有更大的灵活性,例如,推迟除数的次要数字的应用(a(x> 1)),直到从部分商中创建部分商数.先前步骤除以(1),它反过来允许它们作为乘积减法而不是除法运算.

Answer 2

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

确实，人们可以在标准长除法算法的开头隐约看到该方法的轮廓，但这是唯一的线索。你可能会费尽心思地寻找这种重复现象，却看不到它。涉及的数字太多了——查看这些关系会让人感到困惑。

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

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

当然，这就是我们如何在计算机 ALU 中在硬件中进行除法运算，而不需要微代码。

至少，我认为这种方法是在避开微代码而采用数十亿个晶体管的情况下使用的。我不了解最新 CPU 的内部结构，但它们有需要烧毁的晶体管。