Finding prime numbers

[arsenalftw067]

I have an array of size 100, where each index contains elements ranging from 0 - 100. My job is to find all the prime numbers in this array, and print them out.

So I first need to populate this array, but starting at the value of 2 not 0. Then my program goes through this newly populated array with values starting from 2 to 100, and it will take the first value (so in this  case 2) and do a modulus operation on all the elements in the array.

for example, the first element is 2

3 % 2, 4 %2, 5 % 2, etc

if the remainder is not 0, then this means that it is a prime number and it will store this number in the new array


I have a problem where my code reaches an unhandled exception! and I don't know why

Code Select Expand


TITLE PrimeNumber (Prime.asm)

; This program finds prime numbers under 100

INCLUDE Irvine32.inc ; new
includelib C:\Irvine\Kernel32
includelib C:\Irvine\User32
includelib C:\Irvine\Irvine32

.data
array DWORD 100 DUP (?) ;array of 100
newarray DWORD 100 DUP (?) ; new array to hold prime
size = ($-array)/4 - 2
counter DWORD 2 ; to start population at 2 not 0
count DWORD 0
.code
main PROC
mov esi, OFFSET array
mov edi, OFFSET newarray
mov ecx, size
call PopulateArray ; populate array from 0 - 100
call Prime
call Showarray

main ENDP

PopulateArray PROC ;this proc will populate the array
push esi ; saving the pointer
push ecx ; saving the counter
mov eax, counter
L1:
mov [esi], eax; start populating array
inc esi ; move pointer to next element
inc eax ; eax equals next integer value
loop L1

pop ecx
pop esi

ret
PopulateArray ENDP

Prime PROC
push edi

L1:
push esi
mov ebx, [esi] ; eax holds array element
cmp ebx, count
JE nothing ; if the value is 0
mov ecx, size
L2:
inc esi
mov eax , [esi]
div ebx
cmp edx, count ;see if remainder is zero
JE notprime
JG Isprime
loop L2

pop esi
inc esi
loop L1

nothing:
pop esi
inc esi ; point to next element
loop L1

notprime:
loop L2

Isprime:
mov [edi], eax
inc edi
loop L2

ret
Prime ENDP

ShowArray PROC
pop edi
mov edi, OFFSET newarray
mov ecx, LENGTHOF newarray
mov ebx, TYPE newarray
call DumpMem
ret
ShowArray ENDP

END main


[dedndave]

the Prime function has an unbalanced stack
be careful how you push and pop esi
and - there is no pop edi at the end

[arsenalftw067]

What do you mean its unbalanced? So I am performing my push and pop incorrectly?

[dedndave]

that's right

for esi.....
you push at the top of the loop
then, the flow has conditional branches
i didn't really spend much time examining this code, but i would make sure there is always 1 pop for each push
it's a common mistake

edi is simple - at the beginning of the routine, you push edi
but, there is no associated pop to restore edi

when the ret is executed, it gets the address from the stack
so, if the stack is not balanced, execution may attempt to branch to an illegal address
that's probably what causes the exception

[arsenalftw067]

I can't find out where I did my pops wrong in the PRIME function

First I pushed edi

Then, in my first loop I push esi, and the program beginnings the 2nd loop. Once the 2nd loop is completely done, I pop esi, inc esi, then push it back by iterating through the first loop again.


Where did I go wrong?

Code Select Expand


Prime PROC
push edi

L1:
push esi
mov ebx, [esi] ; eax holds array element
cmp ebx, count
JE nothing ; if the value is 0
mov ecx, size
L2:
inc esi
mov eax , [esi]
div ebx
cmp edx, count ;see if remainder is zero
JE notprime
JG Isprime
loop L2

pop esi
inc esi
loop L1

nothing:
pop esi
inc esi ; point to next element
loop L1

notprime:
loop L2

Isprime:
mov [edi], eax
inc edi
loop L2

pop edi
ret
Prime ENDP


[dedndave]

it's the LOOP instruction that seems to be messing you up   

LOOP branches until ECX becomes 0
when ECX is 1, then LOOP is executed, ECX becomes 0
at that point, execution "falls through" to the instruction following LOOP

Code Select Expand

loop L1

nothing:
pop esi
inc esi ; point to next element
loop L1

notprime:
loop L2

Isprime:
mov [edi], eax
inc edi
loop L2

pop edi

the first "loop L1" falls through to the "nothing:" code when ECX becomes 0
the second "loop L1" falls through to to the "notprime:" code when ECX becomes 0
the first "loop L2" falls through to the "Isprime:" code when ECX becomes 0
the second "loop L2" falls through to the "pop edi" code when ECX becomes 0

if i'm not mistaken, this causes additional "pop esi" s to be executed   :P

worst of all....
the second "loop L1" falls through to a "loop L2", with ECX = 0
when that happens, ECX becomes 0FFFFFFFFh - and L2 has a very long count

[dedndave]

once you get all that sorted.....

a simpler way to do primes is to use the Sieve of Eratosthenes

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

