Method and apparatus for performing the square root function using a rectangular aspect ratio multiplier

• US 5,060,182 A
• Filed: 09/05/1989
• Issued: 10/22/1991
• Est. Priority Date: 09/05/1989
• Status: Expired due to Term

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Cyrix Corp (Texas Instruments, Inc.)
• Inventors: Matula, David W., Brightman, Thomas B., Briggs, Willard S.
• Primary Examiner(s): Shaw, Dale M.
• Assistant Examiner(s): Mai, Tan V.
• Application Number:
  US07/402,822
• Time in Patent Office: 777 Days
• Field of Search: 364/752, 364/736, 364/715.01, 364/729
• US Class Current: 708/605
• CPC Class Codes: G06F 7/5525 Roots or inverse roots of single operands

Abstract

A method and apparatus for performing the square root function which first comprises approximating the short reciprocal of the square root of the operand. A reciprocal bias adjustment factor is added to the approximation and the result truncated to form a correctly biased short reciprocal. The short reciprocal is then multiplied by a predetermined number of the most significant bits of the operand and the product is appropriately truncated to generate a first root digit value. The multiplication takes place in a multiplier array having a rectangular aspect ratio with the long side having a number of bits essentially as large as the number of bits required for the desired full precision root. The short side of the multiplier array has a number of bits slightly greater by several guard bits than the number of bits required for a single root digit value, which is also determined to be the number of bits in the short reciprocal. The root digit value is squared and the exact square is subtracted from the operand to yield an exact remainder. Succeeding new root digit values are determined by multiplying the short reciprocal by the appropriately shifted current remainder, selectively adding a digit bias adjustment factor and truncating the product. The root digit values are appropriately shifted and accumulated to form a partial root. The described steps are repeated to serially generate root digit values and partial roots with corresponding new exact remainders.

Claims

1. A circuit for calculating an exact square root of an operand, comprising:

circuitry for obtaining a short reciprocal of the square root of the operand;

circuitry for computing a first root digit value by multiplying a short reciprocal of the square root of the operand by said operand;

circuitry for computing a first remainder as the difference between said operand and a square of said first root digit value;

circuitry for computing a second root digit value by multiplying said short reciprocal by one half of said first remainder;

circuitry for generating a product of said second root digit value and a sum of said second root digit value and twice said first root digit value;

circuitry for computing a second remainder as the difference between said first remainder and said product of said second root digit value and said sum of said second root digit value and twice said first root digit value, said first and second root digit values and said first and second remainders calculated such that said first remainder and said second remainder have magnitudes corresponding to less than one unit in the last place of said first root digit value and said second root digit value, respectively; and

circuitry for computing a partial root, said partial root comprising a sum of all appropriately shifted root digit values.

2. The circuit of claim 1 wherein said circuitry for obtaining said short reciprocal comprises:

circuitry for adding a reciprocal bias adjustment factor to an approximate reciprocal to yield a sum and truncating said sum to yield said short reciprocal, said reciprocal bias adjustment factor chosen to offset accumulated error in the approximate reciprocal and bias said short reciprocal to produce root digit values which, when accumulated to form a partial root, are always at most one unit in the last place greater than or exactly equal to an exact value of the square root truncated to a predetermined number of bits.

3. The circuit of claim 1 wherein said circuitry for computing a first root digit value comprises:

circuitry for selectively adding a digit bias adjustment factor to a product of said short reciprocal and said operand if said product is positive; and

circuitry for truncating said product to a predetermined number of bits to generate said root digit value, said digit bias adjustment factor operable to offset error introduced by said truncation.

4. The circuit of claim 1 wherein said first root digit value gives rise to a negative first remainder when said first root digit value is greater than an exact value of the square root truncated to a predetermined number of bits, said negative remainder causing said second root digit value to be negative, thereby causing said partial root to have a value less than the value of said first root digit value.

5. The circuit of claim 1 wherein said circuitry for computing a partial root comprises circuitry for calculating a sum of the appropriately shifted root digit values, said sum forming a partial root of a partial root and remainder pair, said pair composing the exact square root of the operand.

6. The circuit of claim 1 wherein said circuitry for obtaining said short reciprocal comprises:

look-up table circuitry for storing a plurality of reciprocal seed values;

retrieval circuitry coupled to said look-up table circuitry for retrieving a particular reciprocal seed value approximately equal to the reciprocal of the square root of the operand;

