Section 4.6.3
1. xm, where m = 2⌊lg n⌋ is the highest power of 2 less than or equal to n.
2. Assume that x is input in register A, and n in location NN; the output is in register X.
01 A1 ENTX 1 1 A1. Initialize.
02 STX Y 1 Y ← 1.
03 STA Z 1 Z ← x.
04 LDA NN 1 N ← n.
05 JAP 2F 1 To A2.
06 JMP DONE 0 Otherwise the answer is 1.
07 5H SRB 1 L + 1 − K
08 STA N L + 1 − K N ← ⌊N/2⌋.
09 A5 LDA Z L A5. Square Z.
10 MUL Z L
11 STX Z L Z ← Z × Z mod w.
12 A2 LDA N L A2. Halve N.
13 2H JAE 5B L + 1 To A5 if N is even.
14 SRB 1 K
15 A4 JAZ 4F K Jump if N = 1.
16 STA N K − 1 N ← ⌊N/2⌋.
17 A3 LDA Z K − 1 A3. Multiply Y by Z.
18 MUL Y K − 1
19 STX Y K − 1 Y ← Z × Y mod w.
20 JMP A5 K − 1 To A5.
21 4H LDA Z 1
22 MUL Y 1 Do the ...Get Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
