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:

    “The most winning woman I ever knew was hanged for poisoning three little children for their insurance-money, and the most repellent man of my acquaintance is a philanthropist who has spent nearly a quarter of a million upon the London poor.”
    —Sir Arthur Conan Doyle (1859–1930)

    “O for a man who is a man, and, as my neighbor says, has a bone in his back which you cannot pass your hand through! Our statistics are at fault: the population has been returned too large. How many men are there to a square thousand miles in this country? Hardly one.”
    —Henry David Thoreau (1817–1862)