(42S) Quotient and Remainder
|
04-06-2023, 12:03 AM
Post: #6
|
|||
|
|||
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;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;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)