## Division By Repeated Subtraction

### May 12, 2017

I imagine most of my readers can write the requested function. But it was enlightening to me to see the problems my student had understanding recursion, which is natural to me. Here’s the function he wanted (we assume no negative numbers):

(define (divide n d)
(if (< n d)
0
(+ (divide (- n d) d) 1)))

> (divide 29 4)
7

I also showed him this function, which keeps a counter as he originally wanted to do:

(define (divide n d)
(define (divide-helper q r)
(if (< r d)
(values q r)
(divide-helper (+ q 1) (- r d)))))
(divide-helper 0 n))

> (divide 29 4)
7


We went back and forth through a couple of rounds of emails, but what eventually made him understand how it worked was when I asked what happened when he evaluated (divide 29 0). When he finally realized that the recursion never stopped because n was never decremented, he finally got recursion.

As I said, the interaction was enlightening, and it was also rewarding to help a student get across the mental barrier that prevented him from understanding a new concept.

You can run the program at http://ideone.com/A6XJoS.

Pages: 1 2

### 11 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

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


10. sealfin said

Firstly, we need to remember that if $b$ is $0$ then $\frac{a}{b}$ is undefined, and so we need to specify that the function will return not only the quotient and the remainder of $\frac{a}{b}$ but also whether $\frac{a}{b}$ is undefined:

type
t_WholeNumber = 0 .. maxint; { As defined by the College Algebra (MA008) (<http://Udacity.com/course/ma008>) course offered by Udacity. }
t_DivModResult = record
m_quotient : integer;
m_remainder : t_WholeNumber;
m_undefined : boolean
end;
function f_DivMod( a { The dividend. }, b { The divisor. } : integer ) : t_DivModResult;

Secondly, we also need to remember that $a$ may be positive or negative (or zero) and that $b$ may be positive or negative, and so to function correctly regardless of the signs of $a$ and $b$ whilst remaining simple the function will first determine if the quotient will be negative (if either $a$ or $b$ – but not both – is negative) and will use the absolute values of $a$ and $b$ thereafter…

var
quotient_is_negative : boolean;
result : t_DivModResult;
  function f_IsNegative( p : integer ) : boolean;
begin
f_IsNegative := p < 0
end;
begin
quotient_is_negative := ( f_IsNegative( a ) and not f_IsNegative( b )) or ( not f_IsNegative( a ) and f_IsNegative( b ));
a := abs( a );
b := abs( b );

…setting the quotient to be negative (if necessary) just before it is returned:

  if quotient_is_negative then
result.m_quotient := result.m_quotient * -1;
f_DivMod := result
end;

Let’s specify that the base cases of the function – viz., the cases wherein the function will not invoke itself – are the cases where either $b$ is greater than $a$ (and so the quotient and remainder of $\frac{a}{b}$ are $0$ and $a$, respectively) or where $b$ is $0$ (and so $\frac{a}{b}$ is undefined):

  if b = 0 then
result.m_undefined := true
else
if b > a then
begin
result.m_undefined := false;
result.m_quotient := 0;
result.m_remainder := a
end

The remaining non-base case of the function – viz., the case wherein the function will invoke itself – is the case where $a$ is greater than- or equal to- $b$; we know that:

in that case the quotient is at least $1$;

in that case the function will invoke itself and will pass to itself as an argument a dividend of not $a$ but of $a-b$;

and that the function invoked in 2. will return a data structure containing the quotient and remainder of $\frac{a-b}{b}$ and whether $\frac{a-b}{b}$ is undefined.

And so, given 1. and 3., the function will increment the quotient in the data structure returned to it after 2.:

    else { a >= b }
begin
result := f_DivMod( a - b, b );
result.m_quotient := result.m_quotient + 1
end;

And the following is the complete function:

type
t_WholeNumber = 0 .. maxint; { As defined by the College Algebra (MA008) (<http://Udacity.com/course/ma008>) course offered by Udacity. }
t_DivModResult = record
m_quotient : integer;
m_remainder : t_WholeNumber;
m_undefined : boolean
end;

function f_DivMod( a { The dividend. }, b { The divisor. } : integer ) : t_DivModResult;
var
quotient_is_negative : boolean;
result : t_DivModResult;

function f_IsNegative( p : integer ) : boolean;
begin
f_IsNegative := p < 0
end;

begin
quotient_is_negative := ( f_IsNegative( a ) and not f_IsNegative( b )) or ( not f_IsNegative( a ) and f_IsNegative( b ));
a := abs( a );
b := abs( b );
if b = 0 then
result.m_undefined := true
else
if b > a then
begin
result.m_undefined := false;
result.m_quotient := 0;
result.m_remainder := a
end
else { a >= b }
begin
result := f_DivMod( a - b, b );
result.m_quotient := result.m_quotient + 1
end;
if quotient_is_negative then
result.m_quotient := result.m_quotient * -1;
f_DivMod := result
end;

(I hope that the above is comprehensible; although I’m interested in teaching – and more specifically in improving the teaching and assessment of GCSEs and AS & A levels in the STEM subjects and in making the teaching and assessment of those qualifications available to more students (more specifically to students who are studying at secondary schools or sixth form colleges which don’t offer those qualifications or who are, like myself, not in education) – I’m not, and have never been, a teacher or anything approaching that :/ )

11. Daniel said

Here’s a solution in x86 assembly that takes unsigned integers.

The handling of division-by-zero is non-portable, as it uses Linux system calls. For handling divide-by-zero, I wanted to trigger the same behavior as calling the div instruction with a zero divisor (without calling the div instruction directly). I tried to do this using interrupts, but was unsuccessful (I have limited experience using assembly code). I asked about this on Stack overflow. Any help would be appreciated.
https://stackoverflow.com/questions/46756369/how-can-i-use-interrupts-to-trigger-a-divide-by-zero-error-exception-in-x86-asse

/* divide.s */

.section .text

# unsigned int divide(unsigned int dividend,
#                     unsigned int divisor)
.globl divide
divide:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %ecx
movl 12(%ebp), %edx
cmpl $0, %edx jne valid invalid: # If divisior is zero, raise SIGFPE. # This is what appears to happen when the # div instruction is called with a zero divisor. movl$0x14, %eax # sys_getpid
int $0x80 movl %eax, %ebx movl$0x25, %eax # sys_kill
movl $8, %ecx # arithmetic exception int$0x80
movl $1, %eax movl$0, %ebx
int $0x80 movl$0, %eax
jmp return
valid:
cmpl %edx, %ecx
jae recurse
base:
movl $0, %eax jmp return recurse: subl %edx, %ecx pushl %edx pushl %ecx call divide addl$8, %esp
addl $1, %eax return: movl %ebp, %esp popl %ebp ret  Here’s a C program that calls the function. /* main.c */ #include <stdio.h> unsigned int divide(unsigned int, unsigned int); int main(int argc, char* argv[]) { printf("%d / %d = %d\n", 10, 3, divide(10, 3)); printf("%d / %d = %d\n", 3, 10, divide(3, 10)); }  Example Usage: $ as --32 -o divide.o divide.s
$gcc -m32 -o main main.c divide.o$ ./main


Output:

10 / 3 = 3
3 / 10 = 0
`