(42, all flavours) Integer Division - how?

[Albert Chan]

(12-17-2020 08:53 AM)Werner Wrote:  I wanted to use integer division to correctly split
Cc00 = Qq*Xx + Rr, where each letter is a half-length integer and Cc<Xx

Revisiting DIV(Cc00, Xx), using mod 10 test for halfway case.

Note: the code assumed half-length = 1.
This can be easily generalize, by adjust code for last nonzero digit of Rr.

PHP Code:

function idiv7(Cc00, Xx)
    local Qq, Rr = d2(Cc00/Xx), Cc00%Xx -- simulate 2 digits calculator
    local c = floor(Qq)
    if Qq ~= c then return c end        -- Fast-path
    if Rr < Xx-Rr then return c end     -- Cc00/Xx rounded-down to c
    if Rr > Xx-Rr then return c-1 end   -- Cc00/Xx rounded-up to c
    c = Rr % 10                         -- halfway: Cc00 = (2*Qq +/- 1) * Rr
    if c == 0 then c = Rr/10 end        -- last nonzero digit of Rr
    if 0 ~= ((Qq%10)*2-9)*c % 10 then Qq = Qq-1 end
    return Qq
end 


Since Lua is not really a 2-digits calculator, I added d2():
d2 = function(x) return string.format('%.2g',x) + 0 end

The code confirmed correct for all possible 2-digits combinations of (Cc, Xx), Cc<Xx
Proof that above half-way test work generally, for half-length integers.

Cc00 / Xx = (Cc00/100) / (Xx/100)
But, Xx < 100, so factoring out 10's always have numerator ends in 0.

For halfway case, taking mod 10 both side, we have:

Cc00 = (2*Qq ± 1) * Rr
0 ≡ (2*Qq ± 1) * c (mod 10), where c = last non-zero decimal digit of Rr

Update:

If Xx had all factors of 10 removed, Xx must still be even.
Rr = Xx/2 ends in 1,2,3,4, 6,7,8,9. In other words, c ≠ 0, or 5

If (2*Qq + 1)*c ≡ 0, then (2*Qq - 1)*c ≡ -2*c ≠ 0 (mod 10)

Passing +1 test implied failing -1 test, and vice versa.