circuitry for computing a first reciprocal approximation equal to the product of said particular reciprocal seed value and the difference of three-halves and a second term, said second term being the product of said particular seed value and a third term, said third term being the product of one-half of said operand and said particular reciprocal seed value; and

circuitry for computing a second reciprocal approximation equal to the product of said first reciprocal approximation and the difference of three halves and a fourth term, said fourth term being the product of said first reciprocal approximation and a fifth term, said fifth term being the product of one-half of the operand and said first reciprocal approximation.

7. The circuit of claim 6 wherein said circuitry for obtaining said short reciprocal further comprises:

circuitry for computing said short reciprocal equal to the truncated sum of a prior reciprocal approximation and a reciprocal bias adjustment factor chosen to offset accumulated error in said prior reciprocal approximation and bias said short reciprocal to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to the exact value of the square root truncated to a predetermined number of bits.

8. The circuit of claim 7 wherein said prior reciprocal approximation is equal to said second reciprocal approximation.

9. The circuit of claim 7 wherein said reciprocal bias adjustment factor is equal to the sum of a first and a second term, said first term equal to 2^-k in the Nth place where N is equal to the number of bits of the radix of the root digit values and k is a predetermined number of guard bits, said second term being large enough to bias said short reciprocal such that said short reciprocal is larger than an exact reciprocal of the square root of the operand and said second term being small enough such that said first and second remainders correspond to less than one unit in the last place of said first and second root digit values, respectively.

10. The circuit of claim 9 wherein said reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 1/64 of a unit in the Nth place.

11. The circuit of claim 1 wherein said circuitry for obtaining said short reciprocal comprises:

look-up table circuitry for storing a plurality of approximate reciprocal values;

retrieval circuitry coupled to said look-up table circuitry for retrieving a particular approximate reciprocal value approximately equal to the reciprocal of the square root of the operand.

12. The circuit of claim 11 wherein said circuitry for obtaining said short reciprocal further comprises:

circuitry for adding a reciprocal bias adjustment factor to said particular approximate reciprocal value to yield a sum and truncating said sum to yield said short reciprocal, said reciprocal bias adjustment factor chosen to offset error in the approximate reciprocal value and bias said short reciprocal to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to the exact value of the square root truncated to a predetermined number of bits.

13. The circuit of claim 11 wherein said reciprocal bias adjustment factor is equal to the sum of a first and a second term, said first term equal to 2^-k in the Nth place where N is equal to the number of bits of the radix of the root digit values and k is a predetermined number of guard bits, said second term being large enough to bias said short reciprocal such that said short reciprocal is larger than an exact reciprocal of the square root of the operand and said second term being small enough such that said first and second remainders correspond to less than one unit in the last place of said first and second root digit values, respectively.

14. The circuit of claim 13 wherein said reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 1/64 of a unit in the Nth place.

15. The circuit of claim 1 wherein said circuitry for obtaining said short reciprocal comprises:

look-up table circuitry for storing a plurality of short reciprocal values; and

retrieval circuitry coupled to said look-up table circuitry for retrieving a particular short reciprocal value approximately equal to the reciprocal of the square root of the operand said particular short reciprocal value comprising the truncated sum of an approximate reciprocal value of the square root of the operand and a reciprocal bias adjustment factor chosen to offset error in said approximate reciprocal value and bias said short reciprocal value to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to the exact value of the square root of the operand truncated to a predetermined number of bits.

16. The circuit of claim 15 wherein said reciprocal bias adjustment factor is equal to the sum of a first and a second term, said first term equal to 2^-k in the Nth place were N is equal to the number of bits of the radix of the root digit values and k is a predetermined number of guard bits, said second term being large enough to bias said short reciprocal such that said short reciprocal is larger than an exact reciprocal of the square root of the operand and said second term being small enough such that said first and second remainders correspond to less than one unit in the last place of said first and second root digit values, respectively.

17. The circuit of claim 16 wherein said reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 1/64 of a unit in the Nth place.

18. The circuit of claim 1, wherein said circuitry for obtaining said short reciprocal comprises:

look-up table circuitry for storing a plurality of reciprocal seed values;

retrieval circuitry for retrieving a particular reciprocal seed value associated with the operand;

circuitry for computing an approximate reciprocal value equal to the product of said particular reciprocal seed value and the difference of three-halves and a second term, said second term being the product of said particular reciprocal seed value and a third term, said third term being the product of one-half of said operand and said particular reciprocal seed value.

