2

Assuming base b=2, is there a particular advantage in terms of performance when comparing SRT division to non restoring division?

In Non restoring division, for each iteration, the output digits belong to the set {-1,1} which implies that an addition or subtraction is always performed.

In SRT for each iteration the output digits belong to the set {-1,0,1}, where the 0 has the meaning of not performing operation when the partial reminder is particularly small,

Is the only advantage the fact that it allows to bypass some addition subtraction? Does just this thing make the whole division faster? I also suppose that full advantage can be taken if one design such divider asyncronously, am I wrong?

user8469759
  • 618
  • 1
  • 11
  • 25
  • I deleted my answer since you are asking a hardware question better answered by others. – jonk Sep 04 '16 at 20:02
  • You could have left your answer it was useful. – user8469759 Sep 04 '16 at 20:27
  • It's not useful if you are interested in this as a matter of hardware implementations. I wasn't prepared to dig into that aspect as there are at least four different implementations to consider, as well as a fully combinatorial approach which was taken by a company called Bipolar Integrated Technologies [BIT] a long time ago. (I worked with them for a short time.) I can undelete the answer, if you'd like it kept. But in the long term if it only confuses future readers about your question, I'm not sure it is a good idea. Let me know. – jonk Sep 04 '16 at 21:06

2 Answers2

1

SRT division magic is being able to iterate without having to perform carry propagation over all the bits of the dividend (and partial remainder). That means that you can reach higher frequencies, that an single and double precision divider can use the same clock, or that you can cascade several SRT divisors or use higher radices to calculate more than 1 bit per cycle...

In non-restoring, to decide whether you need to add or subtract, you need to complete the previous addition or subtraction and determine precisely whether the result is positive or negative. In SRT, you only need to check a few MSBs (IIRC, around 2 for SRT radix 2, around 7-10 from the remainder and divisor for radix 4, combining division and square root is also possible with moderate additional complexity) : The SRT algorithm only needs an approximate result to decide whether an addition, a subtraction, or nothing is expected.

Addition and subtraction for SRT should be done using "carry-save" (or borrow-save, etc.) adders that don't perform carry propagation. Carry propagation and conversion to two's complement format is really needed only for the few bits needed for the SRT decision : +1/0/-1 for radix-2 or +2/+1/0/-1/-2 for radix 4, etc.

The result is also calculated without carry propagation by keeping two values R = result and RM=R-1, adding one bit to the right for each cycle :

  • SRT = 0 : R'=R & '0', RM'=RM & '1'
  • SRT = +1 : R'=R & '1', RM'=R & '0'
  • SRT = -1 : R'=R' & '1', RM'=R' & '0'
TEMLIB
  • 3,347
  • 1
  • 14
  • 21
-1

The non restoring algorithm simply performs either addition or subtraction accordingly. Whereas in restoring algorithm subtraction is performed and checked wether the result is negative or not and then addition is done if negative result. Thus we can say that per each left shift restoring algorithm checks result and operates appropriately whereas in non restoring algorithm left shift is performed and then add or subtract is done in next step so as our aim is in left shift we get fast answer in non restoring algorithm

Himani
  • 1