Prime Number Program

[veronicak5678]

I wrote the following code as instructed by my teacher using his algorithm. He told us it would produce a distinct pattern, and that we should be able to change a few lines in it to make it produce a list of prime numbers.
The distinct pattern turns out to be squares (1, 4, 9, 16, ...) I can't figure out what to change to produce prime. Any ideas?

Code Select Expand

;===================================================================
         EXTERN  NEWLINE:FAR
         EXTERN  PUTDEC:FAR
         EXTERN  putstrng:FAR
;===================================================================
INCLUDE PCMAC.INC
.MODEL  SMALL
.586
        .STACK  512
        .DATA
CUPS DB 500 DUP (0)
CUP DB 0
X DW 1
Y DW 1
Z DW 0       
;---------------------------------
.CODE
MARBLES   PROC
        MOV     AX,DGROUP           ;SET DS-REGISTER TO POINT TO
        MOV     DS,AX               ;DATA SEGMENT
        MOV     ES,AX   
XLOOP:
MOV CX, 500
CMP X, CX
JGE XDONE
MOV CX, X
MOV Y, CX
YLOOP:
MOV CX,500 
CMP Y, CX
JGE YDONE ;STOP WHEN X > 500
DEC Y ; ELEMENT 0
MOV DI,Y
CMP [CUPS+DI],0
JE ONES
MOV [CUPS+DI], 0
MOV CX, X
ADD Y, CX
INC Y
JMP YLOOP
ONES:
MOV [CUPS+DI], 1
MOV CX, X
ADD Y, CX
INC Y
JMP YLOOP
YDONE:
INC X
JMP XLOOP
XDONE:
MOV DI, 500
CMP Z, DI
JGE ENDPROGRAM
MOV DI, Z
CMP [CUPS+DI],1
JE PRINT
JMP ZEROS
PRINT:

MOV AX, DI
INC AX
CALL PUTDEC
CALL NEWLINE
ZEROS:
INC Z
JMP XDONE
ENDPROGRAM:

.EXIT
        MOV     AX, 4C00H
        INT     21H
MARBLES   ENDP
        END     MARBLES

[dedndave]

i dunno what your teacher is thinking - lol
but, i know that if you want to test a number to see if it is a prime, if it isn't divisable by a value less than its' squareroot, it isn't a prime
a simple way is to start at the squareroot and try all the previously found primes below that
there are faster ways to find primes, though - if you search the forum, there are a few algorithms for it

[veronicak5678]

I don't know if I have a square root function...do you know of one? Is there a simple way to write one?

[dedndave]

this will handle small numbers (up to 16,777,215) - it depends on how large of primes you want to find
there may be a squareroot routine in one of the libraries your prof gave you
of course, you could use the FPU, too, i suppose
i have not tried using the FPU in 16-bit code on a 32-bit machine yet
the last time i wrote 16-bit FPU code, it was for an 8087 - lol
another approach is to just divide the number of bits by 2
if you have a value with 30 bits in it, the squareroot will have no more than 15 bits, so you could start at 7FFFh and work down
you may test a few values that are above the squareroot - but we are not really looking for super fast
actually, it may be faster because you do not have to find the sqaureroot - i don't know

;-----------------------------------------------
;
SQINT   PROC    NEAR
;
;  This is a 24-bit integer squareroot routine.
; It calculates the squareoroot, then rounds
; it to the nearest integer.
;
; By: DednDave - 1987
;
; Call With: DL:AX = 24 bit integer (0-FF:FFFFh)
;
;   Returns: AX = rounded squareroot (0-1000h)
;            BX = DX = CH = 0
;            CF = clear
;            CL, BP, SI, DI invalid
;
        MOV     DH,DL
        MOV     DL,AH
        MOV     BH,AL
        MOV     AX,0C000h
        MOV     BL,AL
        MOV     CX,8
;
SQINT0: TEST    AX,DX
        JNZ     SQINT3
;
        ROR     AX,1
        ROR     AX,1
        LOOP    SQINT0
;
        MOV     CL,4
;
SQINT1: TEST    AH,BH
        JNZ     SQINT2
;
        SHR     AH,1
        SHR     AH,1
        LOOP    SQINT1
;
        RET
;
SQINT2: SUB     CL,4
;
SQINT3: SHL     CL,1
        ADD     CL,9
        XOR     AX,AX
        MOV     SI,AX
        MOV     DI,AX
        MOV     BP,AX
;
SQINT4: SHL     BX,1
        RCL     DX,1
        RCL     DI,1
        RCL     BP,1
        SHL     BX,1
        RCL     DX,1
        RCL     DI,1
        RCL     BP,1
        STC
        RCL     SI,1
        RCL     AX,1
        SUB     DI,SI
        SBB     BP,AX
        JNC     SQINT6
;
        ADD     DI,SI
        ADC     BP,AX
        DEC     SI
        LOOP    SQINT4
;
SQINT5: SHL     SI,1
        RCL     AX,1
        SHL     SI,1
        RCL     AX,1
        SHL     SI,1
        ADC     AX,CX
        RET
;
SQINT6: INC     SI
        LOOP    SQINT4
;
        JMP     SQINT5
;
SQINT   ENDP
;
;-----------------------------------------------

[veronicak5678]

Thanks for the info, but I am getting really far from the assignment here. I think I'm missing something here. I will keep thinking about it.

[ilian007]

