了解长除法算法

Question

我在 SphinxAPI class 中为 PHP 创建了一些长除法代码，它将 64 位 int 分成两个 32 位整数，并在 bc 库不可用时在 32 位机器上使用：

    // x32, no-bcmath
    $p = max(0, strlen($v) - 13);
    $lo = abs((float)substr($v, $p));
    $hi = abs((float)substr($v, 0, $p));

    $m = $lo + $hi*1316134912.0; // (10 ^ 13) % (1 << 32) = 1316134912
    $q = floor($m/4294967296.0);
    $l = $m - ($q*4294967296.0);
    $h = $hi*2328.0 + $q; // (10 ^ 13) / (1 << 32) = 2328

能不能告诉我，这里用的是什么长除法算法（作者在评论里叫"fun"）？还是常用算法的表达式改写了？

Answer 1

我已经制作了新版本的算法扩展来回答评论。

新版本

作为输入，我们有一个 64 位整数 v，表示为一串十进制数字。我们需要把它打包成two's complement format。结果有两部分h和l（64位整数的高32位和低32位部分）

怎么做？

v = h*2^32 + l。表示h是多少whole2^32包含v：h=floor(v/2^32)。 l 是剩余的部分：l = v % 2^32。我们需要计算它们。

我们需要一个数据类型来进行计算。在 PHP 上，我们有 float 数据类型。它有 a mantissa of 52 bits。尾数可以表示 0 到 4*10^15 范围内的整数加上一些东西（以及负方向几乎相同的范围）。 float在32位PHP平台上可以表示最大范围的数字。所以算下来是最好的选择。

我们需要select一个divider来拆分v，因为我们无法将它的64位放入float的52位尾数中。让我们把它分成两部分 hi 和 lo。 lo包含一个数，由v的低13位小数表示，hi表示另外几部分：v = hi*10^13 + lo。（稍后我们会解释为什么 10^13 被 selected ）

hi 包含 h1 = hi * floor(10^13/2^32) 次 2^32。但是提醒（余数表示 hi * (10^13%2^32) ）连同 lo 也可以包含一些 2^32。让我们数一数：h2 = q = floor(hi*(10^13%2^32) + lo)/2^32。并且 h = h1 + h2。

我们来介绍m = hi*(10^13%2^32) + lo。 l = m - q*2^32。现在我们有了 h 和 l.

这两个部分

为什么我们 select 编辑了 10^13？我们要： 1.将计算时的所有数字都放入52bits中 2.从10^13 / 2^32(=2328)取整数（非有理数）不报错。 10^13 最适合。

旧版本

此代码使用浮点运算将给定数字 v 打包为两个 32 位 h 和 l 部分。

代码的作者选择10^13作为除法器，将v的部分放入double-precision floating-point的52位尾数中而不丢失有效位（2^51更大比 10^13).

算法说明：

给定的数字v被10^13分成两部分：
- v = hi * 10^13 + lo
然后计算所得数字的高位部分：
- h = (10^13 / 2^32) * hi + (m / 2^32)
- 其中m = lo + hi * (10^32 % 2^32)
- 这里我们计算给定数字v中包含多少2^32来填充结果64位整数的高位部分h。棘手的部分是 m。我们需要它将剩余的 'amount' 从 hi 添加到 lo 并计算它包含多少 2^32。
l实际上计算为模：
- l = m % 2^32.

这个算法要重写吗？我认为应该以更清晰的方式重写它。我还会检查浮点数乘法后重要位的丢失情况。

了解长除法算法

Understanding long division algorithm

algorithm

long-integer