biginteger - 如何检查伯尼克尔和齐格勒师的先决条件？

Question

Burnikel 和 Ziegler 用于划分大数的“RecursiveDivision”算法有两个前提条件，其中之一是“商 Q 必须适合 n 位”。如果不先进行除法，您如何知道前提条件是否成立？

Answer 1

据我所知，Burnikel-Ziegler有一个不同的前提条件。重要的是肢体的数量（在我的例子中，肢体是一个 32 位无符号整数）。如果将n肢体除以m肢体，则结果最多为n-m+1肢体（我假设相同的计算对于数字的数量是正确的）。所以这可以给你一个提示。

但在我的BigInteger代码中，前提是：

function ShouldUseBurnikelZiegler(LSize, RSize: Integer): Boolean;
begin
  // http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-November/023493.html
  Result := (RSize >= BigInteger.BurnikelZieglerThreshold) and
            ((LSize - RSize) >= BigInteger.BurnikelZieglerOffsetThreshold);
end;

LSize是RSize肢体中左操作数（除数）的大小和右操作数（除数）的大小。我的代码的阈值是：

const
  BurnikelZieglerThreshold       =   91;
  BurnikelZieglerOffsetThreshold =    5;

您应该（通过实验）找到自己代码的阈值。

在我的代码中，我已经给出了我得到的链接。

---

我知道并不是每个人都熟悉 Pascal（或 Object-Pascal），但我认为上面的代码足够可读，可以理解。