NASM - The Netwide Assembler
NASM Forum => Programming with NASM => Topic started by: iVision on July 23, 2013, 03:47:20 PM
-
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
-
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:
;--------------------------------------------------------------
; 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
-
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:
;--------------------------------------------------------------
; 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:)
-
Well, in general, once you've got a new value:
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
-
Well, in general, once you've got a new value:
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 :P
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 :P)
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 :P)
; 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 :P 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
-
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
-
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 :P)
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.
; 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
-
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 :P)
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.
; 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 (http://faydoc.tripod.com/cpu/add.htm) at least it has description of an instruction. But with an example or a more rookie-friendly would be nice!