Method and apparatus for shared radix 4 division and radix 4 square root

A method for calculating a square root comprising the steps of:

• (a) providing a radicand to an initial look-up table;
• (b) providing an initial 2 bits from said initial look-up table to a quotient/root register and a divisor/root multiple selector;
• (c) shifting and complementing the output of said quotient/root register in accordance with said 2 bits from said initial look-up table and providing the result to a carry save adder;
• (d) shifting the output of said carry save adder and providing the shifted output of said carry save adder to a partial remainder/radicand register;
• (e) repeating steps (b)-(d) for a next 2 bits from said initial look-up table;
• (f) repeating steps (b)-(d) for a final bit from said initial look-up table;
• (g) converting a plurality of the upper bits of said partial remainder/radicand register into sign and magnitude form and providing the magnitude to a prediction look-up table;
• (h) providing the output of said prediction look-up table to said quotient/root register and said divisor/root multiple selector;
• (i) shifting and complementing the output of said quotient/root register in accordance with the output of said prediction look-up table and providing the result to said carry save adder;
• shifting the output of said carry save adder and providing said output back to said partial remainder/radicand register;
• and
• (k) repeating steps (g)-(j) above for a plurality of iterations.

An apparatus for performing division and calculating a square root comprising:

• partial remainder/radicand register means for storing a partial remainder or radicand in sum and carry form;
• a carry save adder having an input coupled to an output of said partial remainder/radicand register means and an output coupled to an input of said partial remainder/radicand register means;
• quotient/root register means for storing a quotient or root in Q and Q-1 forms and having an output coupled to said carry save adder;
• a carry look-ahead adder coupled to receive a plurality of the upper bits from said partial remainder/radicand register means;
• prediction look-up table means, having an input coupled to said carry look-ahead adder and an output coupled to said quotient/root register means, for producing a predicted next divisor or root;
• initial look-up table means, having an input coupled to receive a radicand and an output occupied to said quotient/root register means, for producing an initial plurality of digits of a root;
• a complementor coupled between said carry look-ahead adder and said prediction look-up table means for complementing any negative outputs of said carry look-ahead adder;
• a multiplexer for coupling one of the outputs of said prediction look-up table means and said initial look-up table means to said quotient/root register means;
• a divisor/root multiple selector means, coupled to an output of said multiplexer and an output of said quotient/root register means, for shifting and complementing an output of said quotient/root register means with the amount of the shift being determined by the output of said multiplexer and providing said shifted/ complemented output to said carry save adder;
• a shifter coupled to the output of said carry save adder;
• and
• a full mantissa width carry look-ahead adder coupled to an output of said carry save adder.