比较两个可能溢出的倍数 [英] Compare two multiples which could overflow
问题描述
我有三个值：
UInt64 a，b，c，d;
我需要确定是否：（a * b）< =（c * d）。当然，只需进行
乘法和比较就能告诉我结果。但是，
值可能会溢出。例如，如果：
a = UInt64.MaxValue;
b = 2;
c = UInt64.MaxValue / 3;
d = 4;
我仍然需要能够结束ab cd。我可以通过以下方式确定是否会在乘法时进行
包装：
if（a< = 1 || b< = 1）
{
返回false;
}
return（（UInt64.MaxValue / a）< b ）;
但它仍然无法帮助我确定ab cd。我是否有任何关于如何确定这一点的想法？谢谢。
2008年10月3日星期五16:35:06 -0700，< ag ******* @ gmail。编写：
我有三个值：
UInt64 a，b，c，d;
我需要确定：（a * b）< =（c * d）。 [...]
我不知道.NET内置的任何东西会直接执行此操作
处理溢出时。如果您正在处理签名的64位值，
您可以使用Math.DivRem（），比较a / c与d / b
（包括余数） 。但是对于无符号的64位值，我认为你可能只需要b / b
就可以做很长时间的数学运算。
Pete
ag*******@gmail.com 写道：
我有三个值：
UInt64 a，b，c，d;
我需要确定：（a * b）< =（c * d）。当然，只需进行
乘法和比较就能告诉我结果。但是，
值可能会溢出。例如，如果：
a = UInt64.MaxValue;
b = 2;
c = UInt64.MaxValue / 3;
d = 4;
我仍然需要能够结束ab cd。我可以通过以下方式确定是否会在乘法时进行
包装：
if（a< = 1 || b< = 1）
{
返回false;
}
return（（UInt64.MaxValue / a）< b ）;
但它仍然无法帮助我确定ab cd。我是否有任何关于如何确定这一点的想法？谢谢。
嗯，你想把它们分成几小块，分成32位块，并检查这些是否是
。首先是一些理论。比如，n = 2 ^ 32，那么
a = a0 + a1 * n
b = b0 + a2 * n
c = c0 + c1 * n
d = d0 + d1 * n
（a0 + a1 * n）*（b0 + b1 * n） - （c0 + c1 * n）*（d0 + d1 * n）0
a0 * b0 + a0 * b1 * n + a1 * b0 * n + a1 * b1 * n * n>
c0 * d0 + c0 * d1 * n + c1 * d0 * n + c1 * d1 * n ^ 2 0
a0 * b0 +（a0 * b1 + a1 * b0）* n + a1 * b1 * n * n>
c0 * d0 +（c0 * d1 + C1 * d0）* n + c1 * d1 * n * n
现在你要总是如何比较数字，比如321 175.你首先
比较最高位数。如果他们不平等，你有
答案。如果它们相等，则比较第二个数字，依此类推，
等等。
这里你也是这样做的。如果a1 * b1 c1 * d1，则结果为真。如果
a1 * b1< c1 * d1，则结果为false。如果两者相等，你转向比较下一个数字，即你比较
a0 * b1 + a1 * b0与c0 * d1 + c1 * d0，等等。
UInt64 a0 = a& 0xFFFFFFFF;
UInt64 a1 = a> 32;
UInt64 b0 = b& 0xFFFFFFFF;
UInt64 b1 = b> 32;
UInt64 c0 = c& 0xFFFFFFFF;
UInt64 c1 = c> 32;
UInt64 d0 = d& 0xFFFFFFFF;
UInt64 d1 = d> 32;
UInt64 x00 = a0 * b0;
UInt64 x01 = c0 * d0;
//这个可能会溢出，所以将它们分得更多：
int x10 =（a0 * b1）& 1 +（a1 * b0）& 1; //较低位
int x11 =（c0 * d1）& 1 +（c1 * d0）& 1; //较低位
UInt64 x20 = a0 * b1 / 2 + a1 * b0 / 2; //前63位
UInt64 x21 = c0 * d1 / 2 + c1 * d0 / 2; //前63位
if（x10 = 2）
{
x20 ++;
x10 = 0;
}
if（x11 = 2）
{
x21 ++;
x11 = 0;
}
字节x20 =
UInt64 x30 = a1 * b1;
UInt64 x31 = c1 * d1;
现在如果比较较高的部分，较低的位不重要，
除非较高的部分相等。所以你可以这样做：
if（x30 x31）
返回true;
else if（x30< x31）
返回false;
else if（x20 x21）
返回true;
else if（x20< x21 ）
返回false;
else if（x10 x11）
返回true;
else if（x10< ; x11）
返回false;
else if（x00 x01）
返回true;
else
返回false;
FWIW，这不会溢出。每个部分x00 - x31都在UInt64
范围内。
-
Rudy Velthuis http://rvelthuis.de
"全世界的问题是傻瓜和狂热分子总是如此肯定，但是那些更加聪明的人充满了...... b $ b怀疑。 - Bertrand Russell
非常有帮助和信息丰富。谢谢，鲁迪。
SteveT
I have three values:
UInt64 a, b, c, d;
I need to determine if: (a*b) <=(c*d). Naturally, just doing the
multiplication and comparing would tell me the result. However, the
values could potentially overflow. For example, if:
a = UInt64.MaxValue;
b = 2;
c = UInt64.MaxValue / 3;
d = 4;
I still need to be able to conclude ab cd. I can determine if
wrapping will occur on multiplication by doing:
if (a <= 1 || b <= 1)
{
return false;
}
return ((UInt64.MaxValue / a) < b);
But it still doesn''t help me determine ab cd. Anybody have any
thoughts on how I could determine this? Thanks.
On Fri, 03 Oct 2008 16:35:06 -0700, <ag*******@gmail.comwrote:
I have three values:
UInt64 a, b, c, d;
I need to determine if: (a*b) <=(c*d). [...]I''m not aware of anything built into .NET that would do this directly
while handling overflow. If you were dealing with signed 64-bit values,
you could have used the Math.DivRem(), comparing a/c against d/b
(including remainder). But with unsigned 64-bit values, I think you might
as well just do the math the long way.
Pete
ag*******@gmail.com wrote:
I have three values:
UInt64 a, b, c, d;
I need to determine if: (a*b) <=(c*d). Naturally, just doing the
multiplication and comparing would tell me the result. However, the
values could potentially overflow. For example, if:
a = UInt64.MaxValue;
b = 2;
c = UInt64.MaxValue / 3;
d = 4;
I still need to be able to conclude ab cd. I can determine if
wrapping will occur on multiplication by doing:
if (a <= 1 || b <= 1)
{
return false;
}
return ((UInt64.MaxValue / a) < b);
But it still doesn''t help me determine ab cd. Anybody have any
thoughts on how I could determine this? Thanks.Well, you want to split them up a bit, into 32 bit chunks, and check
these. First some theory. Say, n = 2^32, then
a = a0 + a1*n
b = b0 + a2*n
c = c0 + c1*n
d = d0 + d1*n
(a0 + a1*n)*(b0 + b1*n) - (c0 + c1*n)*(d0 + d1*n) 0
a0*b0 + a0*b1*n + a1*b0*n + a1*b1*n*n >
c0*d0 + c0*d1*n + c1*d0*n + c1*d1*n^2 0
a0*b0 + (a0*b1 + a1*b0)*n + a1*b1*n*n >
c0*d0 + (c0*d1 + C1*d0)*n + c1*d1*n*n
Now you do how you always compare numbers, like 321 175. You first
compare the highest digits. If they are not equal, you have your
answer. If they are equal, you compare the second digits, and so on,
and so forth.
Here you do the same. if a1*b1 c1*d1, then the result is true. If
a1*b1 < c1*d1, then the result is false. And if both are equal, you
turn to comparing the next "digit", i.e. you compare
a0*b1 + a1*b0 with c0*d1 + c1*d0, etc.etc.
UInt64 a0 = a & 0xFFFFFFFF;
UInt64 a1 = a >32;
UInt64 b0 = b & 0xFFFFFFFF;
UInt64 b1 = b >32;
UInt64 c0 = c & 0xFFFFFFFF;
UInt64 c1 = c >32;
UInt64 d0 = d & 0xFFFFFFFF;
UInt64 d1 = d >32;
UInt64 x00 = a0*b0;
UInt64 x01 = c0*d0;
// this one may overflow, so split them up even more:
int x10 = (a0*b1) & 1 + (a1*b0) & 1; // lower bit
int x11 = (c0*d1) & 1 + (c1*d0) & 1; // lower bit
UInt64 x20 = a0*b1/2 + a1*b0/2; // top 63 bits
UInt64 x21 = c0*d1/2 + c1*d0/2; // top 63 bits
if (x10 = 2)
{
x20++;
x10 = 0;
}
if (x11 = 2)
{
x21++;
x11 = 0;
}
Byte x20 =
UInt64 x30 = a1*b1;
UInt64 x31 = c1*d1;
Now if the higher parts are compared, the lower bits don''t matter,
except if the higher parts are equal. So you can do:
if (x30 x31)
return true;
else if (x30 < x31)
return false;
else if (x20 x21)
return true;
else if (x20 < x21)
return false;
else if (x10 x11)
return true;
else if (x10 < x11)
return false;
else if (x00 x01)
return true;
else
return false;
FWIW, this will not overflow. Each part, x00 - x31, is in the UInt64
range.
--
Rudy Velthuis http://rvelthuis.de
"The whole problem with the world is that fools and fanatics are
always so certain of themselves, but wiser people so full of
doubts." -- Bertrand Russell
Very helpful and informative. Thanks, Rudy.
SteveT
这篇关于比较两个可能溢出的倍数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
