我正在寻找一种算法来解决 ab-cd 类型的差异,其中 a、b、c 和 d 是类型容量边缘的整数,即 ab 溢出或丢失数字取决于实际表示在机器上。我不能使用任意精度的数学;其中一个平台将是 SQL 数据库。
我考虑将乘积分解为 (a'+a'')b-(c'+c'')d,然后以某种方式向下迭代。但可能有更有效的方法,或者至少有一个聪明的想法如何进行分解。不幸的是,在大多数情况下 a,b;光盘;一、三; b,d 是互质的,所以归约至少不简单。
有什么想法吗?
最佳答案
警告
此方法仅部分起作用。有些情况它无法解决。
摘自您的文字:
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;
}
}
}
有了它,就可以从上面的八个表达式中选择一个表达式,使您可以在没有数字溢出的情况下进行计算。
但是...有时这些都不起作用。似乎有些情况下它们的组合都不起作用(即冲洗和重复不起作用)*。也许还有其他身份可以完成这幅画。
*:我确实尝试过使用一些启发式来探索组合,也尝试过随机探索,但存在我没有选择好的启发式并且我没有随机“运气”的风险。这就是为什么我不能确定。
我想认为我已经取得了一些进展......但是对于最初的问题我最终失败了。可能是当我有更多时间时我会回到这个问题上...或者我可能只是玩电子游戏。
关于php - 大整数乘积差分算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12764150/