# Can you compare integer part of two fractions without division?

Suppose we need to compare $$\left \lfloor{a / b}\right \rfloor$$ and $$\left \lfloor{c / d}\right \rfloor$$ . One way would of course be to calculate $$a/b$$ and $$c/d$$ by division. Is their a faster way?

• Are they positive? Apr 15 '20 at 12:33
• Yes, all $a,b,c,d$ are positive. Apr 15 '20 at 14:04
• Are you comparing for equality, or do you need the full three-way comparison? Apr 15 '20 at 16:28
• Multiplication and adding/subtracting are allowed or not? Apr 15 '20 at 16:53
• Comparing just for equality. Multiplication is faster than division so I guess that would be allowed. Adding subtracting is definitely allowed. Apr 16 '20 at 6:45

A necessary condition for $$\lfloor a/b\rfloor = \lfloor c/d\rfloor$$ is $$|ad-bc| < db$$. This is not sufficient however, so if this test yields true (or if one of the multiplications overflows), you still must do the integer division. Depending on the probability distribution of your numbers a,b,c,d and the runtime complexity of multiplication compared to division, this can still be a runtime improvement on average.