Division algorithm: Difference between revisions

Revision as of 23:07, 12 December 2006

Revision as of 05:55, 22 February 2007

Line 18:

===Restoring division===

Restoring division operates on [[fixed-point]] fractional numbers and depends on the following assumptions:

* <math>N < D</math>

* <math>1/2 \le< N,D < 1</math>

The quotient digits ''q'' are formed from the digit set {0,1}.

Line 25:

The basic algorithm for binary (radix 2) restoring division is:

P[0] := N

'''for''' i = n-1..0 '''do''' ''* for example 31..0 for 32 bits''

i := 0

P := 2P - D ''* trial subtraction from shifted value''

'''whileif''' (iP <> n)0 '''dothen'''

TP[i+1] := 2*P[i] - D

'''if''' TP[ q(i+) := 1] > 0 '''then'* result-bit 1''

q[n-(i+1)] := 1

P[i+1] := TP[i+1]

'''else'''

q[n-(i+1)] := 0 ''* result-bit 0''

P := P + D ''* new partial remainder is (restored) shifted value''

P[i+1] := TP[i+1] + D

'''end if'''

'''end while'''

i := i + 1

'''end while'''

'''where''' ''N=Numerator, D=Denominator, n=#bits, P=Partial remainder, q(i)=bit #i of quotient''

Non-performing restoring division is similar to restoring division except that the value of <code>2*P[i]</code> is saved, so ''D'' does not need to be added back in for the case of <code>TP[i] &le; 0</code>.