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:

    “A quarter of an hour is worth a thousand pieces of gold.”
    —Chinese proverb.

    “After the planet becomes theirs, many millions of years will have to pass before a beetle particularly loved by God, at the end of its calculations will find written on a sheet of paper in letters of fire that energy is equal to the mass multiplied by the square of the velocity of light. The new kings of the world will live tranquilly for a long time, confining themselves to devouring each other and being parasites among each other on a cottage industry scale.”
    —Primo Levi (1919–1987)