Codebase64 wiki

User Tools

Site Tools

Trace:
base:exponentiation

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision		Previous revision
base:exponentiation [2020-04-25 21:22] – created verzbase:exponentiation [2020-06-04 19:36] (current) – verz
Line 2: Line 2:
  
 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.  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 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. The multiplication algorithm provided is tailored for this routine: it accepts 32bit values and will produce a 32bit result.
  
Line 24: Line 26:
 ;       input:  B value to be raised ;       input:  B value to be raised
 ;               .A exponent ;               .A exponent
-; 
 ; ;
 ; algo:  if .A=0 res=1 ; algo:  if .A=0 res=1
 ;        if .A=1 res=B ;        if .A=1 res=B
-;                   _ +;             _ 
-;                  |  B*B if E=2 +;            | B if E=1 
-;        Exp(B,E)= |  B*Exp(B,E-1) if E is odd +;  Exp(B,E)= | B*Exp(B,E-1) if E is odd 
-;                  |_ Exp(B,E/2)*Exp(B,E/2) if E is even+;            |_Exp(B,E/2)*Exp(B,E/2) if E is even
 ; ;
 ; ************************************ ; ************************************
Line 44: Line 45:
  
 Exponent Exponent
-        cmp #0 +        tax 
-        beq res1+        beq res1        ; is E==0 ? 
 +        lda B 
 +        lsr 
 +        ora B+1 
 +        beq resB        ; if B==0 or B==1 then result=B 
 +        txa
         cmp #1         cmp #1
         bne ExpSub         bne ExpSub
-resB    lda #0          ; E=1, result=B+ 
 +resB    lda #0          ; E==1 | B==1 | B==0, result=B
         sta P+2         sta P+2
         sta P+3         sta P+3
Line 56: Line 63:
         sta P+1         sta P+1
         rts         rts
 +
 res1    sta P+1         ; E=0, result=1 res1    sta P+1         ; E=0, result=1
         sta P+2         sta P+2
Line 63: Line 71:
         rts         rts
  
-ExpSub  cmp #2 +ExpSub  lsr             ; E = int(E/2) 
-        beq Sqr         ; E is 2 +        beq resB        ; E is 1
-        lsr             ; E = int(E/2)+
         bcs ExpOdd      ; E is Odd         bcs ExpOdd      ; E is Odd
 +
 ExpEven jsr ExpSub      ; E is Even ExpEven jsr ExpSub      ; E is Even
-        ldx #$FC +        ldx #$3 
-_ldP    lda <p-252,x    ; multiply P by itself +_ldP    lda p,x         ; multiply P by itself 
-        sta <m-252,x    ; P is the result of a previous mult +        sta m,x         ; P is the result of a previous mult 
-        sta <n-252,x    ; copy P in M and N +        sta n,x         ; copy P in M and N 
-        inx +        dex 
-        bne _ldP+        bpl _ldP
         jmp Mult32               jmp Mult32      
-ExpOdd  asl+ 
 +ExpOdd  asl             ; E = 2*int(E/2) (=E-1)
         jsr ExpSub         jsr ExpSub
-        ldx #$FC +        ldx #$4 
-_ldD    lda <p-252,x    ; multiply P by B +_ldD    lda <p-1,x      ; multiply P by B 
-        sta <m-252,x    ; P is the result of a previous mult +        sta <m-1,x      ; P is the result of a previous mult 
-        inx             ; copy P in M+        dex             ; copy P in M
         bne _ldD         bne _ldD
         lda B           ; copy B in N         lda B           ; copy B in N
Line 89: Line 98:
         stx N+2         stx N+2
         stx N+3         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         jmp Mult32
  
base/exponentiation.txt · Last modified: 2020-06-04 19:36 by verz