Post Reply 
(42, all flavours) Integer Division - how?
12-19-2020, 03:14 AM (This post was last modified: 12-20-2020 11:09 AM by Albert Chan.)
Post: #40
RE: (42, all flavours) Integer Division - how?
The chance of hitting half-way cases are small.
We can do the remainder check by then. This made the code simpler too.

PHP Code:
function idiv6c(ab)   -- assumed b 0
    local r 
a/b
    local q 
floor(r)
    if 
~= r then return q end
    r 
= (a%b) * 2
    
if == b then r % (b+bend
    
return and q-or q
end 

Example, for 2-digit calculator, above/below halfway decides how to correct q

a/b = 700/22 = 31.81..., rounded to q = 32
ulp = (a%b)/b = 18/22 ≈ 0.81 ULP, above halfway, return q-1 = 31

a/b = 700/23 = 30.43..., rounded to q = 30
ulp = (a%b)/b = 10/23 ≈ 0.43 ULP, below halfway, return q = 30

---

For halfway case, r is updated, r = a % (b+b)
Previously, r = b, this implied updated r = b/2, or 3b/2
To maintain even q, and remainder range of ±b, 3b/2 got shifted down 2b, to -b/2

Only -b/2 remainder require correction: a/b = q - 1/2, rounded-up to q, floor-divide should be q-1

Example, for 2-digit calculator

a/b = 460/40 = 11.5, rounded to q = 12 (half-way to even)

r = (a%b)*2 = 40 = b --> signal halfway case
r = a%(b+b) = 60 --> signal remainder = -20, floor-divide should return q-1 = 11

Reuse the code for non-halfway: return r > b and q-1 or q

For above example, r=60, b=40, thus it return q-1 = 11, as expected

Update: removed variable h=b/2. This made the code more robust.

Previously, we had r = a%b, followed by r = a%(b+b) if halfway.
Last line was return r > h and q-1 or q

For halfway case, we may hit with *slight* floor-mod rounding.

If a is negative, a % (b+b) = (b+b) - |a| % (b+b) = 4h - 3h = h
But, 3h term might not be exact, thus last h may have *slight* rounding error.

Update 2: fix a typo for halfway test, r == 0 should be r == b
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-19-2020 03:14 AM



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