Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Two-bit Square Root Algorithm

IP.com Disclosure Number: IPCOM000100126D
Original Publication Date: 1990-Mar-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 5 page(s) / 128K

Publishing Venue

IBM

Related People

Karim, FO: AUTHOR

Abstract

A technique is described whereby the speed of performing binary square root computation is doubled by utilizing the concept of a two-bit extraction of the square root per iteration. In prior art, a one-bit extraction algorithm was commonly used in computer implementation of the square root computation. If the square root of an operand was 4n bits, using one-bit algorithms would require 4n iterations to extract the square root, whereas using two-bit algorithms, as described herein, will require only 2n iterations, thereby doubling the speed of performing the square root function.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Two-bit Square Root Algorithm

       A technique is described whereby the speed of performing
binary square root computation is doubled by utilizing the concept of
a two-bit extraction of the square root per iteration.  In prior art,
a one-bit extraction algorithm was commonly used in computer
implementation of the square root computation.  If the square root of
an operand was 4n bits, using one-bit algorithms would require 4n
iterations to extract the square root, whereas using two-bit
algorithms, as described herein, will require only 2n iterations,
thereby doubling the speed of performing the square root function.

      Extracting the square root binary number (A) which is 4n bits
and the square root of the number (Q) which is 2n bits, the bits of
binary number (A) are grouped into bits, such that:
              A = J1 J2 J3  .... Jn-1 Jn

      To extract Q, the square root of a number, requires n
iterations; at iteration #1, register (R) and register (Q) are first
cleared enabling the first group (J) to be added to the register: R1
= R + J1 (1)

      To find the square root of R1 = r1 which is r1 = 2
bits square root.  Subject R1 - r12 = R2 .  R1 is then added to
the Q register so that: Q = r1

      At the next iteration, R2 which is the remainder from previous
iterations multiplied by sixteen, J2 will be added to it.  Then r2
will be extracted and r2 is placed into the Q register by shifting Q
two bits left and adding r2 to it: Q2 = 4 * Q1 + r2
Therefore: Q2 = (r1 r2) Mathematically, this is expressed as follows:

      A = Q2 (2) where A is a number required from which to extract
the square root and Q is the square root: Q = r1 r2 r3  ....
rn ri is two bits square root at the ith iteration.

      Assuming the end of iteration number (n-1)9 and Qn-1 the next
iteration is iteration (n), the last two bits of square root rn to
be: Q = 4 * Qn-1 + rn (3) Substituting equation (3) in equation (2):
              A = (4 * Qn-1 + rn)2
       A = 16 * Q2n-1 + 8 * rn * Qn-1 + rn2 (4)

      At iteration (n-1), (4 * Qn-1) was subtracted from Rn-1
eliminating the need to subtract all of equation (4) from (Rn) as
follows: 16 * Rn - (8 * rn * Qn-1 + rn2) = Rn-1 (5)

      In the implementation of equation (5), the remainder could be a
negative number.  Therefore, the factor (rn - 1) is added to Q: Qn =
4 * Qn-1 + rn-1 (6)

      If the root is large, the amount subtracted from Rn would be
large.  Therefore, it is necessary to restore this amount into the
remainder at the next iteration.  To determine this amount, Rn+1 is
determined:

      16 * Rn - 8 * rn-1 * Qn-1 - (r...