Method and apparatus for computing square roots of binary numbers

Claim 2

A binary number square root calculator comprising: input means for receiving a N-bit operand A; seed means connected to said input means for determining a seed value X(0) of n bits from said operand A as follows: X(0)=(2.sup.max -A)*2.sup.-0.5max-1 ; said seed means including: a complementer means for complementing said operand A; shifter means for shifting said complemented operand -A by -0.5*max-1; and adder means for adding 2 0 .5*max-1 to a shifted complemented operand -A; iteration means connected to said seed means for performing a plurality of iterations of the following: X(n+1)=X(0)+X(n)*X(n)*2.sup.-0.5max-1 where max is the weight of the most significant bit of the smallest perfect binary square higher than the most significant bit of operand A; and root means connected to said iteration means for determining a last iteration and calculating a square root of the operand A from the results of the last iteration X(last) of the iteration means as follows: R=2.sup.0.5*max -X(last).

Claim 3

A binary number square root calculator comprising: input means for receiving an N-bit operand A; seed means connected to said input means for determining a seed value X(0) of n bits from said operand A; iteration means connected to said seed means for performing a plurality of iterations of the following: X(n+1)=X(0)+X(n)*X(n)*2.sup.-0.5max-1 where max is the weight of the most significant bit of the smallest perfect binary square higher than the most significant bit of operand A; said iteration means including: multiplexer-shifter means for providing a shifted and non-shifted output of a selected first or second input, said shifter output being shifted by -0.5*max-1; multiplier means for multiplying said shifted and non-shifted outputs to produce a product; adder means for adding said seed value X(0) to said product; and feedback means for feeding back an output of said adder means to said second input of said multiplexer-shifter means; said seed means being connected to said first input of said multiplexer-shifter means; and root means connected to said iteration means for determining a last iteration and calculating a square root of the operand A from the results of the last iteration X(last) of the iteration means as follows: R=2.sup.0.5*max -X(last).

Claim 4

A binary number square root calculator comprising: input means for receiving an N-bit operand A; seed means connected to said input means for determining a seed value X(0) of n bits from said operand A; iteration means connected to said seed means for performing a plurality of iterations of the following: X(n+1)=X(0)+X(n)*X(n)*2.sup.-0.5max-1 where max is the weight of the most significant bit of the smallest perfect binary square higher than the most significant bit of operand A; said iteration means including: multiplexer-shifter means for providing a shifted and non-shifted output of a selected first or second input, said shifter output being shifted by -0.5*max-1; multiplier means for multiplying said shifted and non-shifted outputs to produce a product; adder means for adding said seed value X(0) to said product; and feedback means for feeding back an output of said adder means to said second input of said multiplexer-shifter means; said seed means being connected to said first input of said multiplexer-shifter means; and root means connected to said iteration means for determining a last iteration and calculating a square root of the operand A from the results of the last iteration X(last) of the iteration means as follows: R=2.sup.0.5*max -X(last).

Claim 5

A binary number square root calculator comprising: input means for receiving a N-bit operand A of maximum binary width of MAX; scaling means for determining an upscaling factor L and a downscaling factor S as a function of the operand bit width N; seed means connected to said input means for determining a seed value X(0) of n bits from said operand A as follows: X(0)=(2.sup.MAX -A*2.sup.L)*2.sup.-0.5MAX-1 ; said seed means including: a complementer means for complementing said operand A; shifter means for shifting said complemented operand -A by L-0.5*MAX-1; aand adder means for adding 2 0 .5*MAX-1 to a shifted complemented operand -A; iteration means connected to said seed means for performing a plurality of iterations of the following: X(n+1)=X(0)+X(n)*X(n)*2.sup.-0.5MAX-1 ; and root means connected to said iteration means for determining a last iteration and calculating a square root of the operand A from the results of the last iteration X(last) of the iteration means as follows: R=(2.sup.0.5*MAX -X(last))*S.

Claim 6

