Oct 26
Russian peasants
The Russian Peasant’s algorithm is a very simple way of multiplying 2 non-negative integers. The variant of the algorithm I am trying to implement is precisely described at the top of a Math Forum article.
In summary, repeatedly halve one of the factors (call it y), ignoring remainders, until it becomes zero; each time y is halved, double the other factor (x); the product is just the sum all x’s that occur when y is odd.
Here’s the offending function. It bombs out with a type error in all non-trivial cases:
(DEFUN PRODUCT (X Y)
(DO ((X X (+ X X))
(Y Y (FLOOR Y 2))
(XY 0 (+ XY (IF (ODDP Y) X))))
((ZEROP Y) XY)))
Filed under //
control flow
numbers
