Post Reply 
(42, all flavours) Integer Division - how?
12-17-2020, 06:41 PM
Post: #36
RE: (42, all flavours) Integer Division - how?
(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(xy)            -- assumed x >=00
    local r
halfy fmod(xy+y), y/2
    
if <= halfy then return r end -- = (x-r)/y must be even
    r 
y                       -- q is odd= (-y/2y)
    return 
halfy and or -- halfway case: = -y/2q 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.
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: (42, all flavours) Integer Division - how? - Albert Chan - 12-17-2020 06:41 PM



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