19. The circuit of claim 18 wherein said circuitry for obtaining said short reciprocal further comprises:

circuitry for adding a reciprocal bias adjustment factor to said approximate reciprocal value to yield a sum and truncating said sum to yield said short reciprocal, said reciprocal bias adjustment factor chosen to offset error in said approximate reciprocal value and bias said short reciprocal to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to the exact value of the square root truncated to a predetermined number of bits.

20. The circuit of claim 19 wherein said reciprocal bias adjustment factor is equal to the sum of a first and a second term, said first term equal to 2^-k in the Nth place where N is equal to the number of bits of the radix of the root digit values and k is a predetermined number of guard bits, said second term being large enough to bias said short reciprocal such that said short reciprocal is larger than an exact reciprocal of the square root of the operand and said second term being small enough such that said first and second remainders correspond to less than one unit in the last place of said first and second root digit values, respectively.

21. The circuit of claim 20 wherein said reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 1/64 of a unit in the Nth place.

22. The circuit of claim 1 wherein said circuitry for obtaining said short reciprocal comprises:

circuitry for obtaining an approximate reciprocal value approximately equal to the reciprocal of the square root of the operand; and

circuitry for adding a reciprocal bias adjustment factor to said approximate reciprocal value to yield a sum and truncating said sum to yield said short reciprocal, said reciprocal bias adjustment factor chosen to offset error in said approximate reciprocal value and bias said short reciprocal to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to the exact value of the square root truncated to a predetermined number of bits.

23. The circuit of claim 22 wherein said reciprocal bias adjustment factor is equal to the sum of a first and a second term, said first term equal to 2^-k in the Nth place where N is equal to the number of bits of the radix of the root digit values and k is a predetermined number of guard bits, said second term being large enough to bias said short reciprocal such that said short reciprocal is larger than an exact reciprocal of the square root of the operand and said second term being small enough such that said first and second remainders correspond to less than one unit in the last place of said first and second root digit values, respectively.

24. The circuit of claim 23 wherein said reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 1/64 of a unit in the Nth place.

25. The circuit of claim 1 and further comprising:

circuitry for decrementing a final partial root generated by one unit in the last place if a final remainder generated is negative.

26. The circuit of claim 25 and further comprising:

circuitry for correcting said final remainder by adding twice the decremented final partial root plus one unit in the last place of the last root digit to said final remainder if said final remainder is negative.

27. A circuit for calculating an exact square root of an operand, comprising:

a rectangular array multiplier;

circuitry coupled to said multiplier for obtaining a short reciprocal of the square root of the operand;

circuitry coupled to said multiplier for facilitating the multiplication of said short reciprocal by said operand to yield a first product;

circuitry for adding a first digit bias adjustment factor and truncating said first product to have less bits than said operand to yield a first root digit value;

circuitry, including said multiplier, for generating a square of said first root digit value;

circuitry for computing a difference between the operand and said square of said first root digit value to yield a first remainder;

circuitry coupled to said multiplier for facilitating the multiplication of said short reciprocal by one half of said first remainder to yield a second product;

circuitry for adding a second digit bias adjustment factor and truncating said second product to have less bits than the operand to yield a second root digit value;

circuitry for computing a first partial root as the sum of the appropriately shifted first and second root digit values;

circuitry, including said multiplier, for generating a product of said second root digit value and the sum of said second root digit value and twice said first root digit value; and

circuitry for computing the difference between said first remainder and said product of said second root digit value and the sum of said second root digit value and twice said first root digit value to yield a second remainder;

circuitry coupled to said multiplier for facilitating the multiplication of said short reciprocal by one half of said second remainder to yield a third product;

circuitry for truncating said third product to have less bits than the operand to yield a third root digit value;

circuitry for computing a second partial root as the sum of the appropriately shifted first, second and third root digit values;

circuitry, including said multiplier, for generating a product of said third root digit value and the sum of said third root digit value and twice said first partial root; and

circuitry for computing the difference between said second remainder and said product of said third root digit value and the sum of said third root digit value and twice said first partial root to yield a third remainder, said first, second and third root digit values calculated such that said first, second and third remainders have magnitudes corresponding to less than one unit in the last place of said first, second and third root digit values, respectively.

28. The circuit of claim 27 and further comprising:

circuitry coupled to said multiplier for storing said short reciprocal.

29. The circuit of claim 27 wherein said circuitry for obtaining a short reciprocal comprises:

