Talk:Division (digital)

From Wikipedia, the free encyclopedia

Contents

[edit] Requested move

This page actually discusses implementing division algorithms for digital circuits (i.e. a divider in a microprocessor math unit). Many other types of division also exist for electronics that are not addressed in this page (e.g. voltage divider, current divider, etc)

[edit] Voting

Add *Support or *Oppose followed by an optional one sentence explanation, then sign your vote with

~~~~

  • Support Jpape 07:21, 6 December 2005 (UTC)

[edit] Discussion

  • It's consistent with Adder (electronics), for whatever that's worth. Though I do agree with the proposal to some extent. --Interiot 07:45, 6 December 2005 (UTC)
  • Move is done. Didn't need an admin to begin with, so I just did it. Be bold! Tedernst | talk 20:46, 9 December 2005 (UTC)

[edit] Non-restoring division

The algorithm as described is inefficient. If the only two digits used are 1 and -1, the latter can be represented as 0, then:

Q = P (positive term) N (the negative term) = ~P = -P-1 Two's complement of N (-N) = P+1

The sum of P and -N = 2*P + 1.

Therefore, the least significant digit for the quotient is always 1, and the overall precision is one less bit than expected.

A better implementation of non-restoring division is to allow digits 0, 1, and -1 (this will require twice the number of state devices for the quotient, though):

P[0] = N
i = 0
while(i<n)
{
  if(abs(P[i]) < 0.25) q[n-(i+1)] = 0;
  else if(P[i] >= 0) { q[n-(i+1)] =  1; P[i+1] = 2*P[i] - D; }
  else               { q[n-(i+1)] = -1; P[i+1] = 2*P[i] + D; }
  i++;
}

Comparing with 0.25 is cheap: the absolute value is less than 0.25 if the two most significant bits of mantissa are equal to the sign bit.

((That's essentially SRT now, isn't it? -Ben))