Peter Sheats’ Blog

Here are the rules for the Russian peasant method:

• Write each number at the head of a column.
• Double the number in the first column, and halve the number in the second column.
  If the number in the second column is odd, divide it by two and drop the remainder.
• If the number in the second column is even, cross out that entire row.
• Keep doubling, halving, and crossing out until the number in the second column is 1.
• Add up the remaining numbers in the first column. The total is the product of your original numbers.

So my procedure will keep track of a, b, and sum. On each iteration the sum will be set to a + sum only when b is odd. When b = 1 the answer will be a + sum.

; We don't care about the remainder of 1
; so we only want to divide the next even number
(define (halve x)
  (if (even? x)
      (/ x 2)
      (halve (-  x 1))))

(define (double x) (+ x x))

(define (even? x)
  (= (remainder x 2) 0))

(define (mul-help a b sum)
  (if (= b 1)
      (+ a sum)
      (mul-help (double a)
                (halve b)
                (if (even? b)
                    sum
                    (+ a sum)))))

(define (mul a b)
  (mul-help a b 0))