Large number (Project Euler #10)

[iVision]

Hey, I'm new to assembly and I'm using the Project Euler to learn this, but I'm stuck at the #10.. Because I use a 32 bit register it cannot fit it. The answer is: 142913828922 which is wayy to large to fit.
How would I do this in 86 Assembly (NASM)?

Thanks in advance

[Frank Kotler]

Well, use two registers. Of course, as soon as you get the sum of primes under two million, someone's going to want the sum of primes under two billion! (at which point we're probably going to need to put partial numbers in memory)

See if this helps ya:

Code: [Select]

;--------------------------------------------------------------
; u64toda - converts (64 bit) integer in edx:eax
; to (comma delimited) decimal representation in
; zero-terminated string in buffer pointed to by edi
;-----------------------------------------------------------------
u64toda:
                pusha
                mov ebx, edx     ; stash high dword
                mov esi,0Ah      ; prepare to divide by 10
                xor ecx, ecx     ; zero the digit count
                jmp highleft     ; check is high word 0 ?
highword:
                xchg eax,ebx    ; swap high & low words
                xor edx,edx     ; zero edx for the divide!
                div esi         ; divide high word by 10
                xchg eax,ebx    ; swap 'em back
                div esi         ; divide low word including remainder
                push edx        ; remainder is our digit - save it
                inc ecx         ; count digits
highleft:
                or ebx,ebx
                jnz highword
lowleft:
                xor edx,edx          ; zero high word
                div esi              ; divide low word by 10
                push edx             ; our digit
                inc ecx              ; count it
                or eax,eax           ; 0 yet ?
                jne lowleft
                cmp ecx, byte 4      ; commas needed ?
                jl write2buf         ; nope
                xor edx,edx            ; zero high word for divide
                mov eax,ecx            ; number of digits
                mov ebx,3
                div ebx
                mov esi,edx            ; remainder = number digits before comma
                test edx,edx
                jnz write2buf        ; no remainder?
                mov esi,3             ; we can write 3 digits, then.
write2buf:
                pop eax              ; get digit back - in right order
                add al,30H           ; convert to ascii character
                stosb                ; write it to our buffer
                dec esi               ; digits before comma needed
                jnz moredigits       ; no comma needed yet
                cmp ecx,2             ; we at the end?
                jl moredigits        ; don't need comma
                mov al,','           ; write a comma
                stosb
                mov esi,03h           ; we're good for another 3 digits
moredigits:
                loop write2buf       ; write more digits - cx of 'em
                mov al,00h           ; terminate buffer with zero
                stosb
popa
                ret
;-------------------------------------------------------------

Best,
Frank

[iVision]

Well, use two registers. Of course, as soon as you get the sum of primes under two million, someone's going to want the sum of primes under two billion! (at which point we're probably going to need to put partial numbers in memory)

See if this helps ya:

Code: [Select]

;--------------------------------------------------------------
; u64toda - converts (64 bit) integer in edx:eax
; to (comma delimited) decimal representation in
; zero-terminated string in buffer pointed to by edi
;-----------------------------------------------------------------
u64toda:
                pusha
                mov ebx, edx     ; stash high dword
                mov esi,0Ah      ; prepare to divide by 10
                xor ecx, ecx     ; zero the digit count
                jmp highleft     ; check is high word 0 ?
highword:
                xchg eax,ebx    ; swap high & low words
                xor edx,edx     ; zero edx for the divide!
                div esi         ; divide high word by 10
                xchg eax,ebx    ; swap 'em back
                div esi         ; divide low word including remainder
                push edx        ; remainder is our digit - save it
                inc ecx         ; count digits
highleft:
                or ebx,ebx
                jnz highword
lowleft:
                xor edx,edx          ; zero high word
                div esi              ; divide low word by 10
                push edx             ; our digit
                inc ecx              ; count it
                or eax,eax           ; 0 yet ?
                jne lowleft
                cmp ecx, byte 4      ; commas needed ?
                jl write2buf         ; nope
                xor edx,edx            ; zero high word for divide
                mov eax,ecx            ; number of digits
                mov ebx,3
                div ebx
                mov esi,edx            ; remainder = number digits before comma
                test edx,edx
                jnz write2buf        ; no remainder?
                mov esi,3             ; we can write 3 digits, then.
