(42S) Quotient and Remainder

[Albert Chan]

I added some documentation to pseduo-code, to make algorithm more clear.
Please feel free to correct my errors ...

Quote:t := Y/X;
Q := FLOOR(t);
R := MOD(Y,X);
if t != Q then return(R,Q);

If Y/X not close to integer, floor-divide Q is correct.
R is floor-mod, always correct, just come for the ride.

Quote:t := X - R;

Y = Q*X + R = (Q+1)*X + (R-X) = (Q+1)*X + (-t)

The rest of the code is to decide remainder(Y,X) = R or -t
If remainder is (-t), we had over-estimated Q by 1

Quote:if ABS(t)<ABS(R) then Q := Q - 1;

With floor-mod, sign(X) = sign(R) = sign(t)
If Z = remainder(Y,X)/X = (-t)/X < 0, then Q over-estimated

Example, with a 2 significant digits calculator
80/7 = 11.428... ≈ 11. remainder(80,7) = +3 --> floor-divide Q = 11
81/7 = 11.571... ≈ 12. remainder(81,7) = −3 --> floor-divide Q = 12 - 1 = 11

Quote:if R != t then return (R,Q)

If |Z| < 1/2, not half-way case, we are done.

Quote:t := MOD(Y,X*10) / X;
return Q - MOD(FLOOR(t),2)

Q is half-way case, rounded-to-even. OP 2 half-way case example:

>(8e11+2) / 4
 200000000000
>(8e11+6) / 4
 200000000002

Z = ±1/2. We zoom-in to decide Z sign.

We could scale by 2, but scale with system base is error-free, simply an exponent shift.
This made t numerator calculation exact. (MOD part is exact)

t numerator divide by denominator may generate rounding errors, but it does not matter.
With half-way case, we expected t = .5, 1.5, 2.5, 3.5, ...

Since we scaled by 10, Z sign from t = +- +- +- +- +-
In other words, Z = -1/2 if FLOOR(t) =  1,  3,  5,  7,  9

--> Z = 1/2 * (-1)^FLOOR(t)