1

I am trying to check if a given number is prime or not in 8086 Assembly program using Turbo Assembler. But maybe there is something wrong in my code, for some of the prime numbers(19,23,31,37) its showing its not a prime number. Rest of the prime numbers(2,3,5,7,11,17,29,41,...,71) are working well.

Here's the whole code:

DATA SEGMENT
NUM DB 37H
PR DB 0H
NPR DB 0H
DATA ENDS

CODE SEGMENT
START: ASSUME CS:CODE, DS:DATA
MOV AX, DATA
MOV DS, AX
MOV AL, NUM
MOV BL, 02H
MOV BH,00H
MOV DX,0000H
MOV AH,00H

UP:DIV BL 
CMP AH,00H
JNE NEXT
INC BH
NEXT: CMP BH, 02H
JE NPRIME
INC BL
MOV AX, 0000H
MOV DX, 0000H
MOV AL, NUM
CMP BL, NUM
JBE UP

PRIME: 
INC PR
JMP EXIT

NPRIME: 
INC NPR

EXIT:
MOV AH, 4CH
INT 21H

CODE ENDS
END START

Maybe the problem must be in this part?

UP:DIV BL 
CMP AH,00H
JNE NEXT
INC BH
NEXT: CMP BH, 02H
JE NPRIME
INC BL
MOV AX, 0000H
MOV DX, 0000H
MOV AL, NUM
CMP BL, NUM
JBE UP

