### Author Topic: Large number (Project Euler #10)  (Read 8200 times)

#### iVision

• Jr. Member
• Posts: 22
##### Large number (Project Euler #10)
« 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)?

#### Frank Kotler

• NASM Developer
• Hero Member
• Posts: 2667
• Country:
##### Re: Large number (Project Euler #10)
« Reply #1 on: July 23, 2013, 05:14:39 PM »
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 digitshighleft:                or ebx,ebx                jnz highwordlowleft:                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 digitsmoredigits:                loop write2buf       ; write more digits - cx of 'em                mov al,00h           ; terminate buffer with zero                stosb popa                ret;-------------------------------------------------------------`
Best,
Frank

#### iVision

• Jr. Member
• Posts: 22
##### Re: Large number (Project Euler #10)
« Reply #2 on: July 23, 2013, 05:47:20 PM »
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 digitshighleft:                or ebx,ebx                jnz highwordlowleft:                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 digitsmoredigits:                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

#### Frank Kotler

• NASM Developer
• Hero Member
• Posts: 2667
• Country:
##### Re: Large number (Project Euler #10)
« Reply #3 on: July 23, 2013, 06:38:14 PM »
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

• Jr. Member
• Posts: 22
##### Re: Large number (Project Euler #10)
« Reply #4 on: July 23, 2013, 07:23:34 PM »
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

• NASM Developer
• Hero Member
• Posts: 2667
• Country:
##### Re: Large number (Project Euler #10)
« Reply #5 on: July 23, 2013, 08:41:51 PM »
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

• NASM Developer
• Hero Member
• Posts: 2667
• Country:
##### Re: Large number (Project Euler #10)
« Reply #6 on: July 24, 2013, 06:40:54 AM »
Quote
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 TESTMAINglobal _startsection .bss    buffer resb 80section .text_start:    push 2000000    call _sum_prime    add esp, 4    mov edi, buffer    call u64toda        mov ecx, buffer    xor edx, edxgetlen:    cmp byte [ecx + edx], 0    jz gotlen    inc edx    jmp getlengotlen:    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 digitshighleft:                or ebx,ebx                jnz highwordlowleft:                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 digitsmoredigits:                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

• Jr. Member
• Posts: 22
##### Re: Large number (Project Euler #10)
« Reply #7 on: July 24, 2013, 09:52:39 AM »
Quote
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 TESTMAINglobal _startsection .bss    buffer resb 80section .text_start:    push 2000000    call _sum_prime    add esp, 4    mov edi, buffer    call u64toda        mov ecx, buffer    xor edx, edxgetlen:    cmp byte [ecx + edx], 0    jz gotlen    inc edx    jmp getlengotlen:    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 digitshighleft:                or ebx,ebx                jnz highwordlowleft:                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 digitsmoredigits:                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!
« Last Edit: July 24, 2013, 09:56:49 AM by iVision »