Browse Prior Art Database

High Speed Division Algorithm

IP.com Disclosure Number: IPCOM000093488D
Original Publication Date: 1967-Oct-01
Included in the Prior Art Database: 2005-Mar-06
Document File: 2 page(s) / 43K

Publishing Venue

IBM

Related People

Senzig, DN: AUTHOR

Abstract

The basic restoring algorithm for division, i.e., the conventional paper and pencil method, and the known nonrestoring algorithms for division are inherently slow. This is because they require approximately either n subtraction or addition cycles or both where n is the word length in bits. These algorithms can be supplemented by one or more speedup techniques. Analysis indicates that such techniques alone cannot improve performance by more than about a factor of four. In any case, the number of iterations is directly proportional to word length, or stated alternatively, convergence is linear or first order.

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 100% of the total text.

Page 1 of 2

High Speed Division Algorithm

The basic restoring algorithm for division, i.e., the conventional paper and pencil method, and the known nonrestoring algorithms for division are inherently slow. This is because they require approximately either n subtraction or addition cycles or both where n is the word length in bits. These algorithms can be supplemented by one or more speedup techniques. Analysis indicates that such techniques alone cannot improve performance by more than about a factor of four. In any case, the number of iterations is directly proportional to word length, or stated alternatively, convergence is linear or first order.

This algorithm is a technique or algorithm for division in which convergence is third order or fourth order. Stated differently, each iteration triples or quadruples the number of correct digits in the quotient. This technique is approximately 50% or 100% faster than previous techniques. This algorithm can be extended to provide still higher order algorithms, but these are probably of lesser interest since, with this fourth order method, a thirty-two bit quotient in two iterations can be generated.

(Image Omitted)

1

Page 2 of 2

2

[This page contains 5 pictures or other non-text objects]