algorithm - 了解长除法算法

Question

我在 PHP 的 SphinxAPI 类中创建了一些长除法代码，它将 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

你能告诉我，这里用的是什么长除法算法吗(作者在评论中称其为“有趣”)？还是常用算法的表达式重写？

Answer 1

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

新版本

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

怎么做？

v = h*2^32 + l。这意味着 h 是多少 whole 2^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 平台上可以表示最大范围的数字。因此，它是进行计算的最佳选择。

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

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 这两个部分。

为什么我们选择 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)。

算法说明:

1. 给定的数字v被10^13分成两部分:

   • v = hi * 10^13 + lo

2. 然后计算所得数字的高位部分:

   • h = (10^13/2^32) * hi + (m/2^32)

   • 其中 m = lo + hi * (10^32 % 2^32)

   • 这里我们计算给定数v中包含多少2^32来填充结果64bit的高位部分h整数。棘手的部分是 m。我们需要它添加从 hi 到 lo 的剩余“数量”，并计算它包含多少 2^32。

3. l 实际上被计算为模:

   • l = m % 2^32。

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