circuitry for adding a reciprocal bias adjustment factor chosen to offset accumulated error in an approximate reciprocal and bias said short reciprocal to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to an exact value of the square root truncated to a predetermined number of bits.

30. The circuit of claim 29 wherein said root digit values give rise to a negative remainder when said root digit values are greater than said exact value, said negative remainder causing a succeeding root digit value to be negative, thereby causing a product of said succeeding root digit value and a term comprising the sum of said succeeding root digit value and twice the previous partial root operable to reduce the magnitude of said negative remainder.

31. The circuit of claim 27 wherein said circuitry for obtaining a short reciprocal of the square root of the operand, comprises:

look-up table circuitry for storing a plurality of reciprocal seed values;

retrieval circuitry coupled to said look-up table circuitry for retrieving a particular reciprocal seed value approximately equal to the reciprocal of the operand;

circuitry for computing a first reciprocal approximation equal to the product of said particular reciprocal seed value and the difference of three-halves and a second term, said second term being the product of said particular reciprocal seed value and a third term, said third term being the product of one-half of said operand and said particular reciprocal seed value; and

circuitry for computing a second reciprocal approximation equal to the product of said first reciprocal approximation and the difference of three-halves and a fourth term, said fourth term being the product of said first reciprocal approximation and a fifth term, said fifth term being the product of one-half of said operand and said first reciprocal approximation.

32. The circuit of claim 31, wherein said circuitry for obtaining a short reciprocal of the square root of the operand further comprises:

circuitry associated with said multiplier for computing said short reciprocal equal to the truncated sum of a prior reciprocal approximation and a reciprocal bias adjustment factor chosen to offset accumulated error in said prior reciprocal approximation and bias said short reciprocal to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to the exact value of the square root truncated to a predetermined number of bits.

33. The circuit of claim 32 wherein said prior reciprocal approximation is equal to the said second reciprocal approximation.

34. The circuit of claim 32 wherein said reciprocal bias adjustment factor is equal to the sum of a first and a second term, said first term equal to 2^-k in the Nth place where N is equal to the number of bits of the radix of the root digit values and k is a predetermined number of guard bits, said second term being large enough to bias said short reciprocal such that said short reciprocal is larger than an exact reciprocal of the square root of the operand and said second term being small enough such that said first, second and third remainders correspond to less than one unit in the last place of said first, second and third root digit values.

35. The circuit of claim 32 wherein said reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 1/64 of a unit in the Nth place.

36. The circuit of claim 27 and further comprising:

circuitry for decrementing a final partial root digit value generated by one unit in the last place if a final remainder generated is negative.

37. The circuit of claim 36 and further comprising:

circuitry for correcting said final remainder by adding twice the decremented final partial root plus one unit in the last place of the last root digit to said final remainder if said final remainder is negative.

38. The circuit of claim 27 wherein said circuitry for obtaining a short reciprocal comprises:

look-up table circuitry for storing a plurality of approximate reciprocal values;

retrieval circuitry coupled to said look-up table circuitry for retrieving a particular approximate reciprocal value approximately equal to a reciprocal of the square root of the operand.

39. The circuit of claim 38 wherein said circuitry for obtaining a short reciprocal further comprises:

circuitry for adding a reciprocal bias adjustment factor to said particular approximate reciprocal value to yield a sum and truncating said sum to yield said short reciprocal, said reciprocal bias adjustment factor chosen to offset error in said particular approximate reciprocal value and bias said short reciprocal to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to the exact value of the square root truncated to a predetermined number of bits.

41. The circuit of claim 39 wherein said reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 1/64 of a unit in the Nth place.

42. The circuit of claim 27 wherein said circuitry for obtaining a short reciprocal comprises:

look-up table circuitry for storing a plurality of short reciprocal values, each of said short reciprocal values comprising the truncated sum of an approximate reciprocal value and a reciprocal bias adjustment factor chosen to offset error in said approximate reciprocal value and bias said short reciprocal value to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to the exact value of the square root truncated to a predetermined number of bits; and

retrieval circuitry coupled to said look-up table circuitry for retrieving a particular short reciprocal value approximately equal to a reciprocal of the square root of the operand.

43. The circuit of claim 41 wherein said reciprocal bias adjustment factor is equal to the sum of a first and a second term, said first term equal to 2^-k in the Nth place where N is equal to the number of bits of the radix of the root digit values and k is a predetermined number of guard bits, said second term being large enough to bias said short reciprocal such that said short reciprocal is larger than an exact reciprocal of the square root of the operand and said second term being small enough such that said first, second and third remainders correspond to less than one unit in the last place of said first, second and third root digit values.

