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

Claim 2

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.

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

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.

Claim 7

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.

Claim 8

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.

Claim 9

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

Claim 10

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.

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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.

Claim 17

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.

Claim 18

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.

Claim 19

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.

Claim 20

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.

Claim 21

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.

Claim 22

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.

Claim 23

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.

Claim 24

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.

Claim 25

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.

Claim 26

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.

Claim 27

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.

Claim 28

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.

Claim 29

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.

Claim 30

The circuit of claim 27 and further comprising: circuitry coupled to said multiplier for storing said short reciprocal.

Claim 31

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.

Claim 32

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.

Claim 33

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.

Claim 34

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.

Claim 35

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

Claim 36

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.

Claim 37

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.

Claim 38

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.

Claim 39

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.

Claim 40

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.

Claim 41

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.

Claim 42

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.

Claim 43

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.

Claim 44

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.

Claim 45

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.

Claim 46

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.

Claim 47

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.

Claim 48

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.

Claim 49

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.

Claim 50

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.

Claim 51

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.

Claim 52

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.

Claim 53

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.

Claim 56

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.

Claim 57

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

Claim 58

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.

Claim 59

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.

Claim 60

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.

Claim 61

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.

Claim 62

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.

Claim 63

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.

Claim 64

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.

Claim 65

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.

Claim 66

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

Claim 67

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.

Claim 68

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.

Claim 69

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.

Claim 70

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.

Claim 71

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.

Claim 72

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.

Claim 73

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.

Claim 74

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.

Claim 75

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.

Claim 76

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.

Claim 77

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.

Claim 78

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.

Claim 79

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.

Claim 80

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.

Claim 81

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.

Claim 84

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.

Claim 85

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.

Claim 86

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.

Claim 87

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.

Claim 88

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.

Claim 89

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.

Claim 90

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.

Claim 91

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.

Claim 92

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

Claim 93

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.

Claim 94

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.

Claim 95

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.

Claim 96

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.

Claim 97

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.