0
$\begingroup$

I wanted to ask here a question about a simple algoirhtm to compute a div d and a mod d. My doubt specifically depend on negative numbers:

enter image description here

Doesn't the algorithm get wrong results for $-4$ and $2$ for instance, since the reminder of that division is 0? In this case the algorithm should give a quotient of $2$, But i image it should be $-2$, am i right?

$\endgroup$
2
$\begingroup$

You're right. If this algorithm divides -k * d by d, it will return k as the result of the division instead of -k.

On top of that, if you divide one billion billions by one, it will take an eternity to finish. Execution time is O (|a| / d), which is just horribly bad.

$\endgroup$
1
  • $\begingroup$ (I think you want $\Omega(|a|/d)$ instead of $O(|a|/d)$). $\endgroup$
    – Steven
    Nov 25 '21 at 9:37

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.