Browse Prior Art Database

Efficient Algorithm for Extended Precision Division

IP.com Disclosure Number: IPCOM000105776D
Original Publication Date: 1993-Sep-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 4 page(s) / 80K

Publishing Venue

IBM

Related People

Schwartz, AA: AUTHOR

Abstract

When division must be performed to a greater precision than is provided by a computer language or computer hardware, special algorithms must be employed. These can be both clumsy and slow.

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

Efficient Algorithm for Extended Precision Division

      When division must be performed to a greater precision than is
provided by a computer language or computer hardware, special
algorithms must be employed.  These can be both clumsy and slow.

      One method of extending the precision in division is to use
normal precision division to obtain a trial quotient for use as a
starting point.  As in conventional long division, this trial
quotient is then multiplied by the divisor, the product is compared
with the dividend, and the trial quotient modified.  This process is
repeated until sufficient precision is obtained.  Note that this
method requires that extended precision multiplication be available.
That method is quite good when only a few bits of extra precision are
required.  The algorithm presented here is more direct.

      This extended precision algorithm resembles conventional long
division superficially, but there are several significant
differences:

     - In conventional long division a radix of 10 is used.  For
       this algorithm, the radix chosen should be the largest
       radix which will preserve precision on the computer system
       on which it will operate and which allows convenient
       representation of numbers.  In the presentation of the
       algorithm which follows, a radix of 100 was used.  In a
       computer language implementation of the algorithm in APL,
       the author used a radix of 2**16.

     - In conventional long division one does a trial division,
       multiplication, and subtraction to determine each digit of
       the quotient.  If the result of the subtraction is greater
       than or equal to the divisor or is less than zero then a new
       estimate of the quotient digit must be made and the process
       repeated.  In the algorithm described here, there is no
       trial.  The first digit of the divisor is divided into the
       first non-zero digit of the dividend, multiplied by the
       divisor without carry between digit positions, and the
       product is subtracted from the remaining dividend without
       borrow or carry between digit positions.

      This means that digit positions can temporarily contain values
which are greater than the radix or are negative.  The resulting new
dividend is then normalized to the radix.

      More than one entry can be added in at each digit position of
the quotient.

      This algorithm is presented in the following example where we
will divide the decimal value 456789 by 123 using radix 100.  In
radix 100 the two numbers are then 45 67 89 and 1 23.  Integer
division is assumed.

                             37   13       Adjusted Quotient
                                  -1       Adjustment:  remainder...