(42, all flavours) Integer Division - how?

[Albert Chan]

(12-15-2020 12:43 PM)Werner Wrote:  Yes, but that is only with binary floating point, not with decimal, as in HP calcs ;-)

Not true. When floor-mod "fix" sign, subtraction cancellation may occur, binary or decimal.

But, the fix is easy. (your code already fixed this, by using IP)

The trick is to start with q = ceil(a/b), or IP(a/b)

For a<0, |a|<b: min(a/b) = min(ulp(b)-b)/b) = min(ulp(b)/b) - 1 > -1

Confirm:
Free42 Binary: 2 53 X^Y 1 - 1/X 1 -  → -9.999999999999999e-1
Free42 Decimal: 1E34 1 - 1/X 1 -      → -9.999999999999999999999999999999999e-1

This guaranteed q start with 0, for negative tiny a.

(12-15-2020 10:37 AM)Albert Chan Wrote:  For negative tiny a = -ε

a1 = a%b - a%c = (b-ε) - (c-ε) = -1 + error
b1 = q%c = q = 0, or -1

It is this error that make idiv3 failed.

If error = 0, this always work, nothing to fix.
If error ≠ 0, and q = 0, we get this:

a1 == b1 test : -1 + error == 0     → error == 1
a1==b1-c test: -1 + error == -c    → error == -b

Since error is tiny, error(b-ε) ≤ ½ulp(b), error(c-ε) ≤ ½ulp(c), both tests failed.
This force correction, returning corrected q-1 = -1

This is revised idiv3 should work with non-integer inputs, if c = b+1 is exact.
I also added a fast-path, to speed things up.

PHP Code:

function idiv3c(a,b)        -- assumed b > 0
    local q, c = ceil(a/b), b+1
    if q*b > a then return q-1 end
    a, b = a%b - a%c, q%c   -- a-b = (-2c, c-1)
    if a==b or a==b-c then return q end
    return q-1
end