: Kindly ignore my previous posting on this subject. I haven't
: supplied full info there.
: I have following computing problem:
: There are four integers a1,a2,b1,b2 with large values
: such that a1 >= a2 and b1 >= b2.
: I have to determine the relation between their products.
: Namely whether
: a1.a2 > b1.b2
: without actually carrying out the multiplication of a1,a2 and b1,b2.
: The multiplication gives integer overflow because of large
: values of variables.
: Is there any way of doing this?
: (The problem arises in the case: a1 > b1 and a2 < b2 or vice-versa)
If you're evading multiplication in order to be "more efficient," you're
sunk. You have to multiply to find the products, so you can compare them.
If you knew something more about a1,a2,b1,b2, and had some very specific
case to deal with, then maybe you could get around this. But if your
inputs can be of any value, you have to multiply.
If you're evading multiplication solely because it gives you an overflow,
and you simply need more precision, then there are ways to implement
greater precision. Let's say you have 32-bit ints on your system, you
could split them into 16-bit hi and low words, then do a lot of juggling,
and end up with a library to do 64-bit ints. Basically, you'd have to
implement your own "more precise integer" library, or use someone else's.
Such a library is not going to be as fast as what you're hardware is
capable of. You've got a lot of extra code and special cases. At some
point, it might be as fast or faster to simply change your ints into floats,
do the comparisons that way, then convert back to ints. How good an approach
this is depends on (1) how fast your floats are, relative to your ints, and
(2) how expensive it is to convert from ints to floats, and floats to ints.
On an i486 for example, an int add costs 1 cycle, a float add costs 10 cycles,
and converting a float to an int costs 33.4 cycles. Not pretty.
Brandon Van Every "No more LaunchPAD .Sigs! HA HA HA HA HA HA!!!"