Re: comparing products of integers


Peter L. Montgomery wrote:
> In article <1114606012.207570.165560@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>
> analyst41@xxxxxxxxxxx writes:
> >I want to compare A.B with C.D where A,B,C,D are 32 bit integers.
Is
> >there a way to do the comparison without creating the potentially 64
> >bit products ?
> >
> >Thanks for any help.
> >
> A (slow) method manipulates 2 x 2 determinants.
> Start with
>
> M = (A C) sign = +1
> (D B)
>
> Then A*B - C*D = sign*det(M).
>
> If A < 0 or D < 0, negate the corresponding row and
> replace sign by -sign. Swap rows and change the sign,
> if necessary, to make A >= D >= 0.
>
> If D = 0, then det(M) has the same sign as A*B.
> Otherwise A and D are positive.
>
> If C < 0, negate the second column and the sign.
>
> If B < 0, then A*B < 0 and C*D >= 0, so you know the sign of
det(M).
>
> If B > C, then A*B > C*D.
>
> Otherwise let q = MIN(FLOOR(A/D), FLOOR(C/B)) (an integer).
> Subtract q*(second row) from (first row).
>

Thank you - I'll try to work out if the coeffcients decrease rapidly as
in the Euclidean Algorithm. Using an all-integer approach seems more
elegant.
>
> You can instead write A, B, C, D each in the form
> a1*2^16 + a0. If your variables are unsigned, then
> a1, a0 are nonnegative. Manipulate
>
> (a1*2^16 + a0) * (b1*2^16 + b0)
> - (c1*2^16 + c0) * (d1*2^16 + d0)
>
> algebraically. If you have 53-bit floating point
> mantissas, you can cast a1, a0, ... to floating point,
> then evaluate the coefficients of
>
> (a1*b1 - c1*d1)*2^32 + ...
>
> and soon get the determinant accurately.
>
> --
> If same-sex marriages are so bad, why do most
> college dormitories assign same-sex roommates?
>
> pmontgom@xxxxxx Microsoft Research and CWI Home: Bellevue, WA

.

Relevant Pages