write2buf:
                pop eax              ; get digit back - in right order
                add al,30H           ; convert to ascii character
                stosb                ; write it to our buffer
                dec esi               ; digits before comma needed
                jnz moredigits       ; no comma needed yet
                cmp ecx,2             ; we at the end?
                jl moredigits        ; don't need comma
                mov al,','           ; write a comma
                stosb
                mov esi,03h           ; we're good for another 3 digits
moredigits:
                loop write2buf       ; write more digits - cx of 'em
                mov al,00h           ; terminate buffer with zero
                stosb
popa
                ret
;-------------------------------------------------------------

Best,
Frank

Oef that is way to hard for a rookie like me haha. How would I even store a 64 bit number? I guess you store the high 32 bits into edx, and the lower 32 bits into eax? (Or visa versa?) How would this even look in assembly? I mean how do you get the higher/lower part when it doesn't fit into a register directly?
I guess this topic is way beyond my knowledge about assembly, but it would be nice if I could understand this

Thanks for replying:)

[Frank Kotler]

Well, in general, once you've got a new value:

Code: [Select]

add eax, (new value)
adc edx, 0 ; any "carry" goes in edx

Since you're probably using eax and edx in calculating primes, you may want to use other registers (or memory) here... but that's the general idea. (yes, the high 32 bits go in edx, the low 32 bits in eax) If you care to post what you've got so far, we may be able to provide more specific suggestions.

I should point out that the routine I posted is far from "optimized". It's supposed to be "easy to understand". You should see the optimized one!

If you're a "rookie", it may be that Project Euler is too advanced to start with. Won't hurt to "stretch yourself" a little, but there's a risk of frustrating yourself. Take smaller steps, if you find you need to. (FWIW, my little sister's a mathematician, and informs me that "Euler" is pronounced "oiler", not "you-ler" as I would have naively assumed - if you care about that sort of thing)

Best,
Frank

[iVision]

Well, in general, once you've got a new value:

Code: [Select]

add eax, (new value)
adc edx, 0 ; any "carry" goes in edx

Since you're probably using eax and edx in calculating primes, you may want to use other registers (or memory) here... but that's the general idea. (yes, the high 32 bits go in edx, the low 32 bits in eax) If you care to post what you've got so far, we may be able to provide more specific suggestions.

I should point out that the routine I posted is far from "optimized". It's supposed to be "easy to understand". You should see the optimized one!

If you're a "rookie", it may be that Project Euler is too advanced to start with. Won't hurt to "stretch yourself" a little, but there's a risk of frustrating yourself. Take smaller steps, if you find you need to. (FWIW, my little sister's a mathematician, and informs me that "Euler" is pronounced "oiler", not "you-ler" as I would have naively assumed - if you care about that sort of thing)

Best,
Frank

Care to explain how to pronounce oiler, as in oiii-ler? I pronounced as éúlerr/ölerr (if you know the Deutsch ö) as an Hollander