Veronica I believe I found way accidently to do that :) will have to think about it how exacly it happens and will post it. Is happens when printing the Array in the early stage if that will help you. not at the end but somewhere in the middle of the process.   I dont know really how but it is when X=1 and after the 500 cyhcles of the y loop. Try to change X like that : 1,3,5,7,9,11.... not sure yet just giving you ideas if I have answer for sure will post it :)

[veronicak5678]

Hi-

I tried putting an 'INC X' in after the loop starts to increase by 2 every time, but that isn't working. I guess I'm not really sure what you mean. Any luck yet?

[dedndave]

Veronica
i was having a hard time understanding your program
that was making it hard for me to see any natural changes that might make it a primes program
it probably also explains the lack of enthusiasm from other members - lol
there are a few points that you should learn that your prof is not teaching you
first, i tried to modularize the program a little bit for clarity
second - i keep the variables you had as X, Y, and Z in registers
always try to make use of your registers
i try to keep all of them busy all the time - this program only needed a few of them
finally, loop structure - if you have a loop that ends with something like "JMP LOOP_BEGINNING",
it usually means your loop is poorly structured
this is a simplified rule of thumb:
at the end of a loop, it should go back to the beginning OR fall through to the next step by a conditional branch

;===================================================================

; MARBLES

;===================================================================

        .MODEL  SMALL
        .586
        .STACK  512

        INCLUDE PCMAC.INC

        EXTERN  NEWLINE:FAR
        EXTERN  PUTDEC:FAR

;------------------------------------------------------

        .DATA

CUPS DB 500 DUP (0)

;------------------------------------------------------

        .CODE

MAIN    PROC    FAR

;initialization

        MOV     AX,DGROUP           ;SET DS AND ES REGISTERS
        MOV     DS,AX               ;TO POINT TO DGROUP
        MOV     ES,AX

;execute the routines

        MOV     AX,1                ;AX = 1 THROUGHOUT THE ENTIRE PROGRAM
        CALL    MARBLES             ;BUILD THE ARRAY
        CALL    DISPLAY             ;DISPLAY THE RESULTS

;terminate program

        MOV     AX,4C00h
        INT     21h

MAIN    ENDP

;------------------------------------------------------

MARBLES PROC    NEAR

;outer loop

        MOV     CX,AX

XLOOP:  MOV     DI,CX

;---------------------------------

;inner loop

YLOOP:  XOR     CUPS[DI-1],AL
        ADD     DI,CX
        CMP     DI,500
        JB      YLOOP               ;STOP WHEN Y > 500

;---------------------------------

        INC     CX
        CMP     CX,500
        JB      XLOOP

        RET

MARBLES ENDP

;------------------------------------------------------

DISPLAY PROC    NEAR

        XOR     DI,DI

DLOOP:  CMP     AL,CUPS[DI]
        JNZ     SKIPIT

        PUSH    AX
        ADD     AX,DI
        PUSH    DI
        CALL    PUTDEC
        CALL    NEWLINE
        POP     DI
        POP     AX

SKIPIT: INC     DI
        CMP     DI,500
        JB      DLOOP

        RET

DISPLAY ENDP

;------------------------------------------------------

        END     MAIN


EDIT - corrected and simplified the inner loop

[veronicak5678]

Hi Dave-

Thanks for helping me again! I'm not sure if your code follows what my teacher wanted though.

All he told us was we had to use the following pseudo-code:

array 500 dup(0)

for x = 1 to 500
     for y = x to 500 step x
        if arr(y) = 0
            arr(y) = 1
        else
            arr(y) = 0
       endif
     next y
next x

then to print:

for x = 1 to 500
    iff arr(x) = 1
    print x
  endif
next x

I think my code was (at least partly) so bad because I was trying to follow this.

[dedndave]

to write that code, i started with yours and just moved things around and simplified it a little at a time
it should do the same thing as yours, hopefully - lol
if you look, you will see that, in the main loops, i used DI to hold "Y" and CX to hold "X"
in the display loop, i used DI to hold "Z"
AX is always a 1, which means that AH is a 0 byte and AL is a 1 byte
looking at it now, i could have used BX or SI to hold a 500, as well

i don't have the PCMAC library, so i didn't test it - let me know if it works - lol

[veronicak5678]

No, it didn't do the same thing. I just ran it and it displayed all the numbers from 1 - 499.

[dedndave]

dang - lol
let me find my booboo

[dedndave]

here it is - replace my inner loop with this

;---------------------------------

;inner loop

YLOOP:  DEC     DI                  ;ELEMENT 0
        CMP     AH,CUPS[DI]
        JNZ     RESET

        MOV     CUPS[DI],AL
        JMP SHORT NEXTY

RESET:  MOV     CUPS[DI],AH

NEXTY:  ADD     DI,CX
        INC     DI
        CMP     DI,500
        JB      YLOOP               ;STOP WHEN Y > 500

;---------------------------------

[veronicak5678]

OK, it's working! Thank you. I'm going to go have dinner, and I'll try to figure out the prime stuff when I get back.

[dedndave]

better yet...

;---------------------------------

;inner loop

YLOOP:  DEC     DI                  ;ELEMENT 0
        MOV     BX,AX
        CMP     AH,CUPS[DI]
        JZ      NEXTY

        DEC     BX

NEXTY:  MOV     CUPS[DI],BL
        ADD     DI,CX
        INC     DI
        CMP     DI,500
        JB      YLOOP               ;STOP WHEN Y > 500

;---------------------------------

yes - now let's see if we can make it do primes