Browse Prior Art Database

Fast Algorithm for Division

IP.com Disclosure Number: IPCOM000082548D
Original Publication Date: 1974-Dec-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Heising, W: AUTHOR [+3]

Abstract

On a machine with addition and subtraction instructions, an overflow indicator and a branch on overflow instruction, but without multiplication or division capabilities, a fast algorithm for division is given wherein a small amount of additional hardware can be used to implement the algorithm.

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

Page 1 of 2

Fast Algorithm for Division

On a machine with addition and subtraction instructions, an overflow indicator and a branch on overflow instruction, but without multiplication or division capabilities, a fast algorithm for division is given wherein a small amount of additional hardware can be used to implement the algorithm.

Let the machine word be of length n and let the base be 2. A number of length m is a group of m consecutive words. The number of length m whose lowest (rightmost) word is stored at address alpha will be denoted by (m,alpha). It is assumed that the machine has, either in software or in hardware, an instruction Add(i,alpha,beta) which adds the number x = (i,alpha) to y = (i,beta). Also, an instruction Sub(i,alpha,beta) which adds the "two's-complement" of x to
y. This, Sub(i,alpha,beta) yields y - x and overflow indicator on if x = y, and 2/ni/ - (x - y) and overflow indicator off, if y < x.

Letting p = (m,beta), q = (m,alpha), m words of the quotient p/q are formed.

(1) Using additions (doubling) form a table of the products 2q,4q,...2/n/q(=q). Let 2/l/q be stored in (m+1,alpha(1)). Form an m+1 word number (m+1,gamma) where the top word consists of 0's and the lower m words are 1's (i.e., (m,gamma) = 2/nm/ -1). The quotient r=p/q will be formed in (m,gamma+1).

(2) Let p = (m,beta) and let the m words (m,beta-m) be 0's. Start with Sub(m+1,alpha(n),Beta-1. If overflow trigger is on then proceed with Sub(m+1,alpha(n-1),Beta-1), otherwise, Add(m+1,alpha(n-2)Beta-1). Proceed in this way down to subtracting or adding 2 . q to (m+1,beta-1). Then return to 2/n/. q sub...