Prime Number Testing.. me again =)

[gusto]

as promised, new project lol... well im testing for prime numbers, prof. gave us a rough idea of how to do it, and im tryin to work it out, but im getting an error code display: 'Divide overflow' in ms-dos... below is my code.. i jus started workin on it, let me kno if im the right track and if im using the correct calls.... x is the number im testing. . . thanks in advanced

Code Select Expand

include \masm615\include\irvine16.inc


.data
x  dword  8
z  dword  2
k  dword  3

intro  byte  "Testing for Prime Numbers.",0

.code
main  proc

startup
mov  edx,offset intro
call  writestring
call  crlf
call  crlf



test1:        mov  eax,x
div  z
cmp  edx,0
jne  test2


ifprime:      call  writedec
call  crlf
exit


test2:        div  k
cmp  edx,0
je  ifprime


exit
main        endp
end  main



is my error coming from test1? im more concerned with that part of the program first... thanks again

[raymond]

The div (and idiv) instruction by an 8/16/32-bit number is performed on a 16/32/64-bit number.

For the 8-bit, the content of the AX register is divided.
For the 16-bit, the content of the DX:AX pair is divided.
For the 32-bit, the content of the EDX:EAX pair is divided.

If your divisor is smaller than the content of AH/DX/EDX, your program will crash due to a "divide overflow".

Raymond

[gusto]

so what exactly do i need to change on that line? prof. also said the number u are to divide (my 'x') has to be a double word . . .

[raymond]

In your case, you make sure that the EDX register is 0, such as:

Code Select Expand

mov  eax,x
xor  edx,edx
div  z

Raymond

[gusto]

thanks ray, that helped me with my first test, now im testing my initial value againts odd numbers(k, then i have -add k,2- so it goes to 5, 7, 9, 11, 13, 15, etc...) to see if they are divisible by them.. no matter wat i put in x, i keep getting that it is not prime.. little help with test2, or if u see something else wrong please let me kno anyone, thanks ..

Code Select Expand

include \masm615\include\irvine16.inc


.data
x    dword    5
z    dword    2
k    dword    3

intro    byte    "Testing for Prime Numbers.",0
itisnot    byte    " Is a not a Prime Number.",0
itis    byte    " Is a Prime Number.",0

.code
main    proc

startup
mov    edx,offset intro
call    writestring
call    crlf
call    crlf
mov    ecx,5


test1:        mov    eax,x
xor    edx,edx
div    z
cmp    edx,0
jne    test2


ifnotprime:        mov    eax,x
call    writedec
mov    edx,offset itisnot
call    writestring
call    crlf
exit


test2:        mov    eax,x
xor    edx,edx
div    k
cmp    edx,0
je    ifnotprime
add    k,2
loop    test2
mov    eax,x
call    writedec
mov    edx,offset itis
call    writestring
call    crlf


exit
main    endp
end    main


[raymond]

From your description of what you are trying to do, the number which you want to test if it is prime or not is in "x". That is the number which you should be incrementing (and not your divisor).

Your code keeps the value of "x" constant at 5 and increments the value of "k". Simply run your code with pencil and paper and see what happens. :eek

Raymond

[gusto]

im tryin to divide my x by k, then k+2, k+2+2, etc... such that if my x is 7.. and my k starts at 3, itl then make k 5, then 7.. how can i go about writing if k = x then x is prime? i can do all this in C, but not in assebler  :( . . . ugh i hate having a hard time with this  :dazzled:

[raymond]

First of all, you don't have to test until x=z. Its a major waste of time.

For example, if you want to know if 101 is prime, you would only need to divide it until z=11. From that point on, the quotient would ALWAYS be smaller than the divisor and there would ALWAYS be a remainder until you would reach dividing by 101. Stopping after z=11 would require only 5 divisions in the test2 loop instead of 49 divisions if you test until z=101.

Therefore, after each division where you get a remainder, compare the quotient to the divisor and exit the loop as soon as it becomes smaller with proof that it is a prime. Since the quotient of a division is in the EAX register, and the divisor in your code is "z", you can add the following after checking if the EDX register is equal to 0 in your test2 loop:

Code Select Expand

cmp eax,z
jb  itisprime

and add the label "itisprime:" to the section where you display the message that the number is prime.

Raymond

[gusto]

cool ima check it out as soon as i get home.. also how can i exit my program if x is = 1 without using .if statements? thanks again, ill repost after i test what u put =)

[gusto]

i love you ray  :U, its working good so far, im just missing the when x = 1 then exit , part of my code...i kno i need a section after the startup part of my proc, but how can i do it without using .if ?

[raymond]

.if is only a "high level" construct which gets replaced by a comparison and jump(s) based on the result of that comparison. However, using the .if/.endif pair generally makes your code more legible and easier to follow. Unless you are one of those "purists", don't hesitate to use it. The following snippets will result in about the same code with MASM:

Code Select Expand

.if x == 1
   jmp x_is_1
.endif

Code Select Expand

cmp x,1
jz  x_is_1

Then code whatever you need for the x_is_1 section.

N.B. you should also do something similar for x=2 and x=3, otherwise they may be treated as not prime.

Raymond

[gusto]

cool, i got it working the way i need it to, thanks alot Ray... il post my finished code 2morro, maybe u can find a way to make it more efficient  :U

[gusto]

here it is.. thanks alot ray... i got another project coming soon lol  :dance:

Code Select Expand

include \masm615\include\irvine16.inc


  .data
x  dword  1
z  dword  2
k  dword  3

intro  byte  "Testing for prime numbers.",0
itisnot  byte  "The number ",0
itisnot2  byte  " has the factor ",0
itis  byte  " is a prime number",0

  .code
  main  proc

  startup
  cmp  x,1
  jz  x_is_1
  mov  edx,offset intro
  call  writestring
  call  crlf
  call  crlf
  cmp x,3
  jz  x_is_3
  mov  ecx,99999




test1:  mov  eax,x
  xor  edx,edx
  div  z
  cmp  edx,0
  je  ifnotprime1
  jmp  test2

ifnotprime1:  mov  edx,offset itisnot
  call  writestring
  mov  eax,x 
  call  writedec
  mov  edx,offset itisnot2
  call  writestring
  mov  eax,z
  call  writedec
  call  crlf
  exit

ifnotprime: mov  edx,offset itisnot
  call  writestring
  mov  eax,x 
  call  writedec
  mov  edx,offset itisnot2
  call  writestring
  mov  eax,k
  call  writedec
  call  crlf
  exit

itisprime:  mov  eax,x
  call  writedec
  mov  edx,offset itis
  call  writestring
  call  crlf
  exit

test2:  mov  eax,x
  xor  edx,edx
  div  k
  cmp  edx,0
  je  ifnotprime
  cmp  eax,z
  jb  itisprime
  add  k,2
  loop  test2


x_is_3:  jp  itisprime
x_is_1:  exit


  exit
main  endp
  end  main


[raymond]

Two comments.

a)  A binary number is even (divisible by 2) whenever the least significant bit (bit#0) is 0. It is odd when that same bit is 1. Thus, instead of dividing by 2 to test if a number is even, you can simply test if the least significant bit is 0 or 1, i.e.

Code Select Expand

test al,1   ;no need to test the entire 32 bits of EAX
jz   is_even

b)  In your test2 loop, you can exit when the quotient gets smaller than the current divisor (i.e. k) instead of exiting when the quotient gets lower than 2.

Code Select Expand

cmp  eax,k
jb   itisprime

Raymond