Exponentiation by squaring in x64 Linux Assembly

Question

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 

Answer 1

• Testing for n == 1 before handling a negative n seems like a bug. Consider what would have happen with n == -1:

  1. n is not 1. Branch to _notEqualsOne.
  2. n is less than 0. Branch to _lessthan. Now n becomes 1.
  3. The code falls through all the way to _loop1.
  4. n is odd. Branch to _odd.
  5. y := x * y; x := x * x; n := 0`
  6. _condition fails; fall through the return x * y.

  Now, this is bad: we are returning an inversed cube of the original x.

  Postpone equality for 1 testing until the negative case is handled.

• Eliminate _equalsOne label:

    cmp r9, 1
    jne _notEqualsOne
  
    mov rax, r8
    ret
  
  _notEqualsOne:
  

• cmp r9, 0 is executed twice. This is redundant (keep in mind that jne does not affect the flags):

    cmp r9, 0
    jne _notZero
    ; next two lines is what your code does at _ezero
    mov rax, 1
    ret
  
  _notZero:
    jnl _positive
    ; handle a negative case here:
    ; x := 1/x
    ; n := -n
    ; and proceed with the _positive case
    ....
  
  _positive:
    ; A regular case. n > 1 is guaranteed.
  

• Again, _even and _odd lead to some code duplication. x := x * x and n := n/2 are spelled out in both branches. Consider

    test al, 1
    jz _even
  
    ; n is odd here
    ; y := x * y
    ; n := n - 1
  
  _even:
    ; x := x * x
    ; n := n / 2
  

• Division by 2 is better be a right shift. One instruction versus four; a definite win.

• while n > 1 style loop looks more natural than do ... while n > 1.

Answer 2

Handling n < 0

The computation is entirely integer-based. When x := 1 / x is computed, that means the new x is usually zero, though if x was 1 to begin with then the new x is still 1.

As it currently is, with an integer computation, handling negative n makes very little sense. It almost never gives a useful result. It makes more sense to just not handle that case at all - of course this saves code.

There are more ways to multiply than mul

;         x := x * x;
   mov rax, r8 ; move x to rax
   mul rax     ; multiply x by itself
   mov r8, rax ; move x back to r8

Unless you need the upper 64 bits of the 128 bit product, it is easier and more appropriate to use the 2-operand or 3-operand form (whichever applies) of imul. imul is described in the manual as a signed multiplication, but that only matters for "upper half" which is ignored in most cases. See for example Why is imul used for multiplying unsigned numbers?.

So this code can be:

imul r8, r8

Loading small constants into 64bit registers

mov rax, 1 is actually not the best way to set rax to 1, the best way is mov eax, 1.

If the assembler honours the program text, mov rax, 1 would be encoded as 48 c7 c0 01 00 00 00, using a REX.W prefix and the C7-group mov. mov eax, 1 does exactly the same thing (writes to 32bit registers are zero-extended) but can be encoded as b8 01 00 00 00, saving two bytes (a byte from REX prefix, and an extra byte because the B8-group mov can be used).

Saving 2 bytes is not critial, but all else being equal, smaller code is better (faster to fetch, less pressure on code cache).

Comparing a register to zero

cmp r9, 0 is an obvious way to do it, but test r9, r9 saves a byte.