(41) Exponentiation & Residue Reduction

[Albert Chan]

(05-08-2020 01:58 PM)Werner Wrote:  Stack-only, without synthetics, 50 bytes
Calculate R := B^X mod M ...

Amazing !
I touch up a bit so that it can copy/paste directly into Free42 (52 bytes)

Code:

01▸LBL "Z↑YMOD"
02 ABS
03 1
04 R↓
05 R↓
06▸LBL 02
07 2
08 STO÷ ST Y
09 X<> ST L
10 X<>Y
11 IP
12 STO- ST L
13 R↓
14 X<> ST L
15 X=0?
16 GTO 00
17 R↓
18 STO× ST Y
19 X<>Y
20 LASTX
21 MOD
22 X<> ST Z
23▸LBL 00
24 R↓
25 STO× ST X
26 LASTX
27 MOD
28 R↑
29 X≠0?
30 GTO 02
31 RCL ST Z
32 END

Example 123^456 mod 789:

123 [Enter] 456 [Enter] 789 [XEQ] "Z↑YMOD"     → 699

This version does binary ladder expoentiation from right to left, like this:

Code:

(define (pow-mod b x m r)
  (if (fxzero? x) r
      (pow-mod [mod (* b b) m] [fx/ x 2] m
        [if (even? x) r (mod (* b r) m)] )))

scheme> (trace pow-mod)
(pow-mod)
scheme> (pow-mod 123 456 789 1)
|(pow-mod 123 456 789 1)
|(pow-mod 138 228 789 1)
|(pow-mod 108 114 789 1)
|(pow-mod 618 57 789 1)
|(pow-mod 48 28 789 618)
|(pow-mod 726 14 789 618)
|(pow-mod 24 7 789 618)
|(pow-mod 576 3 789 630)
|(pow-mod 396 1 789 729)
|(pow-mod 594 0 789 699)
|699
699