(42, all flavours) Integer Division - how?

[Albert Chan]

(12-17-2020 12:42 PM)Werner Wrote:  Actually that code works for Cc00 = Qq*Xx + Rr, too, save for the round-to-even cases, that are very rare.

Code:

    Half-way-case correction ...
    elsif Rr = Xx-Rr then
    c := Xx+1;
    b := INT(Cc00/c);
    a := Rr - MOD(CC00,c);
    if NOT(a=b or a=b-c ) then Qq:=Qq - 1;
  end;
end;

Your half-way-case had a typo. It should be b := Qq % c
If Qq is correct, we have:

Cc00 = Qq*Xx + Rr = Qq*c - Qq + Rr
Qq = Qq*c + Rr - Cc00

We take (mod c) for both side, b = LHS, a = RHS, and do the test.

---

If remainder() is available, we can replace (mod c) test with it.

PHP Code:

function remainder(x, y)            -- assumed x >=0, y > 0
    local r, halfy = fmod(x, y+y), y/2
    if r <= halfy then return r end -- q = (x-r)/y must be even
    r = r - y                       -- q is odd, r = (-y/2, y)
    return r < halfy and r or r - y -- halfway case: r = -y/2, q is even
end 


remainder() guaranteed that halfway case have even quotient.

For half-way case, Qq must be even (example, 11.5 -> 12, 12.5 -> 12)
We can use sign of remainder, for the half-way case correction:

→ if remaider(Cc00, Xx) < 0 then Qq := Qq - 1;

---

If Cc00/Xx fractional part is 0.5, it implied Cc000 / Xx is integer, ends in 5.

To "remove" 3 0's, and turn last digit to 5, Xx = 8*k
(Cc00 ± 100) / Xx will *not* be half-way case, since 100/8 = 12.5, not an integer.

We can use gap test to check for half-way case. This work on a 2-digits calculator:

→ if (Cc00+100)/Xx - Qq < Qq - (Cc00-100)/Xx then Qq := Qq - 1;

Example, if Cc00 = 900, Xx = 40, Qq = round(22.5) = 22

LHS = high gap = 25 - 22 = 3
RHS = low gap  = 22 - 20 = 2

This meant Qq were already rounded-down, and no correction needed for it.