Browse Prior Art Database

Decimal Multiplier for Small Systems

IP.com Disclosure Number: IPCOM000079581D
Original Publication Date: 1973-Jul-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 3 page(s) / 34K

Publishing Venue

IBM

Related People

Schmookier, MS: AUTHOR

Abstract

Described is an algorithm for decimal multiplication, which requires no special data paths other than those needed for decimal addition and subtraction. The basic concept is that the product is developed from two passes of the multiplier. After the first pass, the partial product is doubled so that each addition or subtraction of the multiplicand during the first pass results in an effective addition or subtraction of twice the multiplicand. Similar improvement is obtained if the partial product is quadrupled, corresponding to addition or subtraction of four times the multiplicand.

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

Decimal Multiplier for Small Systems

Described is an algorithm for decimal multiplication, which requires no special data paths other than those needed for decimal addition and subtraction. The basic concept is that the product is developed from two passes of the multiplier. After the first pass, the partial product is doubled so that each addition or subtraction of the multiplicand during the first pass results in an effective addition or subtraction of twice the multiplicand. Similar improvement is obtained if the partial product is quadrupled, corresponding to addition or subtraction of four times the multiplicand.

Well-known methods for speeding up decimal multiplication consist of supplying various combinations of positive and negative multiples of the multiplicand. The most basic technique is that of permitting the multiplicand to be either added to or subtracted from the partial product. (This is equivalent to supplying the +1 and -1 times multiples.) Therefore, if a multiplier digit is greater than 5, the number of subtractions required is less than the number of additions required. For example, a digit of 8 would require either 8 additions or 2 subtractions. When subtractions are used, the next higher order multiplier digit must be effectively increased by 1. Thus, a multiplier of 328 is recoded as 332 (where 2 has the value -2), and a multiplier of 176 is recorded as 224.

The algorithm requires the partial product to be developed in two phases using the structure shown in the drawing. During the first phase, each multiplier digit in register 1 is examined in succession, one at a time, and depending on its value, the multiplicand in register 2 may be added to or subtracted from the partial product, or the partial product may be left unaltered prior to shifting for the next multiplier digit. The addition or subtraction takes place in an adder 3, which may be a decimal adder or binary adder with decimal correction. The partial product in register 4 is presented to adder 3 by gate 5. Gate 6 (True) or gate 7 (Complement) adds or subtracts, respectively, the multiplicand. After the first phase is completed, the partial product is doubled by adding it to itself by energizing gate 5 and a gate 8. Therefore, the only additions and subtractions taken during the first phase are those corresponding to the +2 or -2 times multiple of the multiplicand.

Prior to starting the second phase, the right and left halves of the partial product in register 4 are swapped by energizing gates 9 and 10 to provide proper alignment. Since the high-order digits of the partial product are in the right half of register 4, gate 11 is energized after each iteration of the second phase to ring- shift register 4. During the second phase, each multiplier digit is again examined, and additions and subtractions corresponding to the +1 and -1 times multiples are t...