Browse Prior Art Database

Extended Precision Divide Algorithm

IP.com Disclosure Number: IPCOM000038530D
Original Publication Date: 1987-Jan-01
Included in the Prior Art Database: 2005-Jan-31
Document File: 3 page(s) / 68K

IBM

Related People

Maple, WR: AUTHOR

Abstract

This invention relates to a method for obtaining extended precision arithmetic quotients in a processor where the significant digit representation of the dividend and divisor exceed the machine's divide capacity. The method steps include (a) estimating a quotient utilizing a predetermined number of higher-order digits of the dividend and divisor; (b) multiplying the entire divisor by the estimate and subtracting the result from the dividend; and (c) repeating steps (a) and (b) using the remainder as the new dividend and adding the result to the previous quotient estimate, step (c) being repeated until the required precision is obtained. The problem solved by this algorithm is that of performing extended precision division on a computer having limited division capabilities.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

Extended Precision Divide Algorithm

This invention relates to a method for obtaining extended precision arithmetic quotients in a processor where the significant digit representation of the dividend and divisor exceed the machine's divide capacity. The method steps include (a) estimating a quotient utilizing a predetermined number of higher-order digits of the dividend and divisor; (b) multiplying the entire divisor by the estimate and subtracting the result from the dividend; and (c) repeating steps (a) and (b) using the remainder as the new dividend and adding the result to the previous quotient estimate, step (c) being repeated until the required precision is obtained. The problem solved by this algorithm is that of performing extended precision division on a computer having limited division capabilities. The specific application of the algorithm is to produce a quotient having up to 31 digits of precision on a computer using the architecture of the IBM System/370. Since the System/370 architecture restricts decimal division precision to 15 digits, a software subroutine must be employed. The standard approach to the problem of extended precision arithmetic involves breaking up the long numbers into two or more smaller numbers, each one of which can be processed by the computer. This works for addition, subtraction, and multiplication because of the distributive quality of the operations involved. However, if the problem is one of division, then Dividend = DD/DR must become (DDL + DDR) / (DRL + DRR)

Divisor which is not distributive. Traditional subroutines used the approach of recursive subtractions (extended precision subtractions) of the divisor from the dividend until the subtrahend would become less than the divisor. The number of subtractions is then the first digit of the quotient. The divisor is then shifted (divided by 10) and the process is repeated using the last subtrahend as the new dividend. Since, in this case, the precision of the quotient must be as great as 31 digits, then the average number of subtractions can be .CE (average digit: 5) * (digits of precision:
31) = 155. The approach described herein uses two unique properties of the problem: 1. The computer being used has division capabilities that the traditional divide subroutine did not use.

This was usually because the ordinary application of a divide subroutine was to provide a divide function when the host computer did not have such capabilities. 2. The division can be performed in a series of iterative steps. Each step can contribute an approximation of the quotient - each approximation can extend the precision of the result. The host computer's divide capabilities permit rapid selection of a high-quality approximation. The division operation can then be restated in terms of an approximated quotient (Q1) and a residual division operation that consists of the remaind...