Finding the nth prime in nasm x86_64 assembly

Question

I'm attempting to write a program that will find the nth prime - in this case the 10001st prime.

Currently, the program detects every number as a prime number, so my result ends up being 10002.

When stepping through the program in GDB, the values being retrieved from the array of primes to divide are not what is expected - i.e. after determining that 3 is prime, the next iteration for 4, the program retrieves 770 from the array.

The code is:

%include '../resources.asm'

SECTION .data

SECTION .text
global main
extern malloc, free, calloc
main:
    ; Allocate space for primes
    mov rsi, 8
    mov rdi, 10001
    call calloc
    ; Store address in r10
    mov r10, rax
    ; First prime is 2
    mov qword [r10], 2
    ; r11 is current number of primes found
    mov r11, 1
    ; r12 is current number being checked
    mov r12, 2
.outer:
    ; Move to next number
    inc r12
    ; Reset array index
    mov rcx, 0
.inner:
    ; Get number and divisor in rax and rbx respectively
    mov rax, r12
    mov qword rbx, [r10 + rcx] ;;;; Issue here, rbx is 770?
    ; Increment array index
    inc rcx
    ; Get modulus
    call umod
    ; If modulus is 0, number is not prime, move to next number
    cmp rax, 0
    jz .outer
    ; See if we've hit the end of current list of primes
    cmp rcx, r11
    jnz .inner
    ; If we are at the end of the list of primes, move the current number into the array
    mov qword [r10 + rcx], r12
    inc r11
    ; Stop if we've got the 10001st prime
    cmp r11, 10001
    jl .outer

And the umod snippet from resources

;
; int udiv(int rax, int rbx) -> rax, rbx
; Unsigned division
udiv:
    push rdx

    xor rdx, rdx
    div rbx
    mov rbx, rdx

    pop rdx
    ret

;
; int umod(int rax, int rbx) -> rax
; Unsigned modulus operation
umod:
    call udiv
    mov rax, rbx

    ret

Note, I realize I may be not following the correct conventions for parameter passing and such. Feel free to make notes if you think it would be helpful.

You need to scale your indexes into the prime buffer by 8 as you're storing 8-byte entities. — 500 - Internal Server Error, Nov 04 '21 at 22:30
@500-InternalServerError Thank you. I don't know why I didn't think to scale my index! — H. Ross, Nov 04 '21 at 22:36

score 0 · Accepted Answer · answered Nov 04 '21 at 22:38

0

As pointed out in the comments, I was not scaling my index register by 8 to compensate for the 8-byte values being stored. The resultant fixed code is here:

%include '../resources.asm'

SECTION .data

SECTION .text
global main
extern malloc, free, calloc
main:
    ; Allocate space for primes
    mov rsi, 8
    mov rdi, 10001
    call calloc
    ; Store address in r10
    mov r10, rax
    ; First prime is 2
    mov qword [r10], 2
    ; r11 is current number of primes found
    mov r11, 1
    ; r12 is current number being checked
    mov r12, 2
.outer:
    ; Move to next number
    inc r12
    ; Reset array index
    mov rcx, 0
.inner:
    ; Get number and divisor in rax and rbx respectively
    mov rax, r12
    mov r13, rcx
    imul r13, 8
    mov qword rbx, [r10 + r13]
    ; Increment array index
    inc rcx
    ; Get modulus
    call umod
    ; If modulus is 0, number is not prime, move to next number
    cmp rax, 0
    jz .outer
    ; See if we've hit the end of current list of primes
    cmp rcx, r11
    jnz .inner
    ; If we are at the end of the list of primes, move the current number into the array
    mov r13, rcx
    imul r13, 8
    mov qword [r10 + r13], r12
    inc r11
    ; Stop if we've got the 10001st prime
    cmp r11, 10001
    jb .outer

    ; Print out result
    mov rax, r12
    call itoa
    mov rdi, rax
    call sprintlf
    call free



    call exit

answered Nov 04 '21 at 22:38

H. Ross

470
3
17

3

Actually, there's a much neater way to do that: `mov qword rbx, [r10 + r13*8]` - now, I can't recall for sure if that works with any index register, but I think it might for 64-bit at least. This works for values 2, 4, 8 only (plus the implicit 1, of course). – 500 - Internal Server Error Nov 04 '21 at 22:40
That is much neater, thank you! Learning new things with each problem. – H. Ross Nov 04 '21 at 23:08
@500-InternalServerError: Correct, the high registers r8-r15 can be used freely in SIB addressing modes. A few have quirky encodings that might cost you some extra bytes of code space, but they still work correctly. See https://stackoverflow.com/questions/36529449/why-are-rbp-and-rsp-called-general-purpose-registers/51347294#51347294 – Nate Eldredge Nov 04 '21 at 23:10
1

Or you can just increment a pointer by 8, so you only need one register. Also, you don't need to wrap a function around an instruction like `div`, that's just harder to read. If you wanted to break up into functions, you might write one that loops until it finds the next prime above some start point, and iterate that. Or not, since you're using the existing list of primes for trial division, rather than e.g. just odd numbers. Still slower than a sieve, but better than e.g. just trying every odd divisor, as long as you stop at the sqrt (when quotient < trial divisor) – Peter Cordes Nov 05 '21 at 03:51
1

Related: [Checking if a number is prime in NASM Win64 Assembly](https://codereview.stackexchange.com/a/204965) code review re: prime checking showing the quotient < divisor stop condition as a way to do the `divisor <= sqrt(n)` condition. – Peter Cordes Nov 05 '21 at 03:51
1

BTW, if you were going to multiply, `imul r13, rcx, 8` could copy-and shift. Or `mov` / `shl r13, 3`. Of course it's better to do that as part of the addressing mode, or like I said, even better to increment a pointer so the addressing mode is a simple one-register `div qword [r11]` or something. Note that R12..R15 are call-preserved in x86-64 SysV, like RBX, RBP, and RSP. Main's caller often doesn't care, but it's still violating the ABI to modify them without saving/restoring. – Peter Cordes Nov 05 '21 at 03:56

Finding the nth prime in nasm x86_64 assembly

1 Answers1