Browse Prior Art Database

Algorithm for Multiplication

IP.com Disclosure Number: IPCOM000082547D
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 computer with just an add operation, a fast multiplication p.q of m-word numbers p (the multiplier) and q (the multiplicand) is performed. The algorithm is such that if the same multiplicand q is reused, then further speedup is possible. A very limited amount of additional hardware is necessary to provide the expanded function.

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

Page 1 of 2

Algorithm for Multiplication

On a computer with just an add operation, a fast multiplication p.q of m-word numbers p (the multiplier) and q (the multiplicand) is performed. The algorithm is such that if the same multiplicand q is reused, then further speedup is possible. A very limited amount of additional hardware is necessary to provide the expanded function.

Let the machine word be of length n digits, the base be b, and let k be a divisor of n. Numbers are referenced by giving the length, i.e., the number of words, m and the address alpha of the lowest word.

The algorithm requires, either in hardware or as software routines, the following instructions. Add (l,alpha,beta) : Add the number (l,alpha) to the number (l,beta). Shift .(l,alpha,i), 1 = i < n: Shift the number A = (1,alpha) i digits to the left. This means obtaining b/i/A. Move (l,alpha,beta): Overwrite the number (l,alpha) on (l,beta).

The execution times for Add(l,alpha,beta), Move(l,alpha,beta) and Shift (1,alpha,i) increase with l and i. Typically the time for Add and Move may be c + ld where c,d are constants, and the time for Shift(l,alpha,i) may be i(c+ld).

For each 1 = i, j = n/k, an instruction Move ij(alpha,beta) takes the i-th group of k digits of the word (1,alpha) and overwrites it on the j-th group of digits of the word (1,beta). In what follows, it shall be assumed, for the sake of simplicity that k = n/2. Then call the lower k digits of the word (1,alpha), the numeric of alpha, and the upper k digits the zone of (1,alpha).

The algorithm proceeds as follows.

(1) In a specified space, for the b/k/ multiples 0.q,1.q,...,(b/k/-1).q of the multiplicand q, the multiple l.q will be the number (m+1,alpha(l)), 0 < or = l < or = b/k/-1. This table is generated by the Add instruction. If the execution of the Add (l,alpha,beta) and Move (l,alpha,beta) instructi...