Donald Knuth的“算法D”的Swift实现，用于分割多精度无符号整数，出自The Art of Computer Programming（计算机程序设计艺术）第二卷：Semi-numerical Algorithms（半数值算法），第4.3.3章
我还需要感谢Henry Warren的著作Hacker's Delight（算法心得），并且由于该书的源代码网站hackersdelight.org已失效，因此要感谢github上的这个仓库，它存档了源代码。提供的测试用例不仅节省了我大量创建测试用例的麻烦，而且在思考Warren为何在他的C实现中使用goto时，我意识到我自己的循环实现存在细微错误，从而使我得以修复它，并且它也是一个正式结构化循环不起作用的良好示例。我不得不使用带有break和continue的无限循环来完成相同的事情。如果没有Hacker's Delight代码作为参考，调试它无疑会花费很长时间。
感兴趣的代码位于KnuthAlgorithmD.swift文件中的divideWithRemainder_KnuthD(_:by:quotient:remainder)函数中。为了本仓库的目的，我使其超级通用。这意味着函数签名具有大量的where子句约束，这可能看起来有些令人生畏，但是您可以对任何参数使用任何使用整数索引的随机访问集合，只要它们在包含哪种无符号FixedWidthInteger上达成一致。这应该使您可以轻松地将其放入代码中并开始使用，但是对于实际使用，您将需要对其进行专门化。我将在下面讨论。
请务必阅读该函数的文档注释，因为该算法对您传入的集合的大小施加了约束。被除数必须至少与除数一样大。接收商的集合必须足够大才能容纳它（1 + 被除数和除数之间的大小差异），而余数的集合必须与除数一样大。这些不是我决定的约束。Knuth在The Art of Computer Programming中描述该算法时声明了它们。目的是让您将其作为自己除法的实现来调用，因此您可以安排满足前提条件。确切如何做到这一点取决于您选择如何表示多精度数字。
divideWithRemainder_KnuthD被标记为@inlinable，不是因为我认为编译器实际上会内联它，而是因为它将实现公开在包的外部，以便编译器可以针对您的项目对其进行专门化。我希望这将消除大部分甚至全部通过泛型/协议见证表进行的thunking（间接调用），这些thunking可能会降低其速度。但是，如果您要认真地使用它，则可能需要将代码直接移到您的项目中并手动对其进行专门化。有三个关键的事情需要关注。
如果您有自己的多精度数字类型，则几乎可以肯定已经为数字确定了特定的内置整数类型，并且您不太可能想要使用不同的类型，即使您这样做了，在大多数情况下，使用简单的typealias而不是泛型就可以解决问题。本节过去讨论了如何处理64位数字类型，因为它们是个问题，但我已经修改了代码，现在可以按原样处理它们。
在所有可能性中，您使用一种特定的数字集合来表示您的数字。我所看到的大多数库/包都使用Array。关键是您不需要一个支持同时作为参数传递的四种不同集合类型的函数。您可能只需要针对您已经使用的那个进行专门化。如果您使用数组来存储数字，那么处理ArraySlice也可能是一个好主意。
该函数分配两个数组以在内部进行工作：一个用于保存归一化的除数，另一个用于保存归一化的被除数，该被除数随着算法的进行而转换为归一化的余数。商数直接放置在需要放置的位置，但是在最后，必须对余数进行反归一化并复制到余数参数中。这可以工作，但是速度很慢，并且所需的复制并不是最糟糕的罪魁祸首。每个数组初始化都是堆分配，而堆分配很慢。如果您正在处理具有数千或数百万位数字的数字，那么堆分配的成本可能可以忽略不计，但是如果您使用128位到2048位的数字，则您可以在分配其中一个数组的时间内完成整个除法运算，而该函数分配了两个数组。
当然，有解决此问题的方法。Knuth的算法没有说明分配工作存储的任何内容。它只是在数据所在的位置修改数据，因此如果您可以接受更改输入参数，则根本不需要任何额外的存储空间，尽管参数大小要求会发生变化：被除数需要一个额外的数字空间，以进行归一化时可能发生的溢出。您可以将参数的数量从2个值参数和2个inout参数减少到3个inout参数。
让我们假设更改您的输入参数不是一个选择。您可以将工作缓冲区作为参数传入，因此您可以重新使用它们。这将创建缓冲区的责任提升到了调用者。当然，它也将实现细节暴露给调用者，但是您希望速度快，对吗？
或者，您可以不直接分配数组，而是从数组缓存中请求它们，该缓存只是从先前分配的缓冲区池中分发它们。为了使其能够很好地工作，您可能需要确保在函数末尾将分发的数组返回到缓存，就像将书归还给图书馆一样，以便可以再次将其取出，并且您要确保缓存管理的成本很低。缓存将需要从其池中删除对其分发的数组的所有引用；否则，数组的引用计数将为2，并且一旦该算法对其副本进行修改，它将触发写时复制，这将执行您试图避免的堆分配。
如果您的应用程序具有特殊的点，可以在这些点上安全地一次重置所有临时存储，则可以使用竞技场分配器。这些竞技场分配器通常在高性能游戏中使用，但当然也可以在其他领域中使用。该想法（以视频游戏为例）是，对于每一帧，游戏都必须进行大量的计算。它必须弄清楚哪些东西与哪些东西发生了碰撞，哪些东西被破坏了，哪些东西被创建了，它们移动后的位置等等……这些计算中的许多都需要临时数据结构，例如四叉树，这些四叉树仅在该帧期间相关，甚至仅在帧中的一个计算中相关。分配和释放堆存储的成本很高，因此，游戏程序员使用一个“竞技场”，该“竞技场”在程序启动时分配一个巨大的内存块。它从指向开头的指针开始，然后每当您请求一些临时内存时，它只会返回该指针的副本，然后将其自己的指针增加您请求的字节数（加上用于字对齐的填充）。在该帧期间，竞技场的内部指针仅会增加。它从不尝试模仿“释放”它分发的任何指针。然后在帧的末尾，所有这些临时指针都超出了范围，并且竞技场只是将其内部指针设置回在启动时分配的块的开头，从而使其可以重新用于下一帧。竞技场本身永远不会被释放。
您可以做类似的事情，预先分配一个大数组，该数组比您希望的任何单个计算所需的数组大很多倍，并根据请求分发其切片。您只需要有一些同步点，类似于视频游戏中的帧，在该点您可以安全地重置竞技场，否则您最终将到达竞技场的末尾，这将需要您要么分配更多空间，要么出错。或者，您可以使用UnsafeMutableBufferPointer而不是数组切片，该UnsafeMutableBufferPointer可以像数组一样使用，除了作为指针外，它们具有引用语义，但这对于这种情况是一件好事。为了使其能够很好地工作，您可能希望竞技场使用C的malloc进行分配，这样您就可以在不需要担心将其保持在某些特定的Swift作用域中的有效性的情况下，将指针分发到该块中。只需import Darwin，或者在Linux上，import GLibC，即可调用malloc。在MacOS上，导入Foundation会隐式导入Darwin。Swift的不安全可变指针类型还具有一个静态的allocate方法，您可以用来代替malloc。
就我个人而言，我更喜欢使用运行时堆栈作为临时存储，并将UnsafeBufferPointer和UnsafeMutableBufferPointer用作我的数字集合，至少就缓冲级函数而言，作为参数传入。这样做对我的大数类型施加了一些约束，但也意味着临时存储分配非常快。实际上只是递减堆栈指针寄存器。我必须将对缓冲级数学函数的调用包装在传递给对withUnsafe...系列函数的嵌套调用的闭包中，但是这些闭包在发布版本中被优化掉了。这也意味着我的大数整数不适合用于，例如，查找π的第百万位数字或当前已知数字之外的下一个质数，因为这些应用程序需要任意数量的数字，并且使用我的大数实现，这将很快占用运行时堆栈。此外，我的实现适用于大型固定宽度整数，因此无论如何它们都不能具有运行时确定的数字数。它在许多应用中效果很好，例如安全哈希和加密，这些应用需要比内置类型更大的整数，但又不是太大的整数。
无论如何，要在相对较少的数字的小数字上获得良好的性能（尽管数字比您想象的要多），您需要为工作存储做一些比每次调用都分配数组更好的事情。确切的最佳方法取决于您的Big Number实现的详细信息，甚至可能取决于使用它的应用程序。