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:

    “I also heard the whooping of the ice in the pond, my great bed-fellow in that part of Concord, as if it were restless in its bed and would fain turn over, were troubled with flatulency and bad dreams; or I was waked by the cracking of the ground by the frost, as if some one had driven a team against my door, and in the morning would find a crack in the earth a quarter of a mile long and a third of an inch wide.”
    —Henry David Thoreau (1817–1862)

    “In old times people used to try and square the circle; now they try and devise schemes for satisfying the Irish nation.”
    —Samuel Butler (1835–1902)