Division By Repeated Subtraction

May 12, 2017

I traded several emails this week with a programming student who was having trouble with this assignment:

Write a function that divides two numbers and returns their quotient. Use recursive subtraction to find the quotient.

The student went on to explain that he thought he needed to use a counter variable that he incremented each time the function recurred, but he didn’t know how to do that because the function could only take two arguments; it had to be of the form (define (divide a b) ...).

Your task is to write the function, and explain to the student how it works. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

8 Responses to “Division By Repeated Subtraction”

  1. Jussi Piitulainen said

    Nice story, especially how division by zero helped :)

    Division itself is a bit of a distraction when it’s not specified that the numbers are non-negative integers, so I spent some time worrying about that, but what bothered me most was not being able to use three arguments when implementing a function that takes two. One must get over that. So I wrote the following. I make no attempt to explain recursion.

    ;; There are many ways to define division when there is a remainder.
    ;; While truncation towards zero is not necessarily the best, it may
    ;; be the one that people are most familiar with. Also, let's just
    ;; implement one kind and worry about its analysis later. (But this
    ;; one does turn out to truncate towards zero, so, whatever.)
    
    (define (divide a b)
      ;; Let an auxiliary procedure, aux, deal with two positive numbers
      ;; only (not zero, not negative, but "strictly" greater than zero).
      ;; It's wishful thinking at this point, but there will be such an
      ;; auxiliary. See below.
      (cond
       ((zero? b) (raise "result is not a finite number"))
       ((zero? a) a)
       ((and (positive? a) (positive? b)) (aux a b 0))
       ((and (negative? a) (positive? b)) (- (divide (- a) b)))
       ((and (positive? a) (negative? b)) (- (divide a (- b))))
       ((and (negative? a) (negative? b)) (divide (- a) (- b)))
       (else (raise "arguments are a new kind of number"))))
    
    (define (aux a b q)
      ;; You need a three-argument procedure to implement a two-argument
      ;; procedure? You define the auxiliary that you need. (It can be
      ;; internal to the main procedure. This one maybe should be.)
      ;;
      ;; Got that? You need a function that you don't have, you get to
      ;; define that function. Then you have that function. This may be
      ;; the single most important idea in programming.
      ;;
      ;; (This auxiliary has a lousy name. That's a relatively minor
      ;; issue. Naming things well is actually not so easy.)
      (if (< a b) q (aux (- a b) b (+ q 1))))
    
    (let ((test (lambda (a b)
                  ;; The above division truncates towards zero, so test it
                  ;; against Scheme's standard integer division, which
                  ;; also truncates towards zero. It's usually a good idea
                  ;; to have a simple test set available while developing
                  ;; software - it's not a proof of correctness, but it
                  ;; can easily be a proof that something went funny.
                  (display `((divide ,a ,b) => ,(divide a b) = ,(quotient a b)))
                  (newline))))
      (test 5 2)
      (test 4 2)
      (test 3 2)
      (test 3 3)
      (test 3 4)
      (test -3 2)
      (test 3 -2)
      (test -3 -2)
      (test 0 3))
    
    ;; TL;DR; Define the auxiliary procedure that you need to use.
    
  2. programmingpraxis said

    @Jussi: Division by zero was the clincher. When the student realized that the computation failed because recursion never reached the base case, he finally understood the true meaning of the base case, and how it makes everything work.

  3. Jussi Piitulainen said

    @Praxis: Yes, I understood that. Note that I followed your rules and wrote my program and its comments before reading your solution.

    Negative numbers might have a similar effect, possibly even more so: there would be cases where the computation “progresses” but in the wrong direction, away from the base case.

  4. mcmillhj said
    (* assuming positive integers
       repeatedly subtracting b from a will result in 0
       1. 20 / 4 = 5
       2. 20 - 4 - 4 - 4 - 4 - 4 = 0
    
       Since we know the result of performing the repeated subtraction in (2) is 0, any computation that we make alongside the subtraction (counting)
       will be the result of the function
    *)
    fun divide a b = if a < b then 0
                              else 1 + (divide (a - b) b);
    
    (*
    divide 10 2
    1 + divide 8 2
    1 + 1 + divide 6 2
    1 + 1 + 1 + divide 4 2
    1 + 1 + 1 + 1 + divide 2 2
    1 + 1 + 1 + 1 + 1 + divide 0 2
    1 + 1 + 1 + 1 + 1 + 0
    ------------------------------
    5
    *)
    
  5. john said

    C11 solution:


    #include <stdio.h>
    #include <stdlib.h>

    int
    divide (int a, int b);

    int
    main (int argc, char **argv)
    {
      const int a = 15;
      const int b = 4;
      printf("%d / %d = %d\n", a, b, divide(a, b));
      exit(0);
    }

    int
    divide (int a, int b)
    {
      if (a < b)
        return 0;
      else
        return 1 + divide(a - b, b);
    }

    We build divide by asking what the base case is: in our case, when a < b. If this is so, then division will yield 0. If this is not the case, then we recursively call the method by noticing that a - b has one less b‘s worth of magnitude than a, meaning that divide(a, b) - divide(a - b, b) = 1. We restructure the formula to get the recursive invocation divide(a - b, b) + 1.

  6. bavier said

    Gforth:
    [sourcecode]
    : / over over < IF 0 ELSE swap over – swap recurse 1 + THEN ;
    [/sourecode]

  7. buoyantair said

    Which language is that? It seems very foreign to me.

  8. Globules said

    Here is a Haskell version. The Natural number type represents unbounded, non-negative integers.

    import Numeric.Natural
    
    -- Let's *derive* a solution to our problem!  If a and b are natural numbers,
    -- then define "n = a divide b" to be the largest natural number, n, such that
    -- n*b ≤ a.  (For now, let's assume b ≠ 0.  We'll deal with 0 later.)  If a < b
    -- then n must be 0 for the inequality to hold.  Otherwise, a ≥ b and the
    -- statement n*b ≤ a is equivalent to saying (n-1)*b + b ≤ a, or (n-1)*b ≤ a-b.
    -- 
    -- We can rewrite this last inequality as m*b ≤ c, where m = n-1 and c = a-b.
    -- But, aside from using different variable names, this is saying "m = c divide
    -- b", which is just a restatement of our original problem! (But, with c being
    -- smaller than a.)
    --
    -- Since m = n - 1, then n = 1 + m
    --                         = 1 + c divide b
    --                         = 1 + (a-b) divide b
    -- 
    -- Translating our two cases to code gives us:
    
    divide :: Natural -> Natural -> Natural
    a `divide` b | a < b     = 0
                 | otherwise = 1 + (a-b) `divide` b
    
    -- Also, still assuming b ≠ 0, we know that this function terminates because if
    -- a < b it gives 0 immediately, otherwise it calls itself recursively with a
    -- strictly smaller first argument.  Since the argument is strictly decreasing
    -- it must become less than b after a finite number of calls, at which point the
    -- first branch will apply.
    -- 
    -- Okay, but what about 0?  Since we said that n is the *largest* number such
    -- that n*b ≤ a, then b = 0 means that we can satisfy the inequality while
    -- increasing n without bound.  And, in fact, divide will try to do exactly
    -- that!  So, to ensure that we always get a result we'll say that "a divide 0"
    -- is undefined for any a.  We can represent this in code as follows:
    
    divideZ :: Natural -> Natural -> Maybe Natural
    _ `divideZ` 0 = Nothing
    a `divideZ` b = Just (a `divide` b)
    

    Sample output from the REPL:

    > 9 `divideZ` 2
    Just 4
    > 3 `divideZ` 5
    Just 0
    > 0 `divideZ` 21
    Just 0
    > 6 `divideZ` 0
    Nothing
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: