Ethiopian Multiplication [1]:
A method of multiplying positive integers using only addition, doubling,
and halving.
Method:
1. Take two numbers to be multiplied and write them down at
the top of two columns.
2. In the left-hand column repeatedly halve the last number,
discarding any remainders, and write the result below the
last in the same column, until you write a value of 1.
3. In the right-hand column repeatedly double the last
number and write the result below. stop when you add a
result in the same row as where the left hand column
shows 1.
4. Examine the table produced and discard any row where the
value in the left column is even.
5. Sum the values in the right-hand column that remain to
produce the result of multiplying the original two
numbers together
Implement Ethiopian multiplication in J, as concisely as possible (no, *
doesn't count). Here's my tee-off:
ethiop =: +/@:( (2&|@:] # (*2^i.@:#)) (1>.<.@:-:)^:a: )~
EG:
17 ethiop 34
578
17 * 34
578
-Dan
[1] http://rosettacode.org/wiki/Ethiopian_Multiplication
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
