Fork me

Nonrestoring Division Calculation

The division operation is carried away by assuming fractional numbers. The Non-Restoring division algorithm is shown below. Initially R is set equal to N and n is the data width. The operands are in two’s compliment form where MSB bit is the signed bit. In Non-Restoring divider, quotient take the digit set {-1,1}. At the output, a conversion is needed to get the actual output.

Non-Restoring Division Algorithm Algorithm

Non-Restoring algorithm is shown with an example. An example of Non-Restoring division is below for N = 0.5 (0.100) and D = -0.75 (1.010). Here n is equal to 4.

Non-Restoring Division Algorithm Example

Thus the output is 0.q1q2q3 = 0.-1-11. To get the actual output an on-the-fly conversion is needed.

  • First mask bits for -1 . That is Q1 = 0.001.
  • Then assign Q2 as Q2 = 0.110.
  • Subtract Q2 from Q1 to get the actual result. That is Q = 1.011 (-0.625).



Algorithm A
ValuesBit Length   m		4Iteration    n		3Dividend     X or N	0000.1000	=	0.5Divisior     D		0000.1100	=	0.75Divisior    -D		1111.0100	=	-0.75r0			0000.10002r0			0001.0000		q0 = 1Add -D			1111.0100r1			0000.01002r1			0000.1000		q1 = 1Add -D			1111.0100r2			1111.11002r2			1111.1000		q2 = -1Add D			0000.1100r3			0000.0100
Algorithm B
ValuesBit Length   m		3Iteration    n		4Dividend     X or N	0000.1000	=	0.5Divisior     D		0000.1100	=	0.75Divisior    -D		1111.0100	=	-0.75r0			0000.10002r0			0001.0000		q0 = 1Add -D			1111.0100r1			0000.01002r1			0000.1000		q1 = 0r2			0000.10002r2			0001.0000		q2 = 1Add -D			1111.0100r3			0000.0100
R = r3 * 2-3 = 0000.0100 * 2-3 =0.25 * 2-3 = 0.03125Q = 0.11-1 = 0.625X = Q * D + R = 0.625 * 0.75 + 0.03125 = 0.5Execution Time = ~0 msOperation Count (Addition/Subtraction) = 3
R = r4 * 2-4 = 0000.0100 * 2-4 =0.25 * 2-4 = 0.015625Q = 0.101 = 0.625X = Q * D + R = 0.625 * 0.75 + 0.015625 = 0.484375Execution Time = ~0 msOperation Count (Addition/Subtraction) = 2

Algorithms Performance Analysis


          

Implementation Code (Javascript)

Credits