(42, all flavours) Integer Division - how?

[Albert Chan]

There is the "cheating" way, by temporarily setting the rounding mode
I coded mathx.setround() for this purpose

PHP Code:

require 'mathx'
function idiv1(a,b)
    mathx.setround(-1)  -- round downwards
    a = mathx.rint(a/b)
    mathx.setround(0)   -- restore round-to-nearest
    return a
end 


Another way is to correct the quotient of a and b (assumed both integers)
Here, we assumed q, Q may have errors of ±1

a = q*b + r = q*c - q + r      , where c = b+1
a = Q*c + R

0 = (q-Q)*c - q + r - R      → -q + r - R ≡ 0 (mod c)

Since r and R can be calculated with MOD, we can correct for q
Assuming |q| < 2^53, this is the code:

PHP Code:

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


lua> a = 0x1p72
lua> for b=1e6+1, 1e6+9 do
:      q = idiv1(a,b) -- reference
:      print(b, q - floor(a/b), q - idiv2(a,b))
:      end

1000001     -1      0
1000002     -1      0
1000003     -1      0
1000004      0      0
1000005      0      0
1000006      0      0
1000007      0      0
1000008      0      0
1000009     -1      0