Multiply without + or *

Question

I'm working my way through How to Design Programs on my own. I haven't quite grasped complex linear recursion, so I need a little help.

The problem: Define multiply, which consumes two natural numbers, n and x, and produces n * x without using Scheme's *. Eliminate + from this definition, too.

Straightforward with the + sign:

(define (multiply n m)
  (cond
    [(zero? m) 0]
    [else (+ n (multiply n (sub1 m)))]))

(= (multiply 3 3) 9)

I know to use add1, but I can't it the recursion right.

Thanks.

Answer 1

Split the problem in two functions. First, you need a function (add m n) which adds m to n. What is the base case? when n is zero, return m. What is the recursive step? add one to the result of calling add again, but decrementing n. You guessed it, add1 and sub1 will be useful.

The other function, (mul m n) is similar. What is the base case? if either m or n are zero, return 0. What is the recursive step? add (using the previously defined function) m to the result of calling mul again, but decrementing n. And that's it!

Answer 2

Since this is almost certainly a homework-type question, hints only.

How do you add 7 and 2? While most people just come up with 9, is there a more basic way?

How about you increment the first number and decrement the second number until one of them reaches zero?

Then the other one is the answer. Let's try the sample:

7 2
8 1
9 0 <- bingo

This will work fine for natural numbers though you need to be careful if you ever want to apply it to negatives. You can get into the situation (such as with 10 and -2) where both numbers are moving away from zero. Of course, you could check for that before hand and swap the operations.

So now you know can write + in terms of an increment and decrement instruction. It's not fantastic for recursion but, since your multiply-by-recursive-add already suffers the same problem, it's probably acceptable.

Now you just have to find out how to increment and decrement in LISP without using +. I wonder whether there might be some specific instructions for this :-)