44. The circuit of claim 42 wherein said reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 1/64 of a unit in the Nth place.

45. The circuit of claim 27 wherein said circuitry for obtaining a short reciprocal comprises:

look-up table circuitry for storing a plurality of reciprocal seed values;

retrieval circuitry for retrieving a particular reciprocal seed value approximately equal to a reciprocal of the square root of the operand; and

circuitry for computing the product of said particular reciprocal seed value and the difference of three-halves and a second term, said second term being the product of said particular reciprocal seed value and a third term, said third term being the product of one-half of said operand and said particular reciprocal seed value.

46. The circuit of claim 45 wherein said circuitry for obtaining a short reciprocal further comprises:

circuitry for adding a reciprocal bias adjustment factor to said approximate reciprocal value to yield a sum and truncating said sum to yield said short reciprocal, said reciprocal bias adjustment factor chosen to offset error in said approximate reciprocal to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to the exact value of the square root truncated to a predetermined number of bits.

47. The circuit of claim 46 wherein said reciprocal bias adjustment factor is equal to the sum of a first a and second term, said first term equal to 2^-k in the Nth place where N is equal to the number of bits of the radix of the root digit values and k is a predetermined number of guard bits, said second term being large enough to bias said short reciprocal such that said short reciprocal is larger than an exact reciprocal of the square root of the operand and said second term being small enough such that said first, second and third remainders correspond to less than one unit in the last place of said first, second and third root digit values.

48. The circuit of claim 46 wherein said reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 1/64 of a unit in the Nth place.

49. The circuit of claim 46 wherein said reciprocal bias adjustment factor is equal to the sum of a first and a second term, said first term equal to 2^-k in the Nth place where N is equal to the number of bits of the radix of the root digit values and k is a predetermined number of guard bits, said second term being large enough to bias said short reciprocal such that said short reciprocal is larger than an exact reciprocal of the square root of the operand and said second term being small enough such that said first, second and third remainders correspond to less than one unit in the last place of said first, second and third root digit values.

50. The circuit of claim 27 wherein said circuitry for obtaining a short reciprocal comprises:

circuitry for obtaining an approximate reciprocal value approximately equal to a reciprocal of the square root of the operand; and

circuitry for adding a reciprocal bias adjustment factor to said approximate reciprocal value to yield a sum and truncating said sum to yield said short reciprocal, said reciprocal bias adjustment factor chosen to offset error in said approximate reciprocal value and bias said short reciprocal to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to the exact value of the square root truncated to a predetermined number of bits.

51. The circuit of claim 50 wherein said reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 1/64 of a unit in the Nth place.

40. The circuit of claim 40 wherein said reciprocal bias adjustment factor is equal to the sum of a first and a second term, said first term equal to 2^-k in the Nth place where N is equal to the number of bits of the radix of the root digit values and k is a predetermined number of guard bits, said second term being large enough to bias said short reciprocal such that said short reciprocal is larger than an exact reciprocal of the square root of the operand and said second term being small enough such that said first, second and third remainders correspond to less than one unit in the last place of said first, second and third root digit values.

52. A method of calculating an exact square root of an operand, comprising the steps of:

inputting a short reciprocal of the operand into a first input of a multiplier circuit;

inputting a remainder value initially equal to the operand into a second input of the multiplier circuit;

computing a root digit value by multiplying in the multiplier circuit the short reciprocal of the operand by a first term equal to one half of the remainder value, the first term initially equal to the operand;

computing a partial root, the partial root comprising a sum of all appropriately shifted root digit values;

computing a new remainder as the difference between the remainder value and a product of the root digit value and a sum of the root digit value and a second term equal to twice the previous partial root, the second term initially equal to zero; and

generating a desired number of root digit values by reiterating the steps of inputting a short reciprocal, inputting a remainder value, computing a root digit value, computing a partial root and computing a new remainder, substituting a new remainder for the remainder value when reiterating the steps of inputting a remainder value, computing a root digit value and computing a remainder, the root digit values computed such that all subsequent remainders have magnitudes corresponding to less than one unit in the last place of a preceding root digit value.

53. The method of claim 52 wherein the step of computing a root digit value comprises the steps of:

selectively adding a digit bias adjustment factor to a product of the short reciprocal and the operand if the product is positive; and

