(42, all flavours) Integer Division - how?

[Albert Chan]

(12-19-2020 10:03 AM)Werner Wrote:  But I rewrite it as

function idiv3(a,b) -- assumed b > 0
local q, c = floor(a/b), b+1
a, b = a%b, a%c
b = (q-c+b)%c
if a==b then return q end
return q-1
end

If a ≥ b > 0, the rewrite work.

If a < 0, q < 0, q-c might overflow
If |a| < b, it may hit with floor-mod cancellation errors.

For tiny a = ε < b, rewritten code had:
a1 = a%b = ε
b1 = (q-c+a%c)%c = (-c+ε) % c = c - (c-ε), might not get back ε

lua> a, b, c, q = 1e-10, 2, 3, 0
lua> a1 = a%b
lua> b1 = (q - c + a%c)%c
lua> a1, b1 --> inequality force correction, returning wrong q-1 = -1
1e-010      1.000000082740371e-010

Original version work for all a, if q = ceil(a/b), or IP(a/b)

For tiny a = ε < b, original code had:
a1 = a%b - a%c = ε - ε = 0
b1 = q%c = 0, or 1

Both variables are exactly calculated. Thus correction code will work.