Compare two multiples which could overflow

[agendum97]

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.MaxVal ue / a) < b);

But it still doesn't help me determine ab cd. Anybody have any
thoughts on how I could determine this? Thanks.

[Rudy Velthuis]

ag*******@gmail .com wrote:

On Oct 4, 6:53*am, "Rudy Velthuis" <newsgro...@rve lthuis.dewrote:

Very simple. They are like numbers in base n instead of base 10. Say
the first number is u + v*n + w*n*n and the other one is x + y*n +
z*n*n. First we must compare w*n*n with z*n*n. But, if w*n*n >
z*n*n, then w z, so we only have to compare w and z, and we can
skip the n*n on both sides (since n*n is positive). If they are
equal, we must compare v and y, and if they are equal too, we
compare u and x. Of course this only works because all factors (u,
v, w, x, y, z) < n(*)

Hey Rudy,

Thanks for explaining. I studied this quite a bit, and I am pretty
sure I understand the approach you are taking here. Basically, how I
evaluated it is:

a*d <=c*b
is
(aL+aH*n)*(dL+d H*n) <=(cL+cH*n)*(bL +bH*n)
is
(aL*dL)+(aL*dH* n)+(aH*n*dL)+(a H*n*dH*n) <=>
(cL*bL)+(cL*bH* n)+(cH*n*bL) +(cH*n*bH*n)

Break each side into three pieces:

1) High product: aH*dH <=cH*bH
2) Medium product: aL*dH+aH*dL <=cL*bH+cH*bL
3) Low product: aL*dL <=cL*bL

On the medium product, n was elimated simply by dividing each side by
n:

((aL*dH*n)+(aH* n*dL))/n <=((cL*bH*n)+(c H*n*bL))/n

That is how we get: aL*dH+aH*dL <=cL*dH+cH*dL

I think the only question I have left is regarding your bitshifting.
I understand why you are bitshifting (in the worst case scenario, the
sum of each medium product could overflow). However, I don't
understand why are are adding the bits and only checking for 2. For
example, you have:

Adding two bits can have 3 possible results: 0, 1, and 2 (binary: 0 1
and 10). Only 2 will not fit in one bit, and the overflow must be added
to rest of the Medium Product.
--
Rudy Velthuis http://rvelthuis.de

"The average person thinks he isn't." -- Father Larry Lorenzoni