truncating the product to a predetermined number of bits to generate the root digit value, the digit bias adjustment factor operable to offset error introduced by the truncation.

54. The method of claim 52 and further comprising the step of obtaining a short reciprocal of the operand.

55. The method of claim 54 wherein the step of obtaining a short reciprocal comprises the step of adding a reciprocal bias adjustment factor to a prior reciprocal approximation to yield a sum and truncating the sum to yield the short reciprocal, the reciprocal bias adjustment factor chosen to offset accumulated error in the prior reciprocal approximation and bias the short reciprocal to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit greater than or exactly equal to an exact value of the square root truncated to a predetermined number of bits.

56. The method of claim 55 wherein the root digit values give rise to a negative remainder when the root digit values are greater than the exact value, the negative remainder causing a subsequent root digit value to be negative, thereby causing a product of the subsequent root digit and a term comprising the sum of the subsequent root digit and twice the previous partial root operable to reduce the magnitude of the negative remainder.

57. The method of claim 55 wherein the reciprocal bias adjustment factor is equal to the sum of a first and a second term, the first term equal to 2^-k in the Nth place where N is equal to the number of bits of the radix of the root digit values and k is a predetermined number of guard bits, the second term being large enough to bias the short reciprocal such that the short reciprocal is larger than an exact reciprocal of the square root of the operand and the second term being small enough to yield remainders corresponding to less than one unit in the last place of a preceding root digit value.

58. The method of claim 55, wherein the reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 164 of a unit in the Nth place.

59. The method of claim 52 wherein the final partial root is corrected by decrementing the final partial root by one unit in the last place if a final remainder generated is negative.

60. The method of claim 59 wherein if the final remainder is negative, the final remainder is corrected by adding twice the decremented final partial root plus one unit in the last place of the last root digit to said final remainder if said final remainder is negative.

61. The method of claim 54 wherein the step of obtaining a short reciprocal of the operand comprises the steps of:

retrieving a reciprocal seed value from a table containing a plurality of values;

computing a first reciprocal approximation equal to the product of the particular reciprocal seed value and the difference of three-halves and a second term, the second term being the product of the particular reciprocal seed value and a third term, the third term being the product of one-half of the operand and the particular reciprocal seed value; and

computing a second reciprocal approximation equal to the product of the first reciprocal approximation and the difference of three-halves and a fourth term, the fourth term being the product of the first reciprocal approximation and a fifth term, the fifth term being the product of one-half of the operand and the first reciprocal approximation.

62. The method of claim 61 wherein the step of obtaining a short reciprocal of the operand further comprises the step of:

computing the short reciprocal equal to the truncated sum of a prior reciprocal approximation and a reciprocal bias adjustment factor chosen to offset accumulated error in the prior reciprocal approximation and bias the short reciprocal to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to the exact value of the square root truncated to a predetermined number of bits.

63. The method of claim 62 wherein the prior reciprocal approximation is equal to the second reciprocal approximation.

64. The method of claim 62, wherein the reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 1/64 of a unit in the Nth place.

65. The method of claim 54 wherein the step of obtaining a short reciprocal comprises the steps of:

retrieving a particular approximate reciprocal value approximately equal to a reciprocal of the square root of the operand from a table storing a plurality of the approximate reciprocal values; and

adding a reciprocal bias adjustment factor to the particular approximate reciprocal value to yield a sum and truncating the sum of yield the short reciprocal, the reciprocal bias adjustment factor chosen to offset error in the particular approximate reciprocal value and bias the short reciprocal to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to the exact value of the square root truncated to a predetermined number of bits.

66. The method of claim 65 wherein the reciprocal bias adjustment factor is equal to the sum of a first and a second term, the first term equal to 2^-k in the Nth place where N is equal to the number of bits of the radix of the root digit values and k is a predetermined number of guard bits, the second term being large enough to bias the short reciprocal such that the short reciprocal is larger than an exact reciprocal of the square root of the operand and the second term being small enough to yield remainders corresponding to less than one unit in the last place of a preceding root digit value.

67. The method of claim 66 wherein the reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 1/64 of a unit in the Nth place.

68. The method of claim 54 wherein the step of obtaining a short reciprocal comprises the step of:

retrieving a short reciprocal approximately equal to a reciprocal of the square root of the operand from a table storing a plurality of short reciprocals, each of the short reciprocals comprising the truncated sum of an approximate reciprocal value and a bias adjustment factor chosen to offset error in the approximate reciprocal value and bias the short reciprocal to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to the exact value of the square root truncated to a predetermined number of bits.

