(41) Exponentiation & Residue Reduction

[Thomas Klemm]

Let us start with the following Python program:

Code:

def pow(b, x, m):
  r = 1
  while x:
    if x % 2:
      r = b * r % m
    b = b ** 2 % m
    x = IP(x / 2)    
  return r

With the help of the Python to RPN - source code converter it is translated to:

Code:

LBL "Z^Y%X"     // Label. Identify programs and routines for execution and branching. Parameter: local or global label.
RTN
LBL A           // def pow
XEQ 66          // reorder 3 params for storage
STO 00          // param: b
RDN
STO 01          // param: x
RDN
STO 02          // param: m
RDN
1
STO 03          // r 
LBL 00          // while
RCL 01          // x
X≠0?            // while true?
GTO 01          // while body
GTO 02          // resume
LBL 01          // while body
RCL 01          // x
2
MOD
X≠0?            // if true?
GTO 03          // if body
GTO 04          // resume
LBL 03          // if body
RCL 00          // b
RCL 03          // r
*
RCL 02          // m
MOD
STO 03          // r 
LBL 04          // resume
RCL 00          // b
X↑2
RCL 02          // m
MOD
STO 00          // b 
RCL 01          // x
2
/
IP              // Returns the integer part of x
STO 01          // x 
GTO 00          // while
LBL 02          // resume
RCL 03          // r
RTN             // return
LBL 50          // PyRPN Support Library of
"-Utility Funcs-"
RTN             // ---------------------------
LBL 66          // Reverse params. (a,b,c) -> (c,b,a)
X<>Y
RDN
RDN
X<>Y
RDN
RTN

Let's clear it up a bit:

• remove local label A
• remove reordering of params for storage
• remove empty support Library
• invert logic in condition
  

In the last step, the condition is inverted.
Instead of:

Code:

X≠0?            // while true?
GTO 01          // while body
GTO 02          // resume
LBL 01          // while body

We use:

Code:

X=0?            // while not?
GTO 02          // resume

This saves us both a LBL and GTO instruction.

With these changes we are already down at 51 bytes and could call it a day:

Code:

00 { 51-Byte Prgm }
01▸LBL "Z↑Y%X"
02 STO 02
03 R↓
04 STO 01
05 R↓
06 STO 00
07 1
08 STO 03
09▸LBL 00
10 RCL 01
11 X=0?
12 GTO 02
13 RCL 01
14 2
15 MOD
16 X=0?
17 GTO 04
18 RCL 00
19 RCL 03
20 ×
21 RCL 02
22 MOD
23 STO 03
24▸LBL 04
25 RCL 00
26 X↑2
27 RCL 02
28 MOD
29 STO 00
30 RCL 01
31 2
32 ÷
33 IP
34 STO 01
35 GTO 00
36▸LBL 02
37 RCL 03
38 END

We also saved a byte by choosing a shorter name.

But can we do better?
You may have noticed that line 13 could be removed since x is still present from line 10.
Furthermore, division by 2 and modulo 2 of x can be combined.

Code:

00 { 47-Byte Prgm }
01▸LBL "Z↑Y%X"
02 STO 02
03 R↓
04 STO 01
05 R↓
06 STO 00
07 1
08 STO 03
09▸LBL 00
10 RCL 01
11 X=0?
12 GTO 02
13 2
14 ÷
15 ENTER
16 IP
17 STO 01
18 X=Y?
19 GTO 04
20 RCL 00
21 RCL 03
22 ×
23 RCL 02
24 MOD
25 STO 03
26▸LBL 04
27 RCL 00
28 X↑2
29 RCL 02
30 MOD
31 STO 00
32 GTO 00
33▸LBL 02
34 RCL 03
35 END

So far we haven't bothered with registers or keeping results on the stack.
But if we leave x on the stack, we save 2 STO and 1 RCL instructions at the cost of 2 RDN instructions.
With this we not only save a register, but also another byte:

Code:

00 { 46-Byte Prgm }
01▸LBL "Z↑Y%X"     ; b x m -- b^x (mod m)
02 STO 00          ; m
03 1
04 STO 01          ; r
05 R↑
06 STO 02          ; b
07 R↑              ; x
08▸LBL 00          ; while
09 X=0?            ; x == 0
10 GTO 02          ; end while
11 2
12 ÷               ; x / 2
13 ENTER
14 IP              ; x // 2
15 X=Y?            ; x is even
16 GTO 01          ; end if
17 RCL 01          ; r
18 RCL 02          ; b
19 ×
20 RCL 00          ; m
21 MOD             ; r × b % m
22 STO 01          ; r
23 R↓              ; x
24▸LBL 01          ; end if
25 RCL 02          ; b
26 X↑2
27 RCL 00          ; m
28 MOD             ; b^2 % m
29 STO 02          ; b
30 R↓              ; x
31 GTO 00          ; while
32▸LBL 02          ; end while
33 RCL 01          ; r
34 END

Feel free to replace the 3 remaining registers with the synthetic registers M, N and O.