4
$\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, 2020 at 12:33
  • $\begingroup$ Yes, all $a,b,c,d$ are positive. $\endgroup$
    – Syed Fahad
    Apr 15, 2020 at 14:04
  • $\begingroup$ Are you comparing for equality, or do you need the full three-way comparison? $\endgroup$ Apr 15, 2020 at 16:28
  • $\begingroup$ Multiplication and adding/subtracting are allowed or not? $\endgroup$ Apr 15, 2020 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, 2020 at 6:45

1 Answer 1

5
$\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 and acknowledge you have read our privacy policy.

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