I am learning some assembly for a compiler project I am working on and I have come across the Exponentiation by Squaring algorithm when it came to calculating x ^ n. To get a grasp on how the algorithm works before I add the operation to my code generation, I have written it out to see if it works.
Is my code optimum? and can it be improved on (such as reducing the number of line needed and efficiency?)
I am assembling with nasm and I am running on x86_64 linux
; Function exp_by_squaring_iterative(x, n)
_ipow:
; set the x and y values
mov r8, 50 ; x
mov r9, 10 ; n
; check if n is 1
cmp r9, 1 ; compare n with 1
je _equalsOne ; goto equalsone if n is 1
jne _notEqualsOne ; goto noequalsone if n is not 1
; return 1
_equalsOne:
mov rax, r8
ret ; if n equals 1 return x
; if n < 0 then
_notEqualsOne:
cmp r9, 0 ; compare n with 0
jl _lessthan ; goto lessthan zero if x is less than zero
jnl _equalszero ; goto equalszero if n is equal to zero
_lessthan:
; x := 1 / x;
; n := -n;
xor rdx, rdx ; zero rdx
mov rax, 1 ; move 1 to rax
div r8 ; divide 1 / x
mov r8, rax ; move x back to r8
not r9 ; revers ns bits
; if n = 0 then return 1
_equalszero:
cmp r9, 0 ; compare n with zero
je _ezero ; go to ezero if n equals zero
jne _nzero ; go to nzero if n is not zero
_ezero: ; return 1
mov rax, 1 ; set rax as 1
ret ; return 1 if n is 0
; y := 1;
_nzero:
mov r10, 1 ; set r10 as 1, y
_loop1:
mov rax, r9 ; move n to rax
test al, 1 ; check if n is an odd number by testing the low bit
jz _even ; jump if even = lowest bit clear = zero
jnz _odd ; jump if odd = lowest bit set
; if n is even then
_even:
; x := x * x;
mov rax, r8 ; move x to rax
mul rax ; multiply x by itself
mov r8, rax ; move x back to r8
; n := n / 2;
mov rbx, 2 ; 2 to rbx
mov rax, r9 ; move n to rax
div rbx ; divide n by 2
mov r9, rax ; move n back
jmp _condition ; jump over odd since if even, was processed
; n is an odd number
_odd:
; y := x * y;
mov rax, r10 ; move y to rax
mul r8 ; multiply y by x
mov r10, rax ; move y back to r10
; x := x * x;
mov rax, r8 ; mov x to rax
mul rax ; multiply x by itself
mov r8, rax ; mov x back to r10
; n := (n – 1) / 2;
mov rax, r9 ; mov n to rax
sub rax, 1 ; minus 1 from n
mov rbx, 2 ; set rbx as 2
div rbx ; divide n by 2
mov r9, rax ; move n back to rax
; while n > 1 do
_condition:
cmp r9, 1 ; compare r9 with 1
jg _loop1 ; if 1 is greater than 1 then loop
; return x * y
mov rax, r8 ; move x to rax
mul r10 ; multiple x and y
ret ; return