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

| cite | improve this answer | |
$\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.