Electronic – How does division occur in our computers

arithmetic-divisioncomputerstutorial

How does division occur inside digital computers? What is the algorithm for it?

I have searched hard in google but haven't got satisfactory results. Please provide a very clear algorithm/flowchart for division algorithm with a sample illustration.

Best Answer

Division algorithms in digital designs can be divided into two main categories. Slow division and fast division.

I suggest you read up on how binary addition and subtraction work if you are not yet familiar with these concepts.

Slow Division

The simplest slow methods all work in the following way: Subtract the denominator from the numerator. Do this recursively with the result of each subtraction until the remainder is less than the denominator. The amount of iterations is the integer quotient, and the amount left over is the remainder.

Example:

7/3:

$$7-3=4$$
$$4-3=1$$
$$1 < 3$$

Thus the answer is 2 with a remainder of 1. To make this answer a bit more relevant, here is some background. Binary subtraction via addition of the negative is performed e.g.: 7 - 3 = 7 + (-3). This is accomplished by using its two's complement. Each binary number is added using a series of full adders:

enter image description here

Where each 1-bit full adder gets implemented as follows:

enter image description here

Fast Division

While the slower method of division is easy to understand, it requires repetitive iterations. There exist various "fast" algorithms, but they all rely on estimation.

Consider the Goldschmidt method:

I'll make use of the following: $$Q = \frac{N}{D}$$

This method works as follows:

Multiply N and D with a fraction F in such a way that D approaches 1.
As D approaches 1, N approaches Q

This method uses binary multiplication via iterative addition, which is also used in modern AMD CPUs.

Related Solutions

Electronic – hardware implementation of division algorithm

Flowcharts are often not a very precise way of indicating what hardware is doing, since flowcharts often imply the existence of a single execution process, whereas hardware often does many overlapping and simultaneous operations.

The portions of the diagram circled in red seem a bit odd. It seems odd to latch A with the value after subtracting B, and then re-add B. More natural would simply be to not bother latching the lower part of the subtraction result. I think the flowchart might be clearer if "named values" were separated into "registers" and "values", and each step either computed values or registers. Thus, for example, one could have something like (assuming 16-bit registers)

C:T[15..0] = (A[14..0]:Q[15]) + ~B-1
if (C or A[15])
  A[15..0] = (A[14..0]:Q[15])
  Q[15..1] = Q[14..0]
  Q[0] = 1
Else
  A[15..0] = T[15..0]
  Q[15..1] = Q[14..0]
  Q[0] = 0
Endif

Every step that updates registers would represent a system clock. Events that merely compute values would not require a clock edge, but would be processed asynchronously.

Electronic – How large is the address decoder to select an address in RAM? Is the address decoder just a bunch of multiplexers

For most RAM, the mux turns into a column select for a large grid, and an entire line of data is read out or written at once. The grid structure gives you the efficiency you need.

http://docencia.ac.upc.edu/master/DTM/docs/03-Memory%20Structures.pdf is a good PDF on the subject. It also shows a "predecode" structure which makes the decoder less complex than it would be otherwise.

Best Answer

Related Solutions

Electronic – hardware implementation of division algorithm

Electronic – How large is the address decoder to select an address in RAM? Is the address decoder just a bunch of multiplexers

Related Topic