php - 大整数乘积差分算法

Question

我正在寻找一种算法来解决 ab-cd 类型的差异，其中 a、b、c 和 d 是类型容量边缘的整数，即 ab 溢出或丢失数字取决于实际表示在机器上。我不能使用任意精度的数学；其中一个平台将是 SQL 数据库。

我考虑将乘积分解为 (a'+a'')b-(c'+c'')d，然后以某种方式向下迭代。但可能有更有效的方法，或者至少有一个聪明的想法如何进行分解。不幸的是，在大多数情况下 a,b；光盘;一、三； b,d 是互质的，所以归约至少不简单。

有什么想法吗？

Answer 1

---

警告

此方法仅部分起作用。有些情况它无法解决。

---

摘自您的文字:

I'm searching for an algorithm to solve differences of the type ab-cd, where a, b, c, and d are integers at the edge of the type capacity,

据我了解，您想计算 (a * b) - (c * d) 以避免数字溢出。你想用算法解决这个问题。

我们首先需要认识到的是 (a * b) - (c * d) 的结果可能不适合数据类型。我不会尝试解决这些情况。

因此，我将寻找不同的方法来计算“ab-cd”。我发现的是:

(a * b) - (c * d) = ((a - c) * b) - (c * (d - b))

您可以重新排序变量以获得不同的产品，从而增加找到一个案例的机会，该案例将允许您在没有可怕的数字溢出的情况下计算操作:

((a - d) * b) - (d * (c - b))
((b - c) * a) - (c * (d - a))
((a - c) * b) - (c * (d - b))
((b - d) * c) - (b * (c - a))
((a - d) * c) - (a * (c - b))
((b - c) * d) - (b * (d - a))
((a - c) * d) - (a * (d - b))

另请注意，这仍然是产品的差异，这意味着您可以递归地应用它们，直到找到一个有效的产品。例如:

    Starting with:
        (a * b) - (c * d)
    =>
    Using the transformation:
        ((a - d) * b) - (d * (c - b))
    =>
    By substitution:
        (e * b) - (d * f)
    =>
    Rinse an repeat:
        ((e - f) * b) - (f * (d - b))

当然，我们需要确保这样做不会遇到数字溢出。值得庆幸的是，还可以使用以下方法测试特定产品是否会导致数字溢出(无需实际执行该产品):

        var max = MaxValue;
        var min = MinValue;
        if (a == 0 || b == 0)
        {
            return false;
        }
        else
        {
            var lim = a < 0 != b < 0 ? min : max;
            if ((a < 0 == b < 0) == a < 0)
            {
                return lim / a > b;
            }
            else
            {
                return lim / a < b;
            }
        }

此外，还可以使用以下方法测试特定差异是否会导致数字溢出(无需实际执行差异):

        var max = MaxValue;
        var min = MinValue;
        if (a < 0 == b < 0)
        {
            return true;
        }
        else
        {
            if (a < 0)
            {
                if (b > 0)
                {
                    return min + b < a;
                }
                else
                {
                    return min - b < a;
                }
            }
            else
            {
                if (b > 0)
                {
                    return max - b > a;
                }
                else
                {
                    return max + b > a;
                }
            }
        }

有了它，就可以从上面的八个表达式中选择一个表达式，使您可以在没有数字溢出的情况下进行计算。

但是...有时这些都不起作用。似乎有些情况下它们的组合都不起作用(即冲洗和重复不起作用)*。也许还有其他身份可以完成这幅画。

*:我确实尝试过使用一些启发式来探索组合，也尝试过随机探索，但存在我没有选择好的启发式并且我没有随机“运气”的风险。这就是为什么我不能确定。

我想认为我已经取得了一些进展......但是对于最初的问题我最终失败了。可能是当我有更多时间时我会回到这个问题上...或者我可能只是玩电子游戏。