Binary Unsigned Integer Multiplication

written by Teresa Carrigan



Top

WHAT IS IT?

This model demonstrates binary unsigned integer multiplication.

Top

HOW IT WORKS

First the model generates two random unsigned binary numbers. The multiplier will have two to four bits, and the multiplicand will have two to eight bits.

The multiplicand is padded with leading zeroes (one zero for each bit of the multiplier), and a partial product register is initialized to all zeroes (the same size as the padded multiplicand).

Each digit of the multiplier is processed, starting with the right-most bit. If the digit is 0, then the multiplicand is shifted one place to the left, dropping a leading zero and padding with a trailing zero. If the digit of the multiplier is 1, then the multiplicand is added to the partial product register before being shifted to the left. When all the bits in the multiplier are processed, the partial product register will contain the answer to the initial multiplication problem.

Top

HOW TO USE IT

The setup button generates two random unsigned binary numbers.

The slow-motion slider is an easy way to adjust the speed of the display. Set it to zero if you want to show the final result as quickly as possible. 0.4 is a good setting for most purposes.

The step button demonstrates the next step, and then stops so you can take notes. This is useful when you are first learning the method.

The go button does each remaining step, at a speed determined by the slow-motion slider. This is useful when you do not need to take notes between each step. If you want to pause the demonstration, click the go button a second time and it will stop after finishing the current step.

The quiz button generates a random multiplication problem and then asks you for the product.

The show-again button starts the same multiplication problem from the beginning. This is very useful when your hand-calculations do not agree with the model's calculations.

Top

THINGS TO NOTICE

This process never does any actual multiplication! It's all just additions and shifts.

When the multiplier is k bits long, the product will be at most k bits longer than the unpadded multiplicand.

After each time the multiplicand is shifted, there is one additional bit in the partial product register that is never changed (because we just add zero to it). A faster approach used by many computers is to shift the partial products register right instead of the multiplicand left, with the bits shifted out of the register being stored separately instead of dropped.

Top

THINGS TO TRY

Set slow-motion to 0.4, click setup, and then click go.

Click setup. Attempt one step at a time on paper, and then click the step button to check that you did that step correctly.

Top

EXTENDING THE MODEL

Allow the user to input the multiplier and multiplicand.

Modify the model to allow larger multipliers.

Top

NETLOGO FEATURES

Extensive use is made of "other-BREED-here", "min-one-of" and "max-one-of".

Top

RELATED MODELS

Top

CREDITS AND REFERENCES

This model was written by Teresa W. Carrigan, 2004.

Permission to use, modify or redistribute this model is hereby granted, provided that both of the following requirements are followed:

  1. this copyright notice is included.
  2. this model will not be redistributed for profit without permission from Teresa Carrigan.
Contact Teresa Carrigan for appropriate licenses for redistribution for profit.

To refer to this model in academic publications, please use: Carrigan, T. (2004). Binary Unsigned Integer Multiplication model. Blackburn College, Carlinville, IL.

In other publications, please use: Copyright 2004 by Teresa W. Carrigan. All rights reserved.

Top

FOR MORE INFORMATION

For more information on binary unsigned integer multiplication, see:
  1. Null, L. and Lobur, J. Essentials of Computer Organization and Architecture, First Edition, Jones and Bartlett, pages 54-55.


Home

Applets on this website were written by Teresa Carrigan in 2004, for use in computer science courses at Blackburn College, with the exception of the Fireworks applet. The applets made with NetLogo require Java 1.4.1 or higher to run. The applets made with NetBeans require Java 1.4.2 or higher to run. Applets might not run on Windows 95 or Mac OS 8 or 9. You may obtain the latest Java plugin from Sun's Java site.