3
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.