Browse Prior Art Database

Square Root Program for Small Computers

IP.com Disclosure Number: IPCOM000045696D
Original Publication Date: 1983-Apr-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Nguyen, TD: AUTHOR

Abstract

A square-root algorithm adapted for assembly or machine language runs efficiently on small computers. The root has a digital precision to the last possible bit; for example, the result of the square root of a 32-bit number has 16 significant bits. The algorithm also executes faster than many other algorithms. The algorithm extracts the square root of a number using iterative operations. It operates optimally on integers. Excusive-OR logic is employed in the rooting. The algorithm is readily adaptable to floating-point operations.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 2

Square Root Program for Small Computers

A square-root algorithm adapted for assembly or machine language runs efficiently on small computers. The root has a digital precision to the last possible bit; for example, the result of the square root of a 32-bit number has 16 significant bits. The algorithm also executes faster than many other algorithms. The algorithm extracts the square root of a number using iterative operations. It operates optimally on integers. Excusive-OR logic is employed in the rooting. The algorithm is readily adaptable to floating-point operations.

The algorithm requires primitive operations, such as Subtraction, Shifting and Exclusive-ORing, to achieve its functions. Written in assembly language, it is suitable to be used on mini- and micro-computers where other methods might be impeded by the lack of a divide instruction or slow division time. For large computers, a micro-programmed version might be initiated by a machine instruction. Relying on bit by bit approximation, an Excusive-ORing scheme replaces a sequence of bit-manipulating steps. This improvement makes the algorithm more desirable. Although only linear, rather than quadratic, convergence is possible. Bits of the result are calculated from the most significant to the least significant, one at a time, approaching the result linearly. The number of major iterations will generally be:

Number of iterations equals (numbers of significant digits in the the operand)/2.

The algorithm has two slightly different versions; each favors a set of features that a given machine language might have. Both are outlined as follows in the PLS3 language to extract square roots of 32-bit integers: VERSION I.

This version favors machines which have Indirect-indexed addressing capability. It uses a table of constants to compute the result. root=140000000'X; pairs=16; Note: Some skipping of leading zeros could be done here which would reduce variable "pairs" by one for every pair of leading zeros; the method is machine-specific.

This vers...