ntt@dciem.UUCP (Mark Brader) (01/30/84)
This method (how it works has been explained by a couple of submitters) is sometimes called "Russian peasant multiplication"; apparently the name was once quite accurate as this method was commonly used there. There is also a practical application in computing. If you want to compute a large power of a number, you can use this method; just substitute squaring for doubling and multiplication for addition, in the right-hand column. If you want to compute, say, A^26, you might have: 26 xxx A 13 A^2 6 xxx A^4 3 A^8 1 A^16 And you multiply (A^16)*(A^8)*(A^2), and you have A^26 in 6 multiplications. Large enough exponents to make this really useful may occur without overflow if A is close to 1 or the arithmetic is modular. Mark Brader