Browse Prior Art Database

A FAST DIVISION TECHNIQUE FOR CONSTANT DIVISORS

IP.com Disclosure Number: IPCOM000128597D
Original Publication Date: 1961-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 6 page(s) / 20K

Publishing Venue

Software Patent Institute

Related People

Ehud Artzy: AUTHOR [+5]

Abstract

A fast algorithm for division by constant divisors is presented. The method has proved very useful implemented as microcode on a binary ma chine, and can be adapted directly into hardware. The mathematical foundations of the algorithm are presented as well as some performance measures.

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

Page 1 of 6

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A FAST DIVISION TECHNIQUE FOR CONSTANT DIVISORS

Ehud Artzy James A. Hinds Harry J. Saal

Abstract

A fast algorithm for division by constant divisors is presented. The method has proved very useful implemented as microcode on a binary ma chine, and can be adapted directly into hardware. The mathematical foundations of the algorithm are presented as well as some performance measures.

Keywords and Phrases:

constant divisors, division algorithms, bit addressabl memory, microprogram

CR categories: 4.13 4.49 6.32

1. Introduction

We are concerned with the generation of fast algorithms for division by specified integers'. The question arose from system design considerations for addressing a bit-addressable memory on the Burroughs B1700. The first part of this note provides the practical motivation for the use of these algorithms. We next present the mathematical foundation and then the algorithm itself. .0

2. Motivation

The Burroughs B1700 imposes no hardware constraints (or advantages) on the choice of container size (byte, word, etc.) from one to twenty-four bits in.width. (See [1) for some consequences in memory utilization.) A natural convenience of integral powers of two is the simplicity of using shifts to convert from one set of units to another. The interpreters we have written for the B1700 use a variety of other widths (e.g. 18, 34, etc.). and we must multiply or divide by small integers such as these.

Multiplication by a particular integer using shifts, adds and subtracts is fairly straightforward. For example, multiplication by 17 is done by a four bit shift and add; multiplication by 15 is done by a four bit shift followed by a subtract. These algorithms are presumably optimal for the numbers in question if we restrict ourselves to shifts, adds and subtracts.

We have frequently found it to be appropriate on the B1700 to use bit addresses rather than unit addresses. We give up maximal addressing capability in a fixed width field, but this has not been a restriction on our designs. There are several places where a unit address is needed, and

State University of New York at Buffalo Page 1 Dec 31, 1961

Page 2 of 6

A FAST DIVISION TECHNIQUE FOR CONSTANT DIVISORS

this requires a fast division method. we now present our technique for rapidly dividing by a given constant. .This method easily detects any non-zero remainder, but not its value. In our applications, since we use exact multiples of the unit width, any non-zero remainder would be an error analogous to the System 360 specification a exception (See [21). .0

3. Mathematical Background

Throughout this paper N will denote the set of natural numbers and N + denotes the set N - {01. If x is a positive rational number, then Lxj denotes the greatest natural number smaller.than or equal to x and rxj denotes the smallest natural number greater than or equal to x. If a, b, m are in N then a(mod m) denotes the smallest inte...