Post Reply 
(42, all flavours) Integer Division - how?
12-15-2020, 02:51 PM (This post was last modified: 12-16-2020 08:30 PM by Albert Chan.)
Post: #31
RE: (42, all flavours) Integer Division - how?
(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
ceil(a/b), b+1
    
if q*a then return q-1 end
    a
a%a%cq%c   -- a-= (-2cc-1)
    if 
a==or a==b-c then return q end
    
return q-1
end 
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-15-2020 02:51 PM



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