Multiplication Algorithm - Quarter Square Multiplication

Quarter Square Multiplication

Two quantities can be multiplied using quarter squares by employing the following identity some attribute to Babylonian mathematics (2000–1600 BC)

\left\lfloor \frac{\left(x+y\right)^2}{4} \right\rfloor - \left\lfloor \frac{\left(x-y\right)^2}{4} \right\rfloor = \frac{1}{4}\left(\left(x^2+2xy+y^2\right) - \left(x^2-2xy+y^2\right)\right) = \frac{1}{4}\left(4xy\right) = xy.

If x+y is odd then x-y will also be odd, this means any fraction will cancel out so no accuracy is lost by discarding the remainders. Below is a lookup table of quarter squares with the remainder discarded for the digits 0 through 18, this allows for the multiplication of numbers up to 9×9.

n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
⌊n2/4⌋ 0 0 1 2 4 6 9 12 16 20 25 30 36 42 49 56 64 72 81

If, for example, you wanted to multiply 9 by 3, you observe that the sum and difference are 12 and 6 respectively. Looking both those values up on the table yields 36 and 9, the difference of which is 27, which is the product of 9 and 3.

Antoine Voisin published a table of quarter squares from 1 to 1000 in 1817 as an aid in multiplication. A larger table of quarter squares from 1 to 100000 was published by Samuel Laundy in 1856, and a table from 1 to 200000 by Joseph Blater in 1888.

Quarter square multipliers were used in analog computers to form an analog signal that was the product of two analog input signals. In this application, the sum and difference of two input voltages are formed using operational amplifiers. The square of each of these is approximated using piecewise linear circuits. Finally the difference of the two squares is formed and scaled by a factor of one fourth using yet another operational amplifier.

In 1980, Everett L. Johnson proposed using the quarter square method in a digital multiplier. To form the product of two 8-bit integers, for example, the digital device forms the sum and difference, looks both quantities up in a table of squares, takes the difference of the results, and divides by four by shifting two bits to the right. For 8-bit integers the table of quarter squares will have 29 entries of 16 bits each.

The Quarter square multiplier technique has also benefitted 8 bit systems that do not have any support for a hardware multiplier. Steven Judd implemented this for the 6502.

Read more about this topic:  Multiplication Algorithm

Famous quotes containing the words quarter and/or square:

    “Like the water, the Walden ice, seen near at hand, has a green tint, but at a distance is beautifully blue, and you can easily tell it from the white ice of the river, or the merely greenish ice of some ponds, a quarter of a mile off.”
    —Henry David Thoreau (1817–1862)

    “The square dance fiddler’s first concern is to carry a tune, but he must carry it loud enough to be heard over the noise of stamping feet, the cries of the “caller,” and the shouts of the dancers. When he fiddles, he “fiddles all over”; feet, hands, knees, head, and eyes are all busy.”
    —State of Oklahoma, U.S. public relief program (1935-1943)