# ### Site Tools

No renderer 'pdf' found for mode 'pdf'

## Meta

base:exponentiation

This is an old revision of the document!

# Exponentiation

This routine computes the exponentiation of a 16 bit value. It handles only integer values. The largest result is 2^32-1 (32 bits); that makes 31 the largest possible exponent. Results larger than 2^32-1 will overflow. The algorithm is recursive and at each iteration breaks the exponentiation in a simpler product: if the exponent is even, it will compute the exponentiation with half the exponent and square it, while if it's odd it will compute the product of the value by the value raised at the exponent minus one. The number of multiplications to be computed varies with the exponent, and the maximum is eight for the exponent 31 (31, 30, 15, 14, 7, 6, 3, 2). The multiplication algorithm provided is tailored for this routine: it accepts 32bit values and will produce a 32bit result.

```Num1=25
Num2=5

example lda #>Num1
sta B+1
lda #<Num1
sta B
lda #Num2
jmp Exponent

; ************************************
;
;       Exponent
;
;       input:  B value to be raised
;               .A exponent
;
;
; algo:  if .A=0 res=1
;        if .A=1 res=B
;                   _
;                  |  B*B if E=2
;        Exp(B,E)= |  B*Exp(B,E-1) if E is odd
;                  |_ Exp(B,E/2)*Exp(B,E/2) if E is even
;
; ************************************

P = \$fb
M = \$62
N = \$6a
;E = \$2
B = \$3

Exponent
cmp #0
beq res1
cmp #1
bne ExpSub
resB    lda #0          ; E=1, result=B
sta P+2
sta P+3
lda B
sta P
lda B+1
sta P+1
rts
res1    sta P+1         ; E=0, result=1
sta P+2
sta P+3
lda #1
sta P
rts

ExpSub  cmp #2
beq Sqr         ; E is 2
lsr             ; E = int(E/2)
bcs ExpOdd      ; E is Odd
ExpEven jsr ExpSub      ; E is Even
ldx #\$FC
_ldP    lda <p-252,x    ; multiply P by itself
sta <m-252,x    ; P is the result of a previous mult
sta <n-252,x    ; copy P in M and N
inx
bne _ldP
jmp Mult32
ExpOdd  asl
jsr ExpSub
ldx #\$FC
_ldD    lda <p-252,x    ; multiply P by B
sta <m-252,x    ; P is the result of a previous mult
inx             ; copy P in M
bne _ldD
lda B           ; copy B in N
sta N
lda B+1
sta N+1
;lda #0
stx N+2
stx N+3
jmp Mult32
Sqr     lda B           ; multiply B by itself
sta M           ; copy B in M and N
sta N
lda B+1
sta M+1
sta N+1
lda #0
sta M+2
sta M+3
sta N+2
sta N+3
jmp Mult32

Mult32          ; 32=32*32
lda #0
sta P
sta P+1
sta P+2
sta P+3
ldy #\$20
_loop   asl p
rol p+1
rol p+2
rol p+3
asl N
rol N+1
rol N+2
rol N+3
bcc _skip
clc
ldx #\$fc 