如何检查 Burnikel 和 Ziegler 师的前提条件？

Question

Burnikel 和 Ziegler 的 "RecursiveDivision" 大数除法算法有两个先决条件，其中之一是 "the Quotient Q must fit into n digits."如果不先进行除法，你怎么知道先决条件是否成立？

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;

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

在我的代码中，我已经给出了link where I got that。

我知道不是每个人都熟悉 Pascal（或 Object-Pascal）这一事实，但我认为上面这段代码的可读性足以理解这个想法。

如何检查 Burnikel 和 Ziegler 师的前提条件？

How to check precondition to Burnikel and Ziegler division?

biginteger

preconditions