to begin with, there is no sense in even storing even numbers - the only even prime is 2   

so, you can start with an array from 3 to 99, odd values only
and - you only have to take out odd multiples up to SQR(100) = 10
and - only values that haven't already been cleared out need to be tested

3 is still in the array, so clear out values that are multiples of 3 (except 3)
5 is still in the array, so clear out values that are multiples of 5 (except 5)
7 is still in the array, so clear out values that are multiples of 7 (except 7)
9 is no longer in the array because it is a multiple of 3 - no need to do that one

bang ! - you're done   :t

your code has to know that 1 and 2 are primes, even though they are not in the array

[nidud]

deleted

[arsenalftw067]

why would the size be 198?

The array is 4 bytes so you divide it by 4 and since I want it to start at 2, I subtract 2

@dedbdave

whaat? when my loop 2 is finished, it should pop esi, inc esi, and loop 1 again, why would it fall through to nothing?

Code Select Expand


L2:
inc esi
mov eax , [esi]
div ebx
cmp edx, count ;see if remainder is zero
JE notprime
JG Isprime
loop L2

pop esi
inc esi
loop L1


isn't this code saying that once we go through loop 2, it will pop esi inc esi and loop L1??


Yes! that is the method I am trying to do! So the logic would be:

Start at 2, and every 2nd digit put a 0, then if the next number is NOT 0 then for every x digit put a 0, and whatever numbers are remaining, they are all prime right?

I don't understand what you mean by "and - you only have to take out odd multiples up to SQR(100) = 10"

[dedndave]

you can create the array however you like
i can tell you that, to find large primes, only odd values are stored
this divides the space required by 2 - bang
the code used to retrieve or test primes "knows" that 1 and 2 are primes, and not in the array

also - most prime sieves use individual bits to represent each numeric value
that's ok - i can understand not doing that for purposes of learning

let's take an array from 3 to 30, to demonstrate the principal of Eratosthenes....

Code Select Expand

MyArray db 3,5,7,9,11,13,15,17,19,21,23,25,27,29

the max test value is squareroot(30) = 5.4 (we can stop after test value = 5)
on the first pass, we are going to start with a test value of 3:

start:
test to see if 3 is still in the array - if it were not, we could skip this test value
it is, so we process it....
we leave the 3 in place, because it is a prime
adding 3 gives us an even number, so we can skip it
adding 3 again gives us 9 - we clear 9 from the array (not a prime)
add 6 (skip all even values), gives us 15 - we clear 15 from the array
add 6, gives us 21 - we clear 21 from the array
add 6, gives us 27 - we clear 27 from the array
add 6, greater than 30, so we process the next test value which is 5 - i.e. go to start

to find all primes up to 100, you only have to process test values up to squareroot(100)
that's because all multiples above 10 will already be crossed out if needed

11, for example - 11 will not be cleared out because it is a prime
but, 22, 33, 44, 55, 66, 77, 88, and 99 are already cleared or otherwise not present in the array
22, 44, 66, 88 are even - so they do not exist in the array
33 and 99 are multiples of 3, so they will already be cleared
55 is a multiple of 5, so it will already be cleared
77 is a multiple of 7, so it will already be cleared

[arsenalftw067]

Ah yes awesome explanation! I kind of have a grip on it

So if I have an array of 100, and I am finding the prime, does my ecx counter = 10? Since the sqrt(100) = 10? So I would only have to iterate the loop 10 times?

let me get this straight...

so the first value in the array is 2, I iterate the loop where I add 2 to my esi counter (pointer to array), so now esi points to 4, and I change this value to 0? so it would now look like: 2, 3, 0, 5, 0, 7, 0, 9, 0....

Then my loop iterates again, ecx gets decremented to 9 (or does ecx get incremented? I forgot where ecx starts at, the size of the array or at 0 TO the size of the array?), and it moves to the next value which is 3..

Then the loop iterates by adding 3 to the esi counter, so now esi points to 6, but 6 is removed so it will add 3 again, so now esi points to 9, it will change 9 to 0, then add 3 again etc, so now the array looks like: 2, 3, 0, 5, 0, 7, 0, 0, 0, 11, 0, etc...

Am I getting the logic correct?

[dedndave]

again, i will say that even values are not normally stored in the array
this reduces the size of the array by a factor of 2
if we were doing a large array, that means that what would require 1 GB only requires 512 MB 
at the end of the day, this isn't about storage space, it's about range using available memory

as for the "loop count"...
ok, you don't really know how many passes to make   
what you do is "loop until the test value exceeds the squareroot of the array max value"
if you don't have the capacity to find the squareroot,
you can square the current test value very easily, and test that against the array max value
(squareroots are fairly easy using the FPU instructions, though)

so the first value in the array is 2, I iterate the loop where I add 2 to my esi counter (pointer to array), so now esi points to 4, and I change this value to 0? so it would now look like: 2, 3, 0, 5, 0, 7, 0, 9, 0....

this is essentially correct, although i wouldn't do even numbers   :P

[nidud]

deleted