(42, all flavours) Integer Division - how?

[Albert Chan]

In the mean time, this is my implementation for remainder(a,b), for Free42 Decimal.
Since a = q*b + r = (-q)*(-b) + r, remainder(a,b) = remainder(a,|b|)

That's why I set b = |b|, before the code even started.
This allowed REM work with signed arguments, both a and b.

Code:

00 { 44-Byte Prgm }
01▸LBL "REM"    @  L     X     Y     Z     T
02 ABS          @  All code below, b >= 0
03 RCL ST Y
04 RCL ST Y     @        b     a     b     a
05 MOD          @  b   a%b     b     a     a
06 STO- ST L
07 LASTX        @    b-a%b   a%b     b     a
08 X<>Y         @      a%b b-a%b     b     a
09 X<Y?
10 RTN          @ positive remainder
11 X=Y?
12 GTO 00
13 X<>Y         @ negative remainder
14 +/-
15 RTN
16▸LBL 00       @ halfway case
17 R↓
18 R↓
19 10
20 ×            @   b*base     a   b/2   b/2
21 MOD
22 X<>Y
23 STO+ ST X
24 ÷            @        k   b/2   b/2   b/2
25 IP
26 -1
27 X<>Y         @    IP(k)    -1   b/2   b/2
28 Y↑X
29 ×
30 END

Example: (for halfway case, quotient must be even)

 459 40 XEQ "REM"   →  19 =  459 - 11*40
 460 40 XEQ "REM"   → -20 =  460 - 12*40
 461 40 XEQ "REM"   → -19 =  461 - 12*40
-459 40 XEQ "REM"   → -19 = -459 + 11*40
-460 40 XEQ "REM"   →  20 = -460 + 12*40
-461 40 XEQ "REM"   →  19 = -461 + 12*40

9 PI XEQ "MOD" →  2.716814692820413523074713233440994
9 PI XEQ "REM" → -0.424777960769379715387930149838509

Since REM based from MOD, it is numerically better if we pull out a's sign.
This way, we avoided floor-mod subtraction cancellation errors, when it "fix" sign.

remainder(a,b) = sign(a) * remainder(|a|, b)

We can use REM to implement DIV, like this

(12-18-2020 12:08 AM)Albert Chan Wrote:  remainder() based idiv is very elegant.

PHP Code:

function idiv6(a, b)    -- assumed b > 0
    local r = a/b
    local q = floor(r)
    if q == r and remainder(a, b) < 0 then q=q-1 end
    return q
end