(42S) Quotient and Remainder
04-06-2023, 12:03 AM
Post: #6
 Albert Chan Senior Member Posts: 2,697 Joined: Jul 2018
RE: (42S) Quotient and Remainder
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)
 « Next Oldest | Next Newest »

 Messages In This Thread (42S) Quotient and Remainder - Werner - 04-05-2023, 09:38 AM RE: (42S) Quotient and Remainder - Albert Chan - 04-05-2023, 12:39 PM RE: (42S) Quotient and Remainder - Werner - 04-05-2023, 01:11 PM RE: (42S) Quotient and Remainder - Albert Chan - 04-05-2023, 01:48 PM RE: (42S) Quotient and Remainder - Werner - 04-05-2023, 03:55 PM RE: (42S) Quotient and Remainder - Albert Chan - 04-06-2023 12:03 AM RE: (42S) Quotient and Remainder - Albert Chan - 04-06-2023, 02:55 PM

User(s) browsing this thread: 1 Guest(s)