22C:18, Lecture 14, Fall 1996

Multiplication

To multiply two binary numbers, we use the same algorithm that is commonly used for decimal numbers. For example:

         1010  multiplicand
        x 101  multiplier
      --------
         1010  
        0000   partial products
     + 1010
    ----------
       110010  product

Note that the partial products resulting from binary multiplication are represented by exactly the same strings of digits as the partial products that would result from the decimal multiplication of one thousand and ten by one hundred and one -- that is, the number base we used had no effect on the computation of the partial products. The number base comes into the picture only when it comes time to add the partial products to make the product.

Note also that, since the only multiplier digits are zero and one, the problem of remembering the multiplication table is eliminated. Each partial product is either zero or a verbatim copy of the multiplicand!

In looking for an algorithmic statement of this approach to binary multiplication, it was found that a group of Russian peasants used precisely this method to multiply decimal numbers, and as a result, the binary multiplication algorithm given here is commonly known as the Russian Peasant Algorithm:

	set the product to zero
	while the multiplier is nonzero
	    if the multiplier is odd
	        add the multiplicand to the product
            divide the multiplier by two
            multiply the multiplicand by two

	prod = 0;
	while (ier) {
		if (ier & 1) {
			prod += icand;
		}
		ier >>= 1;
		icand <<= 1;
	}

	; procedure to multiply two numbers
	;   link through R1
	;   assumes R2 is used for the stack pointer
	;   given: multiplier in R3    (ier)
	;          multiplicand in R4  (icand)
	;   returns: product in R5     (prod)
	
	mult:
		CLR	R5
	multlp:
		TST	R3	; exit loop if ier=zero
		BZS	mulqt
		SRU	R3,1	; ier /= 2, C = remainder
		BCR	mulno	; if C set (ier odd)
		ADD	R5,R5,R4;   add in the partial product
	mulno:
		SL	R4,1	; icand *= 2
		BR	multlp
	mulqt
		JUMPS	R1	; return

The best of these fast algorithms was developed by HP for the HP PA RISC architecture. In developing the first generation of this architecture, the HP designers concluded that a hardware multiply instruction was not justified, because most multiplies are multiplies by constants and can be replaced by add-and-shift instructions (as on the Hawk) and because the rare multiply of one variable by another could be done quickly enough in software.

The HP PA RISC multiply algorithm is based on the following notions:

1. First, do the multiply in base 16, so each step involves multiplying the multiplicand by the least significant 4 bits of the multiplier and then adding the partial product to the result.

2. To multiply the multiplicand by one hex digit of the multiplier, use an efficient case/select control structure to select one of 16 different blocks of code for multiplying by a constant. Each of these blocks will be only a few instructions long because of the use of add-and-shift instructions.

3. To avoid the cost of loop control instructions, note that the fixed word size implies that each multiply can be done in a fixed number of iterations (4 hex digits in a 16 bit multiplier, or 8 hex digits in a 32 bit multiplier). So, just write out the body of the loop 4 or 8 times in series and eliminate any need for loop counters.

Some Bad Advice on Commenting

Many beginning programmers have difficulty figuring out how much commentary to add to their programs. Here are some rules:

1. Write one comment per line
2. Use long identifiers
3. Use plenty of white space within lines
4. Double space text for readability
5. Add a block of comments before any significant block of code
6. Break up subroutines over one page ling into multiple subroutines
7. Add a block of comments before each subroutine to document its use

Some Good Advice on Commenting

In the real world, many programs are read by many people between the time they are written and the time they are discarded. One study showed that the typical program written for the Department of Defense was read by over 100 people during its lifetime. So, write comments directed to the people who will read your program. Who reads programs? Programmers! Programmers assigned to fixing bugs in the code, programmers assigned the job of enhancing the code, programmers who are assigned the job of moving the code from one runtime environment to another (from Mac to DOS to Windows to UNIX to some future system, perhaps).

So, write comments that answer the questions programmers will have about the code, and don't repeat the obvious. Assume that the programmers reading your code and comments know as much as you do about the machine! Comments that simply repeat what anyone with a minimal knowledge of the language can figure out say nothing! Assume your reader knows the language, and use your comments to say what the program text doesn't say.

In addition, comments are very appropriate where they document obscure tricks, places where you've pushed the limits of the language or dredged up obscure features that commonplace programmers are unlikely to know.

Finally, comments that give the big picture are very important. Anyone reading a block of code that says "a=b+c" can figure out that it adds b and c to give the new value of a, but the reason for this sum is certainly not apparent! Comments should give these reasons, fitting the local operations in the program into a larger picture.