Saturday, January 24, 2009
I came across a technique for multiplying big numbers recently, called prosthaphaeresis , that predates the use of logarithms. It relied on the use of pre-calculated cosine tables, and made use of the trigonometric relation:
cos(A)*cos(B) = [ cos(A+B) + cos(A-B) ]/2
All you need to to is scale the two large numbers to between 0 and 1, look up the scaled numbers in your cosine table to find the angles they represent, add and subtract the angles, find the cosines of the new angles in your table, and average them.
This speeds up multiplication by reducing a series of single-digit multiplications and additions to some table lookups, three addition/subtractions, and a division by two. Before calculators, computation was much more of a scarce resource; anything that could speed it up was useful. Before logarithms were invented, this could speed up your multiplication a lot.
For example, let's say we wanted to multiply 45678 x 23456. Convert them to (0.45678 x 10^5) x (0.23456 x 10^5). Combine the two multiplied 10^5 base 10 exponents into 10^10 and save it for later. Looking up 0.45678 and 0.23456 in the cosine table says the angles representing them are 62.820 and 76.434 degrees, respectively. Adding and subtracting these angles gives new angles of 139.254 and -13.614. The cosines of these angles are -0.75761 and 0.97190. Averaging them gives 0.10715. Multiply this by the base 10 exponent of 10^10, and you have 1071400000.
By my calculator, 45678 x 23456 = 1071423168, which to the correct number of significant figures, is 1071400000, the same answer from the cosine method. Pretty neat, for the days before calculators.
Burton MacKenZie www.burtonmackenzie.com
 Greek "prosth-" or "adding" and "-aphaeresis" or "subtracting"