Browse Prior Art Database

Algorithm for Division by 10

IP.com Disclosure Number: IPCOM000086379D
Original Publication Date: 1976-Sep-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Schulz, RA: AUTHOR

Abstract

Of the basic arithmetic operations performed by a computer, the division operation uses the largest number of machine steps and time and should be avoided where possible. Where the divisor is variable, the normal sequence of operations must be performed but if the divisor is 10, performance of a simple algorithm will provide the required answer.

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

Page 1 of 1

Algorithm for Division by 10

Of the basic arithmetic operations performed by a computer, the division operation uses the largest number of machine steps and time and should be avoided where possible. Where the divisor is variable, the normal sequence of operations must be performed but if the divisor is 10, performance of a simple algorithm will provide the required answer.

The key to this simplified algorithm is to recognize that the binary number representing the decimal fraction 1/10 is a repeating fraction; that is: (1/10)(10) =
(.0001 1001 1001 1001 1001 ...)(2) = 2/-1/ (.0011 0011 0011 ...)(2). where the repeating term is 0011. The fraction may be further factored as: (1/10)(10) = 2/- 5/(0011)(2) (1.0001 0001 0001 ...)(2).

This factoring allows a division by decimal 10 to be accomplished by a few shifting and adding steps. The first step of the algorithm is to generate a factor U which is 3 times the dividend by three additions of the dividend. The second step is to perform a summation of the terms: U+2/-4/ U+2/-8/ U+2/-12/ U ... to the needed accuracy. The third step is to shift the summation five binary positions to the right. The part of the operand remaining in the register is the desired quotient.

For those machines which do not allow register overflows and in which the divisor may be greater than .01 ..., (.25)(10), avoidance of an overflow during performance of the generation of the factor U can be accomplished by first shifting the dividend two plac...