some integer problems

some integer problems

Post by Srikanth Ban » Thu, 24 Feb 1994 22:14:28



I have following computing problem:

There are four integers a1,a2,b1,b2 with large values.
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)

Thanks.

-Srikanth

 
 
 

some integer problems

Post by Srikanth Ban » Thu, 24 Feb 1994 22:29:18


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)

Thanks.

-Srikanth

 
 
 

some integer problems

Post by Brandon Van Eve » Fri, 25 Feb 1994 04:31:31


: 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.

Cheers,
Brandon

--
Brandon Van Every             "No more LaunchPAD .Sigs!  HA HA HA HA HA HA!!!"

 
 
 

some integer problems

Post by Srikanth Ban » Fri, 25 Feb 1994 17:12:54


I received several solutions on this problem.
Suggestions included
   .converting values to double and doing the multiplication
   .take logoarithms, add them and then compare.
   .carry out integer mutiplication in smaller chunks.
   .doing recursive calculation (integer arithmetic but may be much slower
    than double-precision calculation)

Thanks for the solutions

-Srikanth

 
 
 

some integer problems

Post by Kenneth Bo Lars » Fri, 25 Feb 1994 18:59:07



>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)
>Thanks.

Normally this type of problem is solved at a higher level. You modify
your whole algorithm and representation to avoid computations. Assuming you
want to avoid the multiplications because of the overflow you have two
possibilities. Either your integers are 64-bit (or more), in which case
you probably already implemented multi-precision arithmetic and may
use that. If you use 32-bit integers most CPU's (including Intel's)
will multiply two 32-bit integers giving a 64-bit result; and your
problem is solved. I can't give you any solution that will use less
cycles than multiplication. Maybe somebody else can.

Kenneth

Olivetti Research S.C.p.A., Naples

 
 
 

some integer problems

Post by Gabriel C. Lopez Wal » Sat, 26 Feb 1994 00:28:09


: 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)

  Maybe you can try a1/b1 > b2/a2, you need to handle floating point
check if the numbers are enought differents.

+--------------------------------------------------------------------------+

! Lab. de Visualizacion, Supercomputo         (5) 622-8582                 !
! Universidad Nacional Autonoma de Mexico    04510  Mexico D.F.            !
+--------------------------------------------------------------------------+

 
 
 

some integer problems

Post by Ron Capel » Fri, 25 Feb 1994 21:01:11



Quote:>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)

This problem, after accounting for positive and negative values, is
identical to comparing the areas of two rectangles.  Maybe, in fact,
that is the actual application?

To avoid arithmetic overflow, imagine factoring out some large
common area:

              b1
       +---------------+
       |               |
       +---------------|---+            a1 >= a2
    b2 |               |   |            b1 >= b2
       |               |   |
       |               |   | a2         a1 > b1
       |               |   |            a2 < b2
       +---------------+---+
                 a1

As you imply, the problem is trivial for cases such as where
a1 > b1 and a2 > b2, or a1 < b1 and a2 < b2.

Otherwise, the problem is now whether

      (a1 - b1) * a2  >  b1 * (b2 - a2)

Hopefully, these multiplications will not overflow, but if the
magnitudes are still too large, you can apply the algorithm
recursively...
_______________________________________________________________________

...Ron Capelli                 IBM Corp.  Dept. C13,  MS P912

   (914) 433-4280              Poughkeepsie, NY  12601-5400
_______________________________________________________________________

"Possessions increase to fill the space available for their storage."

 
 
 

some integer problems

Post by Doug Moo » Fri, 04 Mar 1994 07:37:01




   >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)

   >Thanks.

   Normally this type of problem is solved at a higher level.

But is it really that hard?

We know (in the case given):

a2 < b2 <= b1 < a1

so compute

(q1,r1) so that q1 * b1 + r1 = a1, r1 < b1

and

(q2,r2) so that q2 * a2 + r2 = b2, r2 < a2

Then

a1 * a2 > b1 * b2

<=>

(q1 * b1 + r1) * a2 > b1 * (q2 * a2 + r2)

<=>

q1*a2*b1 + a2*r1 > q2*a2*b1 + b1*r2

<=>

q1 > q2 OR (q1 = q2 AND a2*r1 > b1*r2)

In the latter case, we have to solve

a2*r1 > b1*r2

given

r1 < b1, r2 < a2.

which is basically the same problem we started with, with smaller
values.

Doug Moore

 
 
 

1. which integer HSL ranges to get all !! integer RGB-values ?

RGB is wanted in the range [0..255, 0..255, 0..255]

The question is which integer granularity the HSL-range needs:
integer means, the (smallest) step is always 1.
So I cannot change the step-width, but only the min, max-Values.

I already simply define:
H = [ 0 .... 360  degrees ] , step = 1
but what is with S and L, would be 101 different values for each sufficient
?:
S = [0... 100%] , step = 1
L = [0... 100%] , step = 1

or do I need higher max values to get smaller normalizes steps like:
S = [0... 240] , step = 1
L = [0... 240] , step = 1

Thank you very much

2. Special Effects in Video Games

3. Need help with division of 96bit integer with 64bit integer?

4. Any Suggestions

5. Integer JPEG decoding

6. Fwd: Design Exhibit

7. Raydream: Integer Divide By Zero?

8. SGI newbie

9. Integers, Floats, and Assembly

10. ? reading a *.bmp as an integer array ?

11. Forcing 32-bit integers and math

12. Understanding 64-bit integer data types in IDL/PV~Wave