Computer method and apparatus for division and square root operations using signed digit

#Generally mathematical operations in a computer such as, (i) division of a dividend by a divisor to produce a quotient and (ii) square root of a radicand to produce a root, are slow. Such division and square root operations are slow because they require iteratively generating a series of partial remainders, and quotient or root digits respectively.

#Therefore, the speed of the division or square root operation is dependent on the amount of time it takes to complete one iteration and the total number of iterations required. The total number of iterations is dependent on the number of quotient or root mantissa digits required to provide an accurate quotient or root. For example, in floating point division twenty-four mantissa digits are required for single precision and fifty-three mantissa digits are required for double-precision, therefore the time required to generate each of the required quotient digits is critical to the speed of the division operation.

#Typically, in each iteration of a square root operation, a root digit and a correction term are computed after examining a current partial remainder. The succeeding or partial remainder for the next iteration is computed by subtracting the correction term from the current partial remainder and scaling the result of the subtraction. In each iteration of a division operation, a quotient digit is computed after comparing a current partial remainder and the divisor. The partial remainder for the next iteration is computed by subtracting a multiple of the divisor from the current partial remainder and scaling the result of the subtraction.

#The foregoing and other objects, features and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the invention, as illustrated in the accompanying drawings in which like reference characters refer to the same parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention.

#FIG. 1 is a block diagram of a computer system in which the present invention may be used;

#FIG. 2 is a block diagram of the CPU module shown in FIG. 1;

#FIG. 1 is a block diagram of a typical computer system 100 in which the present invention is utilized. Included in the computer system 100 are a Central Processing Unit (“CPU”) module 108, a memory system 106 and a PCI chip set 110 connected by a processor bus 112. The PCI chip set 110 is further connected to an Input/Output (“I/O”) system 104 and a co-processor module 102 by a system bus 114.

#FIG. 2 shows the CPU module 108 shown in FIG. 1. The CPU module 108 includes a CPU 220, a backup cache 214 and a processor bus interface logic 216 connected by a private address bus 212 and a private data bus 218. The processor bus interface logic 216 connects the CPU module 108 to the processor bus 112 (FIG. 1). The CPU 220 includes a primary cache 208 and a cache control (CBOX) logic 210. The cache control logic (CBOX) 210 controls the primary cache 208 in the CPU 220 and the backup cache 214.

#CPU 220 further includes logic circuits to enable it to perform operations for the computer system 100. An Instruction Fetch and Decode Unit (IBOX) 202 performs instruction prefetch, decode, branch prediction, instruction issuance and interrupt handling operations. An Integer Execution Unit (EBOX) 204 performs mathematical operations on integer values such as, addition, shifting, byte manipulation, and multiplication. A Floating Point Execution Unit (FBOX) 200 performs mathematical operations on floating point values such as, square root, division and multiplication. A Memory Management Unit (MBOX) 206 performs memory address translation, for example, from virtual memory addresses to physical memory addresses.