Re: comparing products of integers
- From: "Peter L. Montgomery" <Peter-Lawrence.Montgomery@xxxxxx>
- Date: Wed, 27 Apr 2005 14:53:02 GMT
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).
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
.
- Follow-Ups:
- Re: comparing products of integers
- From: analyst41
- Re: comparing products of integers
- References:
- comparing products of integers
- From: analyst41
- comparing products of integers
- Prev by Date: Re: comparing products of integers
- Next by Date: stop-test for iterative methods
- Previous by thread: Re: comparing products of integers
- Next by thread: Re: comparing products of integers
- Index(es):
Relevant Pages
|
