我正在寻找一种算法来解决 ab-cd 类型的差异，其中 a、b、c 和 d 是类型容量边缘的整数，即 ab 溢出或丢失数字取决于机器上的实际表示. 我不能使用任意精度的数学；其中一个平台将是 SQL 数据库。
我考虑将产品分解为 (a'+a'')b-(c'+c'')d 然后以某种方式向下迭代。但可能有一种更有效的方法，或者至少有一个聪明的想法来进行分解。不幸的是，在大多数情况下，a，b；光盘; a, c; b,d 互质，所以至少减少并不简单。
有任何想法吗？
问问题
199 次
5 回答
2
警告
这种方法只是部分功能。有解决不了的情况。
取自您的文字：
我正在寻找一种算法来解决 ab-cd 类型的差异，其中 a、b、c 和 d 是类型容量边缘的整数，
据我了解，您想要计算(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;
}
}
}
有了它，就可以从上面的八个中选择一个表达式，这样您就可以在没有数字溢出的情况下进行计算。
但是......有时这些都不起作用。似乎在某些情况下，甚至它们的组合都不起作用（即冲洗和重复不起作用）*。或许还有其他身份可以补全画面。
*：我确实尝试使用一些启发式来探索组合，也尝试过随机探索，存在我没有选择好的启发式并且我没有随机“运气”的风险。这就是为什么我不能确定。
我想我已经取得了一些进展......但是关于最初的问题我最终失败了。可能当我有更多时间时我会回到这个问题......或者我可能只是玩电子游戏。
于 2012-10-06T22:04:44.607 回答
1
我所知道的解决此类问题的标准方法是像人类一样处理超过一位数的数字，这是我们用手指自然计数的极限。我们carry向前编号。
例如，假设您的数字计算器中的数字限制为 256 (2^8)。为了得到 (243*244)-(242*245) 的差异，我们需要将数字分解为
Label | Part 1 (shifted 2 right) | Part 2 (remainder)
a 2 43
b 2 44
c 2 42
d 2 45
您需要一个数组来存储结果的各个数字或字符串。我认为数组更快，但字符串更方便和可见（用于调试）。
(a*b)-(c*d)
=> a1*b1 shift4 + a1*b2 shift2 + a2*b1 shift2 + a2*b2
- c1*d1 shift4 + c1*d2 shift2 + c2*d1 shift2 + c2*d2
=> 987654321 (right-aligned string positioning)
+ 4xxxx
+ 88xx
+ 86xx
+ 1892
- 4xxxx
- 90xx
- 84xx
- 1890
==========
2
一个简单的实现将独立完成每个步骤，将每个数字推入到位并在必要时将其推进。可能有大量关于优化这些算法的文献，例如将其分解为每个 2 位数的数组槽（因为您的 number-limit 256 寄存器可以轻松处理 2 个 2 位数的加法）。
于 2012-10-06T23:34:20.223 回答
1
如果您的产品接近 Int32 的限制，您可以使用 Int64。
于 2012-10-06T21:48:05.257 回答
0
在玩了一点之后，我发现了一个更简单的算法，遵循我最初的想法。它可能比组合乘法要慢一些，因为它需要真正的乘法和除法，而不仅仅是移位和加法，但到目前为止我还没有对抽象语言的性能进行基准测试。
想法如下重写 ab-cd = (a'+q*d)b-cd = a'b-(c-qb)d = a'b-c'd
如果您将 a>b 和 c>d 排序为 a>b 和 c>d，则该算法似乎转换最快，即减少最大数字并最大化 q。
q=(int)floor((a>c)? a/d : c/b);
a -= q*d;
c -= q*b;
现在重新排序并重新开始。只要所有数字都小到可以安全乘法，任何数字都小于 2 甚至为负数，或者两边的任何数字都找到相同的值，您就可以完成。
于 2012-10-09T19:48:39.040 回答
0
您可以使用BC 数学函数来处理 32 位和 64 位系统上的大数
大数示例
$a = "4543534543543534543543543543545";
$b = "9354354546546756765756765767676";
$c = "5654656565656556565654656565656";
$d = "4556565656546546546546546356435" ;
var_dump(calculate($a, $b, $c, $d));
输出
string '257010385579862137851193415136408786476450997824338960635377204776397393100227657735978132009487561885957134796870587800' (length=120)
使用的功能
function calculate($a, $b, $c, $d)
{
return bcmul(bcmul(bcmul(bcsub($a, $c),bcsub($a, $d)),bcsub($b, $c)),bcsub($b, $d));
}
于 2012-10-06T21:57:39.117 回答