A binary number square root calculator comprising: input means for receiving a N-bit operand A of maximum binary width of MAX; scaling means for determining an upscaling factor L and a downscaling factor S as a function of the operand bit width N; seed means connected to said input means for determining a seed value X(0) of n bits from said operand A as follows: X(0)=(2.sup.MAX -A*2.sup.L)*2.sup.-0.5MAX-1 ; said seed means including: a complementer means for complementing said operand A; shifter means for shifting said complemented operand -A by L-0.5*MAX-1; aand adder means for adding 2 0 .5*MAX-1 to a shifted complemented operand -A; iteration means connected to said seed means for performing a plurality of iterations of the following: X(n+1)=X(0)+X(n)*X(n)*2.sup.-0.5MAX-1 ; and root means connected to said iteration means for determining a last iteration and calculating a square root of the operand A from the results of the last iteration X(last) of the iteration means as follows: R=(2.sup.0.5*MAX -X(last))*S.

Claim 7

A binary number square root calculator according to claim 3, wherein said scaling means determines said upscaling factors L as the difference between MAX and the weight of the most significant bit of the operand A and determines said downscaling factor S as 2 0 .5L.

Claim 8

A binary number square root calculator according to claim 3 wherein said root means includes a means to modify said iteration means to calculate said square root R.

Claim 9

A binary number square root calculator comprising: input means for receiving an N-bit operand A of maximum binary width of MAX; scaling means for determining an upscaling factor L and a downscaling factor S as a function of the operand bit width N; seed means connected to said input means for determining a seed value X(0) of n bits from said operand A as follows: X(0)=(2.sup.MAX -A*2.sup.L)*2.sup.-0.5MAX-1 ; iteration means connected to said seed means for performing a plurality of iterations of the following: X(n+1)=X(0)+X(n)*X(n)*2.sup.-0.5MAX-1 said iteration means including: multiplexer-shifter means for providing a shifted and non-shifted output of a selected first or second input, said shifter output being shifted by -0.5*MAX-1; multiplier means for multiplying said shifted and non-shifted outputs to produce a product; adder means for adding said seed value X(0) to said product; and feedback means for feeding back an output of said adder means to said second input of said multiplexer-shifter means; said seed means being connected to said first input of said multiplexer-shifter means; and root means connected to said iteration means for determining a last iteration and calculating a square root of the operand A from the results of the last iteration X(last) of the iteration means as follows: R=(2.sup.0.5*MAX -X(last))*S.

Claim 10

A binary number square root calculator comprising: input means for receiving an N-bit operand A of maximum binary width of MAX; scaling means for determining an upscaling factor L and a downscaling factor S as a function of the operand bit width N; seed means connected to said input means for determining a seed value X(0) of n bits from said operand A as follows: X(0)=(2.sup.MAX -A*2.sup.L)*2.sup.-0.5MAX-1 ; iteration means connected to said seed means for performing a plurality of iterations of the following: X(n+1)=X(0)+X(n)*X(n)*2.sup.-0.5MAX-1 said iteration means including: multiplexer-shifter means for providing a shifted and non-shifted output of a selected first or second input, said shifter output being shifted by -0.5*MAX-1; multiplier means for multiplying said shifted and non-shifted outputs to produce a product; adder means for adding said seed value X(0) to said product; and feedback means for feeding back an output of said adder means to said second input of said multiplexer-shifter means; said seed means being connected to said first input of said multiplexer-shifter means; and root means connected to said iteration means for determining a last iteration and calculating a square root of the operand A from the results of the last iteration X(last) of the iteration means as follows: R=(2.sup.0.5*MAX -X(last))*S.

Claim 11

A binary number square root calculator according to claim 6, wherein said iteration means further includes a multiplexer means for selecting from a first input of said shifted output of said multiplexer-shifter or a second input of said downscaling factors to provide an output as an input to be multiplied in said multiplier means with said nonshifted output of said multiplexer-shifter means to calculate said square root R.

Claim 12

A binary number square root calculator according to claim 7, wherein said adder means includes an input 2 0 .5*MAX to be added to -X(last) for calculating said square root R.

Claim 13

A binary number square root calculator according to claim 6, wherein said iteration means further includes: a second shifter means for shifting outputs of said adder means by -0.5*MAX-1; second multiplier means for multiplying said output of said multiplier means and an output of said second shifter means to produce a second product; second adder means for adding said seed value X(0) to said second product; and wherein said feedback means feeds back output of said second adder means to said multiplex-shifter means.