On topic: I totaly forget to add the source I had, sorry! I guess it could be better. But I don't know how. Also I don't know if people considering it as spam if I post all my solutions. (I guess I'll just create a thread with all the solutions I have and hopefully someone responds )
Anyway I tried with this code, but it never complete (since it can fit the register or something, at first I thought it just took long )

Code: [Select]

; Parameters: int max
; Description: find the sum of prime numbers under max
_sum_prime:
push ebp
mov ebp, esp

push ebx
push edx

mov ebx, dword 2
mov edx, dword 2
.do:
push ebx
call _next_prime

mov ebx, eax

cmp eax,[ ebp + 8]
jg .break

add edx, ebx
jmp .do


.break:
mov eax, edx

pop edx
pop ebx

mov esp, ebp
pop ebp
ret
;_sum_prime


; Parameters: int prev_prime
; Description: get the next prime number, from prev_prime
_next_prime:
push ebp
mov ebp, esp

push ecx ; save ecx
mov ecx, [ebp + 8] ; ecx = prev_prime

.loop:
inc ecx

push ecx
call _is_prime ; is_prime(ecx)

test eax, eax
jne .break ; ecx is prime number, so break it

jmp .loop ; goto loop

.break:

mov eax, ecx ; store return value
pop ecx ; restore ecx

mov esp, ebp
pop ebp
ret
;_next_prime



; Parameters: int a
; Description: checks if number is a prime
_is_prime:
push ebp
mov ebp, esp

sub esp, 4

push edx ; saves register
mov edx, [ebp + 8] ; hold parameter in edx

mov [ebp - 4], dword 2 ; int i = 2

.for_loop:
push dword [ebp - 4]
push edx
call modulus

test eax, eax
je .test_prime

inc dword [ebp - 4] ; i++
cmp [ebp - 4], edx
jl .for_loop ; i < a

.test_prime:
cmp [ebp - 4], edx
jne .else ; if (i != num) goto else;
mov eax, 1 ; eax = 1 (true)
jmp .end ; goto end; (skip the else block)
.else:
mov eax, 0 ; eax = 0 (false)
.end:
pop edx ; remember to restore it!!

mov esp, ebp
pop ebp
ret 4
;_is_prime



; Parameters: int a, int b
; Description: returns a % b (the remainder)
modulus:
push ebp
mov ebp, esp

push ecx
push edx

xor edx, edx
mov eax, [ebp + 8] ;a
mov ecx, [ebp + 12] ;b

div ecx ;edx holds remainder (a % b)
mov eax, edx ;return remainder

pop edx
pop ecx

mov esp, ebp
pop ebp

ret 8
;modulus
Be easy on me as a rookie Also a side question: when performing calculations, or doing stuff. I could hold the 'data' in registers, or in local variables. What is recommended? Or is this just a user preference? (I like holding it in registers, because its easier to remember what a register represented then [ebp - x])

Also I found a couple problems very easy, and fun to solve in NASM. But yea maybe some are too hard for me. Anyway it definitely helps me understanding it. And I didn't know any other exercises I could do that is why I went solving those problems. (Its too bad that some require larger values than 32 bit integers can store..)

Regards

[Frank Kotler]

I have no idea how to pronounce Euler in other languages - I couldn't even do it in English without my baby sister's help! No matter, the CPU doesn't care how we pronounce it.

I'll look at your code. May take me a while (this place is "jumping" lately - great!). Remind me if I don't get back to you within a day or two. I don't think posting "too much" code is likely to be a problem (within some undefined limit). You seem to have figured out how to use "code tags", which helps.

I think it's "better" to keep values in registers... until we run out of registers, which happens fairly quickly. It is possible to "%define" a "meaningful name" to "ebp - ?". Possibly even easier than remembering what's in which register. I'll try to post an example...

Later,
Frank

[Frank Kotler]

Anyway I tried with this code, but it never complete (since it can fit the register or something, at first I thought it just took long )

Well, I out-stubborned ya, iVision. Your code, with slight modifications, does finally finish, and by golly it even prints out the number you mention in your original post! It takes a really long time - I went off and did other things.

I put a simple "test caller" on it (for Linux - you probably just want to delete it), I modified your code slightly in order to return a 64-bit number in edx:eax. As expected, edx was being used, so I put the high dword in esi temporarily and swapped it back into edx just before returning.

Code: [Select]

; pretend we did this, if you like...
;%ifdef TESTMAIN

global _start

section .bss
    buffer resb 80

section .text
_start:
    push 2000000
    call _sum_prime
    add esp, 4

    mov edi, buffer
    call u64toda
   
    mov ecx, buffer
    xor edx, edx
getlen:
    cmp byte [ecx + edx], 0
    jz gotlen
    inc edx
    jmp getlen
gotlen:
    mov ebx, 1
    mov eax, 4
    int 80h       

    mov ebx, eax
    mov eax, 1
    int 80h

;--------------------------------------------------------------
; u64toda - converts (64 bit) integer in edx:eax
; to (comma delimited) decimal representation in
; asciiz ( & "$") terminated string in buffer pointed to by edi
;-----------------------------------------------------------------
u64toda:
                pusha
                mov ebx, edx     ; stash high dword
                mov esi,0Ah      ; prepare to divide by 10
                xor ecx, ecx     ; zero the digit count
                jmp highleft     ; check is high word 0 ?
highword:
                xchg eax,ebx    ; swap high & low words
                xor edx,edx     ; zero edx for the divide!
                div esi         ; divide high word by 10
                xchg eax,ebx    ; swap 'em back
                div esi         ; divide low word including remainder
                push edx        ; remainder is our digit - save it
                inc ecx         ; count digits
highleft:
                or ebx,ebx
                jnz highword
lowleft:
                xor edx,edx          ; zero high word
                div esi              ; divide low word by 10
                push edx             ; our digit
                inc ecx              ; count it
                or eax,eax           ; 0 yet ?
                jne lowleft
                cmp ecx, byte 4      ; commas needed ?
                jl write2buf         ; nope
                xor edx,edx            ; zero high word for divide
                mov eax,ecx            ; number of digits
                mov ebx,3
                div ebx
                mov esi,edx            ; remainder = number digits before comma
                test edx,edx
                jnz write2buf        ; no remainder?
                mov esi,3             ; we can write 3 digits, then.
write2buf:
                pop eax              ; get digit back - in right order
                add al,30H           ; convert to ascii character
                stosb                ; write it to our buffer
                dec esi               ; digits before comma needed
                jnz moredigits       ; no comma needed yet
                cmp ecx,2             ; we at the end?
                jl moredigits        ; don't need comma
                mov al,','           ; write a comma
                stosb
                mov esi,03h           ; we're good for another 3 digits
moredigits:
                loop write2buf       ; write more digits - cx of 'em
                mov al,00h           ; terminate buffer with zero
                stosb
popa
                ret
;-------------------------------------------------------------

;endif ; (TESTMAIN)


; iVision's code
; Parameters: int max
; Description: find the sum of prime numbers under max
_sum_prime:
push ebp
mov ebp, esp

push ebx
; push edx ; I want to return edx
    push esi ; but we should preserve esi for C

    xor esi, esi ; high dword

mov ebx, dword 2
mov edx, dword 2
.do:
push ebx
call _next_prime

mov ebx, eax

cmp eax,[ ebp + 8]
jg .break

add edx, ebx
adc esi, 0 ; added code
jmp .do


.break:
mov eax, edx
mov edx, esi ; added code

pop esi
; pop edx
pop ebx

mov esp, ebp
pop ebp
ret
;_sum_prime


; Parameters: int prev_prime
; Description: get the next prime number, from prev_prime
_next_prime:
push ebp
mov ebp, esp

push ecx ; save ecx
mov ecx, [ebp + 8] ; ecx = prev_prime

.loop:
inc ecx

push ecx
call _is_prime ; is_prime(ecx)

test eax, eax
jne .break ; ecx is prime number, so break it

jmp .loop ; goto loop

.break:

mov eax, ecx ; store return value
pop ecx ; restore ecx

mov esp, ebp
pop ebp
ret
;_next_prime



; Parameters: int a
; Description: checks if number is a prime
_is_prime:
push ebp
mov ebp, esp

sub esp, 4

push edx ; saves register
mov edx, [ebp + 8] ; hold parameter in edx

mov [ebp - 4], dword 2 ; int i = 2

.for_loop:
push dword [ebp - 4]
push edx
call modulus

test eax, eax
je .test_prime

inc dword [ebp - 4] ; i++
cmp [ebp - 4], edx
jl .for_loop ; i < a

.test_prime:
cmp [ebp - 4], edx
jne .else ; if (i != num) goto else;
mov eax, 1 ; eax = 1 (true)
jmp .end ; goto end; (skip the else block)
.else:
mov eax, 0 ; eax = 0 (false)
.end:
pop edx ; remember to restore it!!

mov esp, ebp
pop ebp
ret 4
;_is_prime



; Parameters: int a, int b
; Description: returns a % b (the remainder)
modulus:
push ebp
mov ebp, esp

push ecx
push edx

xor edx, edx
mov eax, [ebp + 8] ;a
mov ecx, [ebp + 12] ;b

div ecx ;edx holds remainder (a % b)
mov eax, edx ;return remainder

pop edx
pop ecx

mov esp, ebp
pop ebp

ret 8
;modulus

As you see, I really didn't do much to it. I really don't think mixing "ret N" and "ret" is a good idea, although you've mostly done it right... except for one place. From _sum_primes you call next_prime with a parameter on the stack. next_prime ends with a plain "ret", and you don't do a "add esp, 4" (or pop some dummy register), so your stack grows and grows (down). In the "epilog" to sum_primes, the "mov esp, ebp" saves your "asm".

This can be made to run faster. You use every number from 2 up to N (our potential prime) as a "test divisor". There's no point in going past the square root of N - if you haven't found an even divisor by then, you're not going to. Further, there's no point in trying non-prime numbers as divisors - N would have been evenly divisible by its factors, and we'd already have rejected it. Do you know the "Seive of Erasthenes"? I don't, really. I think what it does is to keep a "list" of already-found primes, and uses them as "test divisors", skipping the non-primes. I'm no expert on fast prime-finding, but I know there are a lot of things that can be done to speed it up. With numbers up to two million, there are a lot of "wasted" divs in there. Well, the question didn't ask for fast, it just asked for the sum of primes under 2000000 and you've done that.

I'm really impressed, iVision! Now I'll go look at the rest of your code...

Best,
Frank

[iVision]

Anyway I tried with this code, but it never complete (since it can fit the register or something, at first I thought it just took long )

Well, I out-stubborned ya, iVision. Your code, with slight modifications, does finally finish, and by golly it even prints out the number you mention in your original post! It takes a really long time - I went off and did other things.

I put a simple "test caller" on it (for Linux - you probably just want to delete it), I modified your code slightly in order to return a 64-bit number in edx:eax. As expected, edx was being used, so I put the high dword in esi temporarily and swapped it back into edx just before returning.

Code: [Select]

; pretend we did this, if you like...
;%ifdef TESTMAIN

global _start

section .bss
    buffer resb 80

section .text
_start:
    push 2000000
    call _sum_prime
    add esp, 4

    mov edi, buffer
    call u64toda
   
    mov ecx, buffer
    xor edx, edx
getlen:
    cmp byte [ecx + edx], 0
    jz gotlen
    inc edx
    jmp getlen
gotlen:
    mov ebx, 1
    mov eax, 4
    int 80h       

    mov ebx, eax
    mov eax, 1
    int 80h

;--------------------------------------------------------------
; u64toda - converts (64 bit) integer in edx:eax
; to (comma delimited) decimal representation in
; asciiz ( & "$") terminated string in buffer pointed to by edi
;-----------------------------------------------------------------
u64toda:
                pusha
                mov ebx, edx     ; stash high dword
                mov esi,0Ah      ; prepare to divide by 10
                xor ecx, ecx     ; zero the digit count
                jmp highleft     ; check is high word 0 ?
highword:
                xchg eax,ebx    ; swap high & low words
                xor edx,edx     ; zero edx for the divide!
                div esi         ; divide high word by 10
                xchg eax,ebx    ; swap 'em back
                div esi         ; divide low word including remainder
                push edx        ; remainder is our digit - save it
                inc ecx         ; count digits
highleft:
                or ebx,ebx
                jnz highword
lowleft:
                xor edx,edx          ; zero high word
                div esi              ; divide low word by 10
                push edx             ; our digit
                inc ecx              ; count it
                or eax,eax           ; 0 yet ?
                jne lowleft
                cmp ecx, byte 4      ; commas needed ?
                jl write2buf         ; nope
                xor edx,edx            ; zero high word for divide
                mov eax,ecx            ; number of digits
                mov ebx,3
                div ebx
                mov esi,edx            ; remainder = number digits before comma
                test edx,edx
                jnz write2buf        ; no remainder?
                mov esi,3             ; we can write 3 digits, then.
write2buf:
                pop eax              ; get digit back - in right order
                add al,30H           ; convert to ascii character
                stosb                ; write it to our buffer
                dec esi               ; digits before comma needed
                jnz moredigits       ; no comma needed yet
                cmp ecx,2             ; we at the end?
                jl moredigits        ; don't need comma
                mov al,','           ; write a comma
                stosb
                mov esi,03h           ; we're good for another 3 digits
moredigits:
                loop write2buf       ; write more digits - cx of 'em
                mov al,00h           ; terminate buffer with zero
                stosb
popa
                ret
;-------------------------------------------------------------

;endif ; (TESTMAIN)


; iVision's code
; Parameters: int max
; Description: find the sum of prime numbers under max
_sum_prime:
push ebp
mov ebp, esp

push ebx
; push edx ; I want to return edx
    push esi ; but we should preserve esi for C

    xor esi, esi ; high dword

mov ebx, dword 2
mov edx, dword 2
.do:
push ebx
call _next_prime

mov ebx, eax

cmp eax,[ ebp + 8]
jg .break

add edx, ebx
adc esi, 0 ; added code
jmp .do


.break:
mov eax, edx
mov edx, esi ; added code

pop esi
; pop edx
pop ebx

mov esp, ebp
pop ebp
ret
;_sum_prime


; Parameters: int prev_prime
; Description: get the next prime number, from prev_prime
_next_prime:
push ebp
mov ebp, esp

push ecx ; save ecx
mov ecx, [ebp + 8] ; ecx = prev_prime

.loop:
inc ecx

push ecx
call _is_prime ; is_prime(ecx)

test eax, eax
jne .break ; ecx is prime number, so break it

jmp .loop ; goto loop

.break:

mov eax, ecx ; store return value
pop ecx ; restore ecx

mov esp, ebp
pop ebp
ret
;_next_prime



; Parameters: int a
; Description: checks if number is a prime
_is_prime:
push ebp
mov ebp, esp

sub esp, 4

push edx ; saves register
mov edx, [ebp + 8] ; hold parameter in edx

mov [ebp - 4], dword 2 ; int i = 2

.for_loop:
push dword [ebp - 4]
push edx
call modulus

test eax, eax
je .test_prime

inc dword [ebp - 4] ; i++
cmp [ebp - 4], edx
jl .for_loop ; i < a

.test_prime:
cmp [ebp - 4], edx
jne .else ; if (i != num) goto else;
mov eax, 1 ; eax = 1 (true)
jmp .end ; goto end; (skip the else block)
.else:
mov eax, 0 ; eax = 0 (false)
.end:
pop edx ; remember to restore it!!

mov esp, ebp
pop ebp
ret 4
;_is_prime



; Parameters: int a, int b
; Description: returns a % b (the remainder)
modulus:
push ebp
mov ebp, esp

push ecx
push edx

xor edx, edx
mov eax, [ebp + 8] ;a
mov ecx, [ebp + 12] ;b

div ecx ;edx holds remainder (a % b)
mov eax, edx ;return remainder

pop edx
pop ecx

mov esp, ebp
pop ebp

ret 8
;modulus

As you see, I really didn't do much to it. I really don't think mixing "ret N" and "ret" is a good idea, although you've mostly done it right... except for one place. From _sum_primes you call next_prime with a parameter on the stack. next_prime ends with a plain "ret", and you don't do a "add esp, 4" (or pop some dummy register), so your stack grows and grows (down). In the "epilog" to sum_primes, the "mov esp, ebp" saves your "asm".

This can be made to run faster. You use every number from 2 up to N (our potential prime) as a "test divisor". There's no point in going past the square root of N - if you haven't found an even divisor by then, you're not going to. Further, there's no point in trying non-prime numbers as divisors - N would have been evenly divisible by its factors, and we'd already have rejected it. Do you know the "Seive of Erasthenes"? I don't, really. I think what it does is to keep a "list" of already-found primes, and uses them as "test divisors", skipping the non-primes. I'm no expert on fast prime-finding, but I know there are a lot of things that can be done to speed it up. With numbers up to two million, there are a lot of "wasted" divs in there. Well, the question didn't ask for fast, it just asked for the sum of primes under 2000000 and you've done that.

I'm really impressed, iVision! Now I'll go look at the rest of your code...

Best,
Frank

Okay I just skip the first part of your modified code (since my entrypoint is a C program and not 100% in NASM). How exactly does adc work, just a wild guess: you use adc esi, 0 because you don't want to store a different number (that explains the 0) and then adds the cary (CF) into the esi register. (Does it just append the bit like in a shift operation?). So its stored in edx:esi at this point when the loop finishes you store the edx into eax, and the esi in edx so its now stored in eax:edx, and I suppose I can return this to a C function?

I never had to intention to mix ret N and ret, I forgot to add the 4, thanks for noticing!

Why the square root? Shouldn't we need the prime numbers higher then the square root of 2 million?

I'm really thankful that someone helps me learning assembly, so much thanks!:)
Regards

Side Question: Where can I find good documentation of an instruction? With an example would be nice, I now use this at least it has description of an instruction. But with an example or a more rookie-friendly would be nice!