AlgoVerse

The division algorithm

Find the quotient q and remainder r with a = q·b + r and 0 ≤ r < b, by subtracting or adding b again and again.

The division theorem: for every integer a and every b > 0 there is exactly one pair q, r with

Read the full explanation ↓
Input:
a=170 · b=11PDF export

170 divided by 11: 170 = 15·11 + 5.

  1. def divide(a, b):
  2. # a = q·b + r with 0 ≤ r < b, by repeated subtraction (b > 0).
  3. q = 0
  4. r = a
  5. rows = [(q, r)]
  6. while r >= b:
  7. r = r - b
  8. q = q + 1
  9. rows.append((q, r))
  10. while r < 0:
  11. r = r + b
  12. q = q - 1
  13. rows.append((q, r))
  14. return q, r

Invariant: At every moment a = q·b + r holds; only r may still be outside the range [0, b).

Start

q—
r—

The table is still empty.

Local variables

a170
b11

Orange = changed in this step

Call stack

  1. divide()line 1
Step 1 of 67
Black = take_away, add_back · Orange = key steptake_away: 0/15 · done: 0/1
    Explanation

    The idea

    The division theorem: for every integer a and every b > 0 there is exactly one pair q, r with

    a = q·b + r   and   0 ≤ r < b

    The simplest way to find them: start with q = 0 and r = a. While r ≥ b, take one b away and add one to q; if a was negative, while r < 0, add one b and take one from q.

    A note on negative numbers

    In mathematics the remainder is never negative, so −17 mod 5 = 3. Some programming languages (such as C) give −2; Python gives 3, like mathematics.

    Cost

    This takes |a| / b steps; machines divide directly and much faster. The point here is to see what q and r mean.