[TUTOR] Division, Rounding, and Modulus

[Admiral Ackguh]

The division operation in ACK rounds up if the fraction is 0.5 or more. In games, and many other applications, rounded integer division is useful. So is truncated integer division, where there is no rounding, and the fraction simply discarded. Here are the full, truncated, and rounded results of dividing by five:

Code: Select all

x      0   1   2   3   4   5   6   7   8   9  10  11  12  13
x/5    0  0.2 0.4 0.6 0.8  1  1.2 1.4 1.6 1.8  2  2.2 2.4 2.6
trunc  0   0   0   0   0   1   1   1   1   1   2   2   2   2 
round  0   0   0   1   1   1   1   1   2   2   2   2   2   3

Some more rounded division results:

Code: Select all

x      0   1   2   3   4   5   6   7   8   9  10  11  12  13  14
x/2    0   1*  1   2   2   3   3   4   4   5   5   6   6   7   7
x/3    0   0   1*  1   1   2   2   2   3   3   3   4   4   4   5
x/4    0   0   1*  1   1   1   2   2   2   2   3   3   3   3   4
x/5    0   0   0   1*  1   1   1   1   2   2   2   2   2   3   3
x/6    0   0   0   1*  1   1   1   1   1   2   2   2   2   2   2
x/10   0   0   0   0   0   1*  1   1   1   1   1   1   1   1   1

* indicates the rounding point, the first x value triggering rounding.

R (if y even) = y / 2
R (if y odd) = (y+1) / 2

It is possible to have truncated integer division with the following formula, using R the rounding point:

x div y = ((x + R) / y) - 1

The code must add, divide, and subtract in that order. R is used as an offset, to force the built-in rounding of the ACK division operator to round at multiples of y. Since R is added, the division result is one greater than what we need, hence subtraction by 1. A simpler (but useless in ACK) formula would be ((x - R) / y). For x < R, the negative x - R would overflow the variable used to store the intermediate result, and division would treat it as a huge positive value.

Code: Select all

x         0   1   2   3   4   5   6   7   8   9  10  11  12  13
x/3       0   0   1   1   1   2   2   2   3   3   3   4   4   4 
(x+2)/3   1   1   1   2   2   2   3   3   3   4   4   4   5   5 
above-1   0   0   0   1   1   1   2   2   2   3   3   3   4   4 

Code: Select all

x         0   1   2   3   4   5   6   7   8   9  10  11  12  13
x/6       0   0   0   1   1   1   1   1   1   2   2   2   2   2
(x+3)/6   1   1   1   1   1   1   2   2   2   2   2   2   3   3
above-1   0   0   0   0   0   0   1   1   1   1   1   1   2   2

Here is some sample macro code, given X and Y, using R as temporary, and Q for the result (quotient):

Code: Select all

        08: SET R = Y
        09: IF R & 1 THEN
        10: SET R = R + 1
        11: SET R = R / 2
        12: SET Q = X + R
        13: SET Q = Q / Y
        14: SET Q = Q - 1

If Y is a constant, values for it and R can be substituted:

Code: Select all

        12: SET Q = X + 3
        13: SET Q = Q / 6
        14: SET Q = Q - 1

The formula can be used with non-standard values of R, as shown below, for division by 6, to round at various points. Note that when R equals y, the result is the same as normal rounded division.

Code: Select all

x         0   1   2   3   4   5   6   7   8   9  10  11  12  13
R = 3     0   0   0   0   0   0   1   1   1   1   1   1   2   2
R = 4     0   0   0   0   0   1   1   1   1   1   1   2   2   2
R = 5     0   0   0   0   1   1   1   1   1   1   2   2   2   2
R = 6     0   0   0   1   1   1   1   1   1   2   2   2   2   2
R = 7     0   0   1   1   1   1   1   1   2   2   2   2   2   2
R = 8     0   1   1   1   1   1   1   2   2   2   2   2   2   3

MODULUS: For positive integers, the modulus is the same as the division remainder. It is basically a way to force x between 0 and y-1.

x mod y = x - (y * (x div y))
x div y = ((x + R) / y) - 1
x mod y = x - (y * (((x + R) / y) - 1))

As with truncated division, the code must perform each operation in order, starting from the innermost brackets. Add, divide, subtract, multiply, and subtract. Do not algebraically simplify the formula, as multiplication does not cancel out either truncated or rounded division!

Code: Select all

x         0   1   2   3   4   5   6   7   8   9  10  11  12  13
x div 3   0   0   0   1   1   1   2   2   2   3   3   3   4   4
3*Q       0   0   0   3   3   3   6   6   6   9   9   9  12  12
x-(3*Q)   0   1   2   0   1   2   0   1   2   0   1   2   0   1

x         0   1   2   3   4   5   6   7   8   9  10  11  12  13
x/6       0   0   0   1   1   1   1   1   1   2   2   2   2   2
(x+3)/6   1   1   1   1   1   1   2   2   2   2   2   2   3   3
x div 6   0   0   0   0   0   0   1   1   1   1   1   1   2   2
6*Q       0   0   0   0   0   0   6   6   6   6   6   6  12  12
x-(6*Q)   0   1   2   3   4   5   0   1   2   3   4   5   0   1

General macro code for modulus, where M is result:

Code: Select all

        08: SET R = Y
        09: IF R & 1 THEN
        10: SET R = R + 1
        11: SET R = R / 2
        12: SET M = X + R
        13: SET M = M / Y
        14: SET M = M - 1
        15: SET M = M * Y
        16: SET M = X - M

As above for Y of 6:

Code: Select all

        12: SET M = X + 3
        13: SET M = M / 6
        14: SET M = M - 1
        15: SET M = M * 6
        16: SET M = X - M

For both truncated quotient and modulus:

Code: Select all

        12: SET Q = X + 3
        13: SET Q = Q / 6
        14: SET Q = Q - 1
        15: SET M = Q * 6
        16: SET M = X - M