69. The method of claim 68 wherein the reciprocal bias adjustment factor is equal to the sum of a first and a second term, the first term equal to 2^-k in the Nth place where N is equal to the number of bits of the radix of the root digit values and k is a predetermined number of guard bits, the second term being large enough to bias the short reciprocal such that the short reciprocal is larger than an exact reciprocal of the square root of the operand and the second term being small enough to yield remainders corresponding to less than one unit in the last place of a preceding root digit value.

70. The method of claim 69 wherein the reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 1/64 of a unit in the Nth place.

71. The method of claim 54 wherein the step of obtaining a short reciprocal comprises the steps of:

retrieving a particular reciprocal seed value approximately equal to a reciprocal of the square root of the operand from a table storing a plurality of reciprocal seed values; and

computing an approximate reciprocal value equal to the product of the particular reciprocal seed value and the difference of three-halves and a second term, the second term being the product of the particular reciprocal seed value and a third term, the third term being the product of one-half of the operand and the particular reciprocal seed value.

72. The method of claim 71 wherein the step of obtaining a short reciprocal further comprises the steps of:

adding a reciprocal bias adjustment factor to the approximate reciprocal value to yield a sum and truncating the sum to yield the short reciprocal, the reciprocal bias adjustment factor chosen to offset error in the approximate reciprocal value and bias the short reciprocal to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to the exact value of the square root truncated to a predetermined number of bits.

73. The method of claim 72 wherein the reciprocal bias adjustment factor is equal to the sum of a first and a second term, the first term equal to 2^-k in the Nth place where N is equal to the number of bits of the radix of the root digit values and k is a predetermined number of guard bits, the second term being large enough to bias the short reciprocal such that the short reciprocal is larger than an exact reciprocal of the square root of the operand and the second term being small enough to yield remainders corresponding to less than one unit in the last place of a preceding root digit value.

74. The method of claim 73 wherein the reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 1/64 of a unit in the Nth place.

75. The method of claim 54 wherein the step of obtaining a short reciprocal comprises the steps of:

obtaining an approximate reciprocal value approximately equal to a reciprocal of the square root of the operand; and

adding a reciprocal bias adjustment factor to the approximate reciprocal value to yield a sum and truncating the sum to yield the short reciprocal, the unique reciprocal bias adjustment factor chosen to offset error in the approximate reciprocal value and bias the short reciprocal to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to the exact value of the square root truncated to a predetermined number of bits.

76. The method of claim 75 wherein the reciprocal bias adjustment factor is equal to the sum of a first and a second term, the first term equal to 2^-k in the Nth place where N is equal to the number of bits of the radix of the root digit values and k is a predetermined number of guard bits, the second term being large enough to bias the short reciprocal such that the short reciprocal is larger than an exact reciprocal of the square root of the operand and the second term being small enough to yield remainders corresponding to less than one unit in the last place of a preceding root digit value.

77. The method of claim 76 wherein the reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 1/64 of a unit in the Nth place.

78. The method of claim 52 wherein if a final remainder is negative, the final remainder is corrected by adding twice the decremented final partial root plus one unit in the last place of the last root digit to said final remainder if said final remainder is negative.

79. A method of calculating a square root of an operand using a rectangular array multiplier comprising the steps of:

obtaining a short reciprocal of the square root of the operand;

computing a first product by multiplying the short reciprocal by the operand;

adding a predetermined digit bias adjustment factor to the first product,

truncating the first product to have less bits than the operand to yield a first root digit value;

computing in the rectangular array multiplier the square of the first root digit value;

computing a first remainder as the difference between the operand and the square of the first root digit value;

computing a subsequent product by multiplying the short reciprocal by the appropriately shifted first remainder;

selectively adding a predetermined digit bias adjustment factor to the subsequent product if the subsequent product is positive;

truncating the subsequent product to have less bits than the operand to yield a subsequent root digit value;

computing a partial root as the sum of all appropriately shifted root digit values;

computing a new remainder as the difference between the first remainder and the product of the subsequent digit value and the sum of the subsequent root digit value and twice the preceding partial root; and

generating a desired number of root digit values by reiterating the steps of computing a subsequent product, selectively adding a predetermined digit bias adjustment factor, truncating the subsequent product, computing the product of the subsequent root digit value and the sum of the subsequent root digit value and twice the previous partial root and computing a new remainder, the first root digit value, the subsequent root digit value and all succeeding root digit values calculated such that subsequent remainders have magnitudes corresponding to less than one unit in the last place of a preceding root digit value.

