Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site dciem.UUCP
Path: utzoo!dciem!ntt
From: ntt@dciem.UUCP (Mark Brader)
Newsgroups: net.math
Subject: Re: Math for Smart Alecks -- and exponentiation
Message-ID: <662@dciem.UUCP>
Date: Mon, 30-Jan-84 13:15:16 EST
Article-I.D.: dciem.662
Posted: Mon Jan 30 13:15:16 1984
Date-Received: Mon, 30-Jan-84 15:11:21 EST
References: <805@sdcrdcf.UUCP>
Organization: NTT Systems Inc., Toronto, Canada
Lines: 19

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