In integer-only computation, a fraction like 5/2 is rounded down to 2. Is this any extra work at the ALU level, or, is the way it does division, at the level of logical gates, automatically outputting the rounded down result as standard?


Division is hard and slow.

The typical process to divide x by a non-zero y on a fast modern processor goes like this:

Step 1: Multiply y by 2^k, k even, such that y <= x < 4. Initialise the result to 0.

Step 2: Find the largest integer m such my <= x < (m+1) y; replace result with (result << 2) + m, x with x - my, y with y >> 2. If k ≠ 0 then k = k-2 and back to Step 2.

The hardware to determine m will be limited so it can pick an m that is a little bit too low, for example it might pick m = 2 if x ≈ 3.001m, so the m in the next round could be 4, and after the last round the remainder might be x ≥ y. So we add

Step 3: If x >= y then increase result by 1, subtract y from x.

As you see, there isn't actually any way to produce a fraction.

Some additional steps are needed to handle y = 0, and to handle negative numbers, including the notorious case that say for 32 bit numbers, (-2^31) / (-1) = 2^31 is too large to fit into a signed 32 bit integer.

Note that the hardware automatically produces x modulo y at the same time.

  • $\begingroup$ Thanks for your answer. It's going to take me some time to understand your algorithm. But, to get the dumb answer to the question, it does not require extra work, right? Just like "slow division" by adding divisor until number gets larger than dividend, it would return rounded down answer automatically. $\endgroup$
    – Johan
    Oct 16 '21 at 14:38
  • $\begingroup$ Why I ask, I learnt programming before learning about logical gates and all that, and sometimes exploit the fact that division rounds down, and it first seemed to me like it would be doing extra work in the cpu but then I realized it wouldn't. $\endgroup$
    – Johan
    Oct 16 '21 at 14:39
  • $\begingroup$ Yes, there is no extra time for truncating to an integer. Hypothetically if you had a processor that calculates fractional bits, it would take longer. Say you want 16 additional bits, if the hardware calculates 2 bits per round, that would be 8 extra rounds. $\endgroup$
    – gnasher729
    Oct 16 '21 at 17:46

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.