80. The method of claim 79 wherein the step of computing the square of the first root digit value and the step of computing a first remainder are accomplished during a single multiplying step.

81. The method of claim 79 wherein the step of obtaining a short reciprocal of the operand comprises the step of adding a reciprocal bias adjustment factor to an approximate reciprocal to yield a sum and truncating the sum to yield the short reciprocal, the reciprocal bias adjustment factor chosen to offset accumulated error in the approximate reciprocal and bias the short reciprocal to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to the exact value of the square root truncated to a predetermined number of bits.

82. The method of claim 80 wherein the root digit values give rise to a negative remainder when a root digit value is greater than the exact value of a particular root digit, the negative remainder causing a subsequent root digit value to be negative, thereby causing a product of the subsequent root digit and a term comprising the sum of the subsequent root digit value and twice the previous partial root operable to reduce the magnitude of the negative remainder.

83. The method of claim 82, wherein the reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 1/64 of a unit in the Nth place.

84. The method of claim 81 wherein the reciprocal bias adjustment factor is equal to the sum of a first and a second term, the first term equal to 2^-k in the Nth place where N is equal to the number of bits of the radix of the root digit values and k is a predetermined number of guard bits, the second term being large enough to bias the short reciprocal such that the short reciprocal is larger than an exact reciprocal of the square root of the operand and the second term being small enough to yield remainders corresponding to less than one unit in the last place of a preceding root digit value.

85. The method of claim 84, wherein the reciprocal bias adjustment factor is equal to the sum of a first term being 1/4 of a unit in the Nth place and a second term being 1/64 of a unit in the Nth place.

86. The method of claim 79 wherein the step of obtaining a short reciprocal comprises the steps of:

retrieving a particular reciprocal seed value from a table containing a plurality of seed values;

computing a first reciprocal approximation equal to the product of the the particular reciprocal seed value and the difference of three-halves and a second term, the second term being the product of the particular reciprocal seed value and a third term, the third term being the product of one-half of the operand and the particular reciprocal seed value; and

computing a second reciprocal approximation equal to the product of the first reciprocal approximation and the difference of three-halves and a fourth term, the fourth term being the product of the first reciprocal approximation and a fifth term, the fifth term being the product of one-half of the operand and the first reciprocal approximation.

87. The method of claim 86 wherein the step of obtaining a short reciprocal of the operand further comprises the step of:

computing the short reciprocal equal to the truncated sum of a prior reciprocal approximation and a reciprocal bias adjustment factor chosen to offset accumulated error in the prior reciprocal approximation and bias the short reciprocal to produce root digit values which, when accumulated to form a partial root, yield a partial root at most one unit in the last place greater than or exactly equal to the exact value of the square root truncated to a predetermined number of bits.

88. The method of claim 87 wherein the prior reciprocal approximation is equal to the second reciprocal approximation.

89. The method of claim 79 wherein the square root is corrected by decrementing a final partial root generated by one unit in the last place if a final remainder generated is negative.

90. The method of claim 89 wherein if the final remainder is negative, the final remainder is corrected by adding twice the decremented final partial root plus one unit in the last place of the last root digit to said final remainder if said final remainder is negative.

91. The method of claim 79 wherein if the final remainder is negative, the final remainder is corrected by adding twice the decremented final partial root plus one unit in the last place of the last root digit to said final remainder if said final remainder is negative.

92. A circuit for calculating an exact square root of an operand, comprising:

a multiplier circuit;

circuitry for obtaining a short reciprocal of the square root of the operand;

circuitry, including said multiplier circuit, for computing a root digit value by multiplying a short reciprocal of the square root of the operand by an appropriately shifted remainder value initially equal to said operand;

circuitry, including said multiplier circuit, for computing a new remainder as the difference between said remainder value initially equal to said operand and a product of the root digit value and a sum of the root digit value and a term equal to twice the sum of all appropriately shifted preceding root digits values, said term initially equal to zero;

circuitry for generating a succeeding root digit value by substituting said new remainder for said remainder value and inputting said new remainder into said circuitry for computing a root digit value, said root digit value and said succeeding root digit value computed such that all remainders have magnitudes corresponding to less than one unit in the last place of a preceding root digit value; and

circuitry for computing a partial root, said partial root comprising a sum of all appropriately shifted root digit values.