Browse Prior Art Database

Approximate Scaling of Integers With a Limited Precision Alu

IP.com Disclosure Number: IPCOM000034958D
Original Publication Date: 1989-May-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Luniewski, AW: AUTHOR [+2]

Abstract

Disclosed is a method for rapidly finding an approximate value for avb/c given that the quantities a, b, and c are 32-bit binary positive integers, that the exact value of avb/c is a 32-bit positive integer, and that the processor has only a 32-bit binary arithmetic unit. A fast, approximate solution is preferred to a slow, accurate solution. The algorithm discussed in this method computes avb/c in five stages: 1. Without loss of generality, let a be the larger of the two numbers which are to be multiplied, and b the smaller. Multiply a by an appropriate power of 2 to yield a' in the range 230 < a' < 231. 2. Divide c by an appropriate power of 2 so as to discard the low-order zero bits from the binary representation of c.

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

Page 1 of 2

Approximate Scaling of Integers With a Limited Precision Alu

Disclosed is a method for rapidly finding an approximate value for avb/c given that the quantities a, b, and c are 32-bit binary positive integers, that the exact value of avb/c is a 32-bit positive integer, and that the processor has only a 32-bit binary arithmetic unit. A fast, approximate solution is preferred to a slow, accurate solution. The algorithm discussed in this method computes avb/c in five stages: 1. Without loss of generality, let a be the larger of

the two numbers which are to be multiplied, and b

the smaller. Multiply a by an appropriate power

of 2 to yield a' in the range 230 < a' < 231.

2. Divide c by an appropriate power of 2 so as to

discard the low-order zero bits from the binary

representation of c. If k > 15 bits of precision

still remain, discard an additional k - 15 bits to

obtain a new divisor c'.

3. Compute an approximation s (the scaling factor) of

a/c by computing a'/c'.

4. If the product svb will equal or exceed 231,

discard low- order bits from the binary

representations of s and b so that the product

will be less than 231. Low-order zero bits are

discarded first. If more bits must be discarded,

the larger number is divided by 2 until the

objective is reached or until the two numbers are

of the same magnitude. In the latter case, bits

are then discarded alternately from the two

numbers until the goal is reached. Then perform

the multiplication to yield the product p.

5. Multiply or divide the product p by a power of 2

so as to undo the effect of all the

multiplications and divisions by powers of 2 that

were performed in the previous steps. Step 1 makes the numerator of the division as large as possible, to ensure more bits of precision in the quotient. The first part of step 2 makes the divisor as small as possible without loss of precision, again to ensure more bits of precision in the quotient. However, if the smaller number is still very large (for example, it may have 24 bits of precision), then the quotient will have very few bits of precision (in this example, 31 - 24 = 7 bits of Continued precision). In such a case, more precision may be obtained in the quotient by discarding low-order bits from the divisor before the division is performed...