How does \ or / actually work?

[DavidHooper]

How does \ or / actually work?

I know both are actually repeated subtraction so, for example:
8/2=4 because 2 can be subtracted four times: 8 - 2 - 2 - 2 - 2

But before any wisecracks stroke their beards wisely, then surely this can't be how the operator's are handled by the processor?
If I perform operation A (following), then it is certainly faster than operation B (even taking account for processor optimisations, code overhead etc etc).

A:

x=1000/2

B: x=1000
Do
x=x-2
count=count+1
Loop until x<=2

Maybe it uses the mod operator on the individual digits in some way? Thoughts please.

[Guv]

The basic hardware division algorithm for a CPU can be illustrated using decimal arithmetic. Try dividing 2663 by 11

Line up as follows. Note that divisor was shifted left to line up with dividend. First digit of quotient will be put directly above last digit of divisor.

2663
11

Subract & tally until result is negative. When negative, add back and subtract one from tally. So far we have the following.

02
0463
11

Shift the divisior right one, getting

02
0463
011

You can subtract & tally 5 times before going negative. After adding divisor back and subtracting one from tally, you have the following.

024
0023
011

Shift divisor right, getting

024
0023
0011

After subtracting & tallying three times, the result is negative. Add back and subtract one from tally, getting the following.

0242
0001
0011

If doing integer divison, you are finished. 2663/11 = 242, with a remainder of one.

In dealing with negative values, the algorithm is a bit more complicated, although you can work the division with absolute values and figure out the sign when you have the absolute quotient. If you want fractional digits, just keep the process up, adding zeros to dividend as required.

For a binary CPU, no tally is required. After lining up divisor and dividend, do the following.

• Subtract divisor from dividend.
  
• If result is negative, add divisor to dividend. Set next quotient bit to zero.
  
• If result is positive, set next quotient bit to one.
  
• In either case, shift divisor right one bit and repeat above steps.

Once again, for integer divison with positive values, the above is all that is required. The process stops when the right shift causes a divisor bit to be lost.

For negative values and/or floating point operands, the process is more complicated, but the above is at the heart of the algorithm.

In a 2-complement CPU, there is some cute trickery which allows the algorithm to be almost the same no matter what the sign bits are. I do not remember all the details. One detail I remember is that a negative divisor is added to dividend instead of being subtracted. The decision logic is set based on analysis of the carry into and out of the sign bit of the dividend.

[Alphanos]

It would seem to me that the easiest way for the processor to deal with the sign bits would be to use a simple xnor them. Would work no matter what.

[Guv]

The sign logic in a 2-complement binary CPU is trickier than just determining the sign of the result.

People work with signed magnitude notation, while most computers use complement arithmetic. In signed magnitude the numeric digits do not change when you change the sign. In complement arithmetic, they do. For example, consider the following.

In ten-complement decimal notation using 8 digits.

99995633 is negative 00004367

In 2-complement binary using 8 bits,

11101011 is negative 00010101

The division algorithm used by a CPU manages to generate negative results bit by bit instead of doing a complement operation after working with absolute operands.

[DavidHooper]

cheers guv, once again u helped me out - i'd forgotten all about an implementation of long division!