Please let me know where I am going wrong, Thanks in advance!

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Tanay Chawda
  • 13
  • 1
  • 6
  • When you single-step the inner loop for those problem cases in your debugger, what do you see? What did it divide to get a zero remainder? (You tagged this emu8086, which has a debugger built-in. But you also tagged TASM, which is a separate assembler you might use in dosbox, so you'd need a separate debugger.) – Peter Cordes Apr 11 '22 at 18:38
  • @PeterCordes AX was 0023 and BX was 0005 at that time it had zero remainder, so BH got incremented and then I got remainder zero again after getting 0023 divided by 07. So is my method wrong? and is it possible to get correct results using the method I used (Sorry I m pretty new in this stuffs so I didn't knew what to tag) (I deleted my previous comment because it wasn't phrased well) – Tanay Chawda Apr 11 '22 at 19:42
  • 1
    Why are you doing `CMP BH, 02H` / `JE NPRIME` at all? The logic is non-obvious, and you didn't comment it. After checking all divisors from 2 to `n-1` (or better just up to sqrt(n)), you know that `n` is prime. One trick for detecting that you've passed `sqrt(n)` is by checking the quotient and divisor, as shown in my answer on [Checking if a number is prime in NASM Win64 Assembly](https://codereview.stackexchange.com/q/204902) – Peter Cordes Apr 11 '22 at 19:43
  • Also note that 23h (0x23) is *not* prime. That's 35 (decimal), so it is divisible by 5 and 7. The prime number `23` (decimal) is `0017h`. – Peter Cordes Apr 11 '22 at 19:47
  • @PeterCordes Ah I get it now!! Thanks buddy! maybe that's why I was getting wrong, I was thinking 23 as Dec 23 this whole time – Tanay Chawda Apr 11 '22 at 19:48

1 Answers1

2

I have tried your program and it works fine except that you seem to consider 0 and 1 prime numbers. That's not correct.

A prime number is a number bigger than 1, that is only divisible by itself and by 1.

The quick fix is below:

...
MOV AL, NUM
cmp al, 2           <<<< Add this line
jb  NPRIME          <<<< Add this line
MOV BL, 02H
MOV BH,00H
MOV DX,0000H
MOV AH,00H

UP:DIV BL 
CMP AH,00H
JNE NEXT
INC BH
NEXT: CMP BH, 02H
JE NPRIME
INC BL
MOV AX, 0000H
MOV DX, 0000H
MOV AL, NUM
CMP BL, NUM
JBE UP

PRIME: 
INC PR
JMP EXIT

NPRIME: 
INC NPR

EXIT:
...

Not much of an answer if I would leave it at that! So allow me the following observations:

  • Zeroing DX is a twice repeated, redundant operation
  • You can load BH and BL in one operation
  • Don't load the number at two different places
  • The variables PR and NPR are mutually exclusive, so a single variable would be enough
  • You don't need branching in order to increment the counter

The better fix is below:

  ...
  cmp  NUM, 2
  jb   NPRIME    ; 0 and 1 are no prime numbers
  mov  bx, 0002h ; BH=0 (counter), BL=2 (divisor)
UP:
  mov  al, NUM
  mov  ah, 0
  div  bl
  cmp  ah, 1     ; Only sets carry flag is remainder is 0
  adc  bh, 0     ; Conditional increment of counter
  cmp  bh, 2
  je   NPRIME
  inc  bl
  cmp  bl, NUM
  jbe  UP
PRIME: 
  inc  PR
NPRIME: 
EXIT:
...

Because your algorithm tries every divisor up to the number itself, even the above proposed changes will not make the program truly efficient.
I could add a version of the code that would be at least 10 times faster. In case you're interested, leave me a comment and perhaps I could add it in the weekend...

[edit]

A fast check for primality

Trying to reduce the number of iterations and especially the number of divisions (div is a costly operation) is what we're after here:

  • It is most efficient to split off the small numbers [0,3] first. This avoids extra tests in the loop.
  • Next we split off the even numbers because, except for the number 2 (that we already have split off), no even number is prime.
  • Therefore the loop only has to divide odd numbers. We can omit all the even divisors at once because dividing an odd number by an even number will never produce a zero remainder.
  • We only need to test divisors up to the integer square root of the number. Luckily we don't need to calculate it. As long as the quotient from the division is still greater than the divisor we have not yet reached the integer square root.
; IN (dl) OUT (cx) MOD (ax,bl)
TestPrime:
  xor  cx, cx         ; CX=0 means NotPrime
  cmp  dl, 4
  jb   .Less4
  mov  bl, 1
  test dl, bl
  jz   .No            ; Number is EVEN, so not prime
  ; Remaining candidates {5,7,9,11,13,15,...}
.Loop:
  add  bl, 2          ; Division by {3,5,7,9,11,....}
  mov  al, dl
  mov  ah, 0          ; Will divide AX by BL
  div  bl
  test ah, ah         ; Remainder == 0 ?
  jz   .No            ; Yes, found an additional divisor, so not prime
  cmp  al, bl         ; Quotient > divisor ?
  ja   .Loop          ; Yes, continue up to isqrt(number)
.Yes:
  inc  cx             ; CX=1 means Prime
  ret
.Less4:
  cmp  dl, 2
  jae  .Yes           ; 2 and 3 are prime, 0 and 1 are not prime
.No:
  ret

Prime numbers smaller than 256

Next table shows the number of DIV instructions that got executed and the time it took in nanoseconds. The middle columns are for the question's improved code, and the columns on the right are for today's optimized code. As numbers grow, so does the benefit.

Number IsPrime DIV's nsec DIV's nsec
251 1 250 4163 8 495
241 1 240 4140 8 428
239 1 238 3967 7 285
233 1 232 3869 7 263
229 1 228 3809 7 285
227 1 226 3779 7 255
223 1 222 3697 7 263
211 1 210 3494 7 255
199 1 198 3298 7 263
197 1 196 3276 7 263
193 1 192 3298 7 263
191 1 190 3186 7 263
181 1 180 3020 6 315
179 1 178 2990 6 308
173 1 172 2900 6 285
167 1 166 2802 6 232
163 1 162 2742 6 232
157 1 156 2667 6 240
151 1 150 2637 6 240
149 1 148 2524 6 240
139 1 138 2382 6 240
137 1 136 2352 6 240
131 1 130 2254 5 285
127 1 126 2171 5 293
113 1 112 1946 5 255
109 1 108 1893 5 225
107 1 106 1871 5 225
103 1 102 1848 5 210
101 1 100 1750 5 225
97 1 96 1713 5 225
89 1 88 1555 4 270
83 1 82 1457 4 270
79 1 78 1465 4 240
73 1 72 1390 4 195
71 1 70 1284 4 202
67 1 66 1202 4 210
61 1 60 1209 4 195
59 1 58 1082 4 195
53 1 52 976 3 255
47 1 46 871 3 263
43 1 42 804 3 180
41 1 40 773 3 187
37 1 36 728 3 172
31 1 30 616 3 180
29 1 28 601 2 225
23 1 22 510 2 232
19 1 18 435 2 172
17 1 16 413 2 172
13 1 12 360 2 172
11 1 10 315 1 217
7 1 6 247 1 142
5 1 4 217 1 150
3 1 2 187 0 165
2 1 1 172 0 165

Non prime numbers smaller than 256

Next table shows the number of DIV instructions that got executed and the time it took in nanoseconds. The middle columns are for the question's improved code, and the columns on the right are for today's optimized code. As numbers grow, so does the benefit.

Number IsPrime DIV's nsec DIV's nsec
255 0 4 270 1 195
254 0 126 2261 0 202
253 0 22 518 5 345
252 0 2 202 0 180
250 0 4 285 0 142
249 0 82 1532 1 217
248 0 3 240 0 150
247 0 18 510 6 345
246 0 2 210 0 165
245 0 6 270 2 232
244 0 3 255 0 165
243 0 8 338 1 217
242 0 10 375 0 180
240 0 2 217 0 157
238 0 6 360 0 142
237 0 78 1442 1 187
236 0 3 240 0 142
235 0 46 916 2 232
234 0 2 210 0 157
232 0 3 180 0 157
231 0 6 270 1 187
230 0 4 247 0 142
228 0 2 210 0 150
226 0 112 2066 0 142
225 0 4 247 1 195
224 0 3 240 0 142
222 0 2 217 0 150
221 0 16 435 6 338
220 0 3 240 0 150
219 0 72 1352 1 225
218 0 108 1931 0 142
217 0 30 646 3 278
216 0 2 210 0 157
215 0 42 924 2 232
214 0 106 1893 0 165
213 0 70 1322 1 217
212 0 3 240 0 157
210 0 2 165 0 150
209 0 18 488 5 323
208 0 3 270 0 165
207 0 8 255 1 217
206 0 102 1893 0 165
205 0 40 811 2 202
204 0 2 210 0 165
203 0 28 631 3 278
202 0 100 1795 0 165
201 0 66 1254 1 217
200 0 3 240 0 165
198 0 2 165 0 150
196 0 3 232 0 142
195 0 4 240 1 187
194 0 96 1750 0 142
192 0 2 165 0 150
190 0 4 315 0 142
189 0 6 270 1 195
188 0 3 255 0 142
187 0 16 428 5 308
186 0 2 202 0 142
185 0 36 804 2 232
184 0 3 240 0 165
183 0 60 1142 1 225
182 0 6 270 0 157
180 0 2 165 0 157
178 0 88 1720 0 142
177 0 58 1134 1 187
176 0 3 240 0 150
175 0 6 270 2 232
174 0 2 210 0 180
172 0 3 240 0 157
171 0 8 300 1 187
170 0 4 247 0 150
169 0 168 2938 6 345
168 0 2 210 0 165
166 0 82 1540 0 142
165 0 4 240 1 240
164 0 3 232 0 150
162 0 2 157 0 150
161 0 22 510 3 278
160 0 3 247 0 157
159 0 52 1014 1 187
158 0 78 1442 0 142
156 0 2 165 0 142
155 0 30 646 2 263
154 0 6 270 0 150
153 0 8 375 1 187
152 0 3 247 0 157
150 0 2 210 0 150
148 0 3 270 0 150
147 0 6 270 1 202
146 0 72 1352 0 150
145 0 28 631 2 232
144 0 2 202 0 157
143 0 12 390 5 308
142 0 70 1375 0 165
141 0 46 916 1 225
140 0 3 240 0 165
138 0 2 165 0 195
136 0 3 232 0 150
135 0 4 247 1 195
134 0 66 1247 0 142
133 0 18 488 3 308
132 0 2 165 0 172
130 0 4 247 0 187
129 0 42 879 1 195
128 0 3 240 0 165
126 0 2 165 0 142
125 0 24 556 2 263
124 0 3 240 0 165
123 0 40 811 1 150
122 0 60 1209 0 142
121 0 120 2134 5 308
120 0 2 210 0 142
119 0 16 473 3 278
118 0 58 1127 0 165
117 0 8 300 1 202
116 0 3 247 0 172
115 0 22 556 2 270
114 0 2 210 0 165
112 0 3 240 0 150
111 0 36 758 1 187
110 0 4 240 0 157
108 0 2 165 0 150
106 0 52 1097 0 150
105 0 4 240 1 202
104 0 3 240 0 150
102 0 2 165 0 142
100 0 3 232 0 157
99 0 8 300 1 165
98 0 6 270 0 165
96 0 2 165 0 142
95 0 18 488 2 217
94 0 46 1036 0 150
93 0 30 646 1 195
92 0 3 240 0 157
91 0 12 390 3 308
90 0 2 210 0 180
88 0 3 232 0 187
87 0 28 631 1 187
86 0 42 871 0 142
85 0 16 428 2 232
84 0 2 210 0 180
82 0 40 819 0 157
81 0 8 293 1 202
80 0 3 232 0 142
78 0 2 210 0 157
77 0 10 323 3 278
76 0 3 232 0 142
75 0 4 240 1 150
74 0 36 758 0 150
72 0 2 165 0 142
70 0 4 315 0 142
69 0 22 518 1 187
68 0 3 240 0 142
66 0 2 165 0 142
65 0 12 390 2 232
64 0 3 240 0 142
63 0 6 270 1 150
62 0 30 646 0 150
60 0 2 165 0 150
58 0 28 751 0 142
57 0 18 488 1 195
56 0 3 270 0 165
55 0 10 368 2 232
54 0 2 202 0 180
52 0 3 240 0 157
51 0 16 428 1 195
50 0 4 240 0 142
49 0 48 1044 3 270
48 0 2 210 0 165
46 0 22 593 0 157
45 0 4 240 1 187
44 0 3 240 0 165
42 0 2 202 0 142
40 0 3 270 0 142
39 0 12 398 1 187
38 0 18 488 0 142
36 0 2 210 0 150
35 0 6 270 2 247
34 0 16 420 0 150
33 0 10 323 1 187
32 0 3 232 0 142
30 0 2 202 0 150
28 0 3 263 0 165
27 0 8 293 1 195
26 0 12 465 0 142
25 0 24 563 2 232
24 0 2 210 0 142
22 0 10 323 0 150
21 0 6 270 1 202
20 0 3 232 0 150
18 0 2 225 0 150
16 0 3 232 0 157
15 0 4 232 1 187
14 0 6 263 0 142
12 0 2 217 0 157
10 0 4 315 0 157
9 0 8 308 1 217
8 0 3 247 0 150
6 0 2 217 0 142
4 0 3 240 0 165
1 0 0 165 0 187
0 0 0 157 0 187
Sep Roland
  • 33,889
  • 7
  • 43
  • 76
  • 1
    There were lot of redundancy in my code but I fixed it from your observations, Thank You very much for your help! (And for now I could only think of this algorithm so it might not be very efficient) – Tanay Chawda Apr 16 '22 at 09:02
  • 1
    @TanayChawda The optimized code that I promised has been added to the answer. Please check it out. – Sep Roland Apr 17 '22 at 15:06
  • 1
    Your CPU is a Pentium-M or something, IIRC. It should avoid a partial-register stall to do `xor ax,ax` / `mov al, dl` instead of writing AH by itself, assuming `div r/m8` reads AX as a whole, not two 8-bit halves. On P6-family before Core 2, a partial register stall costs at least 7 cycles in the front-end. (I wonder how much of that can overlap with the back-end div throughput...) Even better would be `xor eax,eax` / `mov al,dl` or `movzx ax, dl` (or better EAX), but Pentium-M is old enough that it might still handle 16-bit zeroing idioms. – Peter Cordes Feb 28 '23 at 04:00
  • Avoiding writing AH by itself is [also better for modern Intel (Sandybridge-family)](https://stackoverflow.com/questions/45660139/how-exactly-do-partial-registers-on-haswell-skylake-perform-writing-al-seems-to). There you'll have a false dependency for writing AL or AX (unavoidable unless you write the full EAX), but you won't have any extra partial-register merging delays if you never write to AH except as part of AX/EAX. (Of course this is for running natively, not running emu8086 interpreting this code.) – Peter Cordes Feb 28 '23 at 04:02
  • Avoiding a false dependency would be quite nice on newer CPUs where `div` is pipelined with throughput significant better than latency. AMD and other CPUs that don't rename partial registers at all treat partial-register write as RMW operations on the full register, so the old value of EAX is an input to `mov ah,0`. – Peter Cordes Feb 28 '23 at 04:05