The MASM Forum Archive 2004 to 2012

Miscellaneous Forums => 16 bit DOS Programming => Topic started by: veronicak5678 on November 14, 2009, 08:12:23 PM

Title: Prime Number Program
Post by: veronicak5678 on November 14, 2009, 08:12:23 PM
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?

;===================================================================
         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
Title: Re: Prime Number Program
Post by: dedndave on November 15, 2009, 02:47:26 AM
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
Title: Re: Prime Number Program
Post by: veronicak5678 on November 15, 2009, 03:03:16 AM
I don't know if I have a square root function...do you know of one? Is there a simple way to write one?
Title: Re: Prime Number Program
Post by: dedndave on November 15, 2009, 08:41:24 AM
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
;
;-----------------------------------------------
Title: Re: Prime Number Program
Post by: veronicak5678 on November 15, 2009, 06:30:09 PM
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.
Title: Re: Prime Number Program
Post by: ilian007 on November 15, 2009, 07:56:36 PM
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 :)
Title: Re: Prime Number Program
Post by: veronicak5678 on November 15, 2009, 10:29:05 PM
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?
Title: Re: Prime Number Program
Post by: dedndave on November 16, 2009, 12:59:45 AM
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
Title: Re: Prime Number Program
Post by: veronicak5678 on November 16, 2009, 01:48:09 AM
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.
Title: Re: Prime Number Program
Post by: dedndave on November 16, 2009, 01:56:04 AM
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
Title: Re: Prime Number Program
Post by: veronicak5678 on November 16, 2009, 02:09:19 AM
No, it didn't do the same thing. I just ran it and it displayed all the numbers from 1 - 499.
Title: Re: Prime Number Program
Post by: dedndave on November 16, 2009, 02:16:18 AM
dang - lol
let me find my booboo
Title: Re: Prime Number Program
Post by: dedndave on November 16, 2009, 02:19:13 AM
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

;---------------------------------
Title: Re: Prime Number Program
Post by: veronicak5678 on November 16, 2009, 02:23:30 AM
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.
Title: Re: Prime Number Program
Post by: dedndave on November 16, 2009, 02:26:21 AM
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
Title: Re: Prime Number Program
Post by: dedndave on November 16, 2009, 02:28:52 AM
ok - one more time - lol

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

;inner loop

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

;---------------------------------
Title: Re: Prime Number Program
Post by: dedndave on November 16, 2009, 02:45:56 AM
we should be able to see the primes here

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

i think the key is the "step x"
Title: Re: Prime Number Program
Post by: MichaelW on November 16, 2009, 03:31:57 AM
Quotethe lack of enthusiasm from other members
I did not respond because I had not seen any clear description of the original algorithm, and I had some doubts that the posted code was a correct implementation. One way to go from squares to prime numbers (within limits) would be this:

P(n) = n2 + n + 41

http://en.wikipedia.org/wiki/Prime_number#Distribution

In my test I used the FPU to calculate n from n2, and the complete calculation involved more than "a few lines", so I'm not sure that this is the intended method.
Title: Re: Prime Number Program
Post by: dedndave on November 16, 2009, 03:48:41 AM
i think if you understand how it generates squares, you will be half-way home - lol
on the first pass, it steps by one
on the second, by two
on the third, by three, and so on
i have never seen this algo before (which doesn't mean much, as i always try to make my own stuff - lol)
it certainly is not a great way to generate squares, for the sake of speed
it is rather interesting, though
the guy we need is Mr Math - Raymond - lol
he has probably played with this algo before
Title: Re: Prime Number Program
Post by: ilian007 on November 16, 2009, 04:10:49 AM
I think you need another array
in that array, keep track of the number of times a marble(one) has been dropped into the cups
it turns out that the cups that only had one ball dropped in them are primes

I guess those are the cups that has not been stepped by step x... (what dedndave said)

for x =1 we step thru all the cups y=1 to 500 step 1 ==> 1,2,3,4,5,6,7,8,9,10

x=2 step with 2 =====> 2,4,6,8,10,12,14,16,18,20,22,24
x=3 step with 3 =====> 3,6,9,12,15,18,21,25
x=4 step with 4 =====> 4,8,12,16,20,24

for that one we stepped only one time (first time) thru: 5,7,11,19

which are primes ....

still thinking how to code that.....

I guess primes=2stepx+1


Title: Re: Prime Number Program
Post by: ilian007 on November 16, 2009, 04:13:34 AM
I think I have no life. I did spent about 20hours this weekend for assembly :( My dog will leave me (expression dont have one)
Title: Re: Prime Number Program
Post by: raymond on November 16, 2009, 06:06:42 AM
I have never seen such an algo to generate squares. (And I must admit I have a lot of trouble with that stupid syntax which doesnotleavespacesbetweenmnemonicsandparameters.)

Without trying that algo in a debugger to follow what is happening, I have to assume it's some kind of a sieve. A sieve is also the quickest way to generate an array of primes.

You first start with a zeroed byte array. Starting with the first known prime 2 (in DI) and in another indexing register (BX), you increment BX by DI and insert a 1 in all the indexed array until BX reaches the upper limit. You then search the array with DI for the next value of 0, transfer it to BX and do the same as for the 2. Continue while DI is less than the square root of the upper limit.

All the items of the filled array which are still equal to 0 (except for 0 and 1) are primes.

A few optimizations can be done for large arrays.
Title: Re: Prime Number Program
Post by: ilian007 on November 16, 2009, 06:18:33 AM
Raymond with all respect we are beginners (introduction to assembly ) :) Teacher said after we are done with the first code we will have to change just about a few lines of it and it will start producing primes...
Title: Re: Prime Number Program
Post by: sinsi on November 16, 2009, 06:48:15 AM
32-bit, uncommented, incomplete

    mov ecx,2
@1: mov edx,ecx
    jmp @3
@2: mov array[edx],1
@3: add edx,ecx
    cmp edx,500
    jbe @2
    inc ecx
    cmp ecx,500
    jbe @1

I felt sorry for you guys and gals...it has been absolute torture to watch these topics.
Quotethe lack of enthusiasm from other members
Dave, don't forget rule 9.
Title: Re: Prime Number Program
Post by: Rockphorr on November 16, 2009, 08:39:38 AM
I think that you must produce algorithm of Eratosfen

1. you create array of pair (2,0)...(n,0)
2. you look ahead in loop for each member (2*i,0)  (3*i,0) ... and replace 0 to 1 (0 -number is prime 1 is complex)
3. you scan array and print all members with 0
Title: Re: Prime Number Program
Post by: Rockphorr on November 16, 2009, 08:49:00 AM
If my tonight time will free I will have done it.
Title: Re: Prime Number Program
Post by: dedndave on November 16, 2009, 01:44:12 PM
i can't test this, but it should work ok...

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

; SQUARES AND PRIMES

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

        .MODEL  SMALL
        .586
        .STACK  512

        INCLUDE PCMAC.INC

        EXTERN  NEWLINE:FAR
        EXTERN  PUTDEC:FAR

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

        .DATA

ARRY    DB 500 DUP (0)              ;START WITH ALL 0'S

KEYMSG  DB 'Press Any Key to Continue...',0Dh,0Ah,24h

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

        .CODE

MAIN    PROC    FAR

;INITIALIZATION

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

;SQUARES

        MOV     AX,1
        MOV     SI,500
        CALL    SQUARES             ;BUILD THE ARRAY
        MOV     DI,1                ;START WITH 1
        CALL    DISPLAY             ;DISPLAY THE RESULTS

        CALL    ANYKEY              ;WAIT FOR A KEYPRESS

;PRIMES

        MOV     AX,1
        MOV     SI,500
        CALL    SETARAY             ;SET THE ARRAY TO ALL 1'S
        CALL    PRIMES              ;BUILD THE ARRAY
        MOV     DI,2                ;START WITH 2 (1 IS NOT A PRIME)
        CALL    DISPLAY             ;DISPLAY THE RESULTS

        CALL    ANYKEY              ;WAIT FOR A KEYPRESS

;TERMINATE

        MOV     AX,4C00h
        INT     21h

MAIN    ENDP

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

SQUARES PROC    NEAR

;BUILD THE ARRAY WITH SQUARES

;OUTER LOOP

        MOV     CX,AX               ;START WITH 1

XLOOP:  MOV     DI,CX

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

;INNER LOOP

YLOOP:  XOR     ARRY[DI-1],AL       ;TOGGLE IT
        ADD     DI,CX
        CMP     DI,SI
        JBE     YLOOP

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

        INC     CX
        CMP     CX,SI
        JBE     XLOOP

        RET

SQUARES ENDP

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

SETARAY PROC    NEAR

;SET THE ARRAY TO ALL 1's

;WE COULD RESET IT TO ALL 0's
;BUT THEN WE'D HAVE TO CHANGE THE DISPLAY ROUTINE TO DISPLAY ELEMENTS=0
;WE WANT TO USE THE SAME DISPLAY ROUTINE FOR BOTH
;SO WE INVERT THE LOGIC

        CLD
        MOV     DI,OFFSET ARRY
        MOV     CX,SI
        REP     STOSB
        RET

SETARAY ENDP

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

PRIMES  PROC    NEAR

;BUILD THE ARRAY WITH PRIMES

;OUTER LOOP

        MOV     CX,2                ;START WITH 2

ALOOP:  MOV     DI,CX
        JMP SHORT NEXTB             ;SKIP THE FIRST ONE

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

;INNER LOOP

BLOOP:  MOV     ARRY[DI-1],AH       ;DON'T TOGGLE IT - RESET IT

NEXTB:  ADD     DI,CX
        CMP     DI,SI
        JBE     BLOOP

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

        INC     CX
        CMP     CX,SI
        JBE     ALOOP

        RET

PRIMES  ENDP

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

DISPLAY PROC    NEAR

;DISPLAY THE RESULTS

DLOOP:  CMP BYTE PTR ARRY[DI-1],1
        JNZ     SKIPIT

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

SKIPIT: INC     DI
        CMP     DI,500
        JBE     DLOOP

        RET

DISPLAY ENDP

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

ANYKEY  PROC    NEAR

;DISPLAY "Press Any Key to Continue..." AND WAIT FOR A KEYPRESS

        MOV     DX,OFFSET KEYMSG
        MOV     AH,9
        INT     21h
        MOV     AH,0
        INT     16h
        RET

ANYKEY  ENDP

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

        END     MAIN
Title: Re: Prime Number Program
Post by: veronicak5678 on November 16, 2009, 04:29:10 PM
It does work, very nicely, but of course there are a lot of instructions I've never seen before. I'll spend some time trying to figure this out.

Thanks again!
Title: Re: Prime Number Program
Post by: dedndave on November 16, 2009, 04:44:42 PM
that's probably because they are instructions your prof has never seen before - lol
you should try to learn the entire instruction set on your own
also - if you are going to continue to write 16-bit code, learn to use the software INT's - especially INT 21h
you can google or use the forum search for "Ralf Brown's Interrupt List"
Title: Re: Prime Number Program
Post by: veronicak5678 on November 16, 2009, 04:53:33 PM
I have been looking at this for about 20 minutes, and I don't get it...

Why is the primes proc generating primes? It seems like it should just generate odds. Forgive me if I'm missing something obvious, but I haven't had coffee yet.

I agree that my professor doesn't seem to be teaching us some important things, but the problem becomes trying to do his assignments with just what he gives us. Or trying to translate your nice programs into something I could have written with the little I know.

And thanks for showing me the Interrupt List. That's pretty cool.
Title: Re: Prime Number Program
Post by: dedndave on November 16, 2009, 05:17:06 PM
it is because the step changes with each pass of the outer loop
the first time through, it steps by 2 (i.e. marking elements that are divisible by 2)
the second time through, it steps by 3 (i.e. marking elements that are divisible by 3)
the third time through, it steps by 4 (i.e. marking elements that are divisible by 4 - which have already been marked - lol)
and so on
we skip the first pass on the inner loop, that way, it does not mark the prime, itself
Title: Re: Prime Number Program
Post by: veronicak5678 on November 16, 2009, 05:22:58 PM
OK, I get it. I will try to translate this to my level.

Thanks again, Dave. I feel like you're my second (and better) teacher!
Title: Re: Prime Number Program
Post by: ilian007 on November 16, 2009, 05:44:21 PM
Dedndave I agree with the last post of Veronica :)
Title: Re: Prime Number Program
Post by: dedndave on November 16, 2009, 05:51:49 PM
hey - at least your prof isn't a meanie
if he was mean, he would have given you the primes program already written and asked for squares - lol
look for that on the final exam, eh ?
Title: Re: Prime Number Program
Post by: ilian007 on November 16, 2009, 06:20:43 PM
He is a very smart and good guy and knows a lot. I think he is so bored of teaching so easy things which are defin. not so exciting for him :) I am trying to create an easy way to produce primes. Your way is great dedndave, but too advanced for me as well :)

I am trying to integrate an extra array in my inner loop which will count the skiped elements (indexes) by Y for all X's

y=(2),4,6,8,10,12,14,16,18,20,22 
y=(3),6,9,12,15,18,21
y=(4),8,12,16,20,24

for those 3 - 1,3,5,7,11,13,17,19 were skipped and all them are primes.

I am trying to pull out all the elements which were NOT XORed by AL

LOOP_Y: 
   XOR     MyArr[DI-1],AL
   ADD     DI,CX
   CMP     DI,500
        JB      LOOP_Y 


Should I put all them in array and then pull all all the 0 elements of the new array ?

shouldnt be so complicated I guess ?


Title: Re: Prime Number Program
Post by: dedndave on November 16, 2009, 06:27:54 PM
just look at the program i posted
take careful note of the differences between the SQUARES and PRIMES routines
those are the lines that i have commented
in that program, i started the PRIMES routine with an all 1's array - so set it to 1 for an all 0's array
Title: Re: Prime Number Program
Post by: MichaelW on November 16, 2009, 08:30:58 PM
In my test doing the P(n) = n2 + n + 41 with the FPU required 9 additional instructions, and no additional data. In the few hours I spent on it I could not find any way to switch the output to primes by changing only a few instructions.

Title: Re: Prime Number Program
Post by: dedndave on November 16, 2009, 08:58:58 PM
look on page 2, Michael
Title: Re: Prime Number Program
Post by: Rockphorr on November 16, 2009, 11:08:14 PM
Solution is

;===================================================================
         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 2 ;<------------------------------------------------------point 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
ADD AX,2  ;<---------------------------------------------------------------------------------point 2 
CALL PUTDEC
CALL NEWLINE
ZEROS:
INC Z
JMP XDONE
ENDPROGRAM:

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



OUOU!!!!!!!!!!!!!!!!! YES IT IS HIM !!!!!!!!!!!!!!!!   :clap: :clap: :clap: :clap: :clap: :clap: :clap: :clap: :clap: :clap: :clap: :clap: :clap: :clap: :clap:
Title: Re: Prime Number Program
Post by: dedndave on November 16, 2009, 11:28:18 PM
guys ! - lol
http://www.masm32.com/board/index.php?topic=12705.msg98049#msg98049
Title: Re: Prime Number Program
Post by: Rockphorr on November 17, 2009, 08:30:43 AM
Quote from: dedndave on November 16, 2009, 11:28:18 PM
guys ! - lol
http://www.masm32.com/board/index.php?topic=12705.msg98049#msg98049

:thumbu
BUT
change few lines is not mean replace parts of code to subroutines
:dance: :dance: :dance:
Title: Re: Prime Number Program
Post by: dedndave on November 17, 2009, 12:17:47 PM
i did that so that both the unmodified and modified code could be run together - lol
that way, you can see the changes - and see the results of both at runtime

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

SQUARES PROC    NEAR

;BUILD THE ARRAY WITH SQUARES

;OUTER LOOP

        MOV     CX,AX               ;START WITH 1

XLOOP:  MOV     DI,CX

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

;INNER LOOP

YLOOP:  XOR     ARRY[DI-1],AL       ;TOGGLE IT
        ADD     DI,CX
        CMP     DI,SI
        JBE     YLOOP

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

        INC     CX
        CMP     CX,SI
        JBE     XLOOP

        RET

SQUARES ENDP

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

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

PRIMES  PROC    NEAR

;BUILD THE ARRAY WITH PRIMES

;OUTER LOOP

        MOV     CX,2                ;START WITH 2

ALOOP:  MOV     DI,CX
        JMP SHORT NEXTB             ;SKIP THE FIRST ONE

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

;INNER LOOP

BLOOP:  MOV     ARRY[DI-1],AH       ;DON'T TOGGLE IT - RESET IT

NEXTB:  ADD     DI,CX
        CMP     DI,SI
        JBE     BLOOP

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

        INC     CX
        CMP     CX,SI
        JBE     ALOOP

        RET

PRIMES  ENDP

;------------------------------------------------------
Title: Re: Prime Number Program
Post by: MichaelW on November 17, 2009, 03:15:19 PM
Dave,

Your solution works fine, but IMO it's too far from the original algorithm. Going from a straightforward implementation of the original algorithm in assembly to your prime code requires changes to more than "a few lines". And I have doubts that the instructor would expect a beginner, already more or less overwhelmed with the assembly code details, to start with the original algorithm and arrive at something like yours.

Title: Re: Prime Number Program
Post by: dedndave on November 17, 2009, 03:24:53 PM
are you talking about the code or the pseudo-code ?
the pseudo-code was the assignment of the instructor
the original assembler code was written by the student
to arrive at the code i used, i merely simplified her original code
i also reorganized it, for a few reasons, primarily to give the student an example to learn from
part of the goal was to help the student write cleaner, more efficient code in the future

EDIT - i am looking at the pseudo-code and trying to see how my code does not match it ?????

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

arr 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
    if arr(x) = 1
    print x
  endif
next x
Title: Re: Prime Number Program
Post by: dedndave on November 17, 2009, 04:40:21 PM
QuoteOne way to go from squares to prime numbers (within limits) would be this:
P(n) = n2 + n + 41

QuoteIn my test doing the P(n) = n2 + n + 41 with the FPU required 9 additional instructions, and no additional data.

(can't use my code - lol - but the FPU is ok)

a quote from your link:
QuoteEuler noted that the function
    n2 + n + 41
gives prime numbers for n < 40 (but not necessarily so for bigger n)
http://en.wikipedia.org/wiki/Prime_number#Distribution

i think the real issue is this, Michael
the instructor did not use "your" algorithmm and.....

QuoteIn the few hours I spent on it I could not find any way to switch the output to primes by changing only a few instructions.

i won't help these students any more - i can see that you have it covered
Title: Re: Prime Number Program
Post by: ilian007 on November 17, 2009, 04:59:23 PM
IN class teacher cleared a little bit the task. He said change should be made on 2-3 lines of the original assembly code without adding new lines. :)
Title: Re: Prime Number Program
Post by: ilian007 on November 17, 2009, 05:26:32 PM
Quote
i won't help these students any more - i can see that you have it covered

Noooo, Dedndave you are totaly right you have cleared and showed us how to do it in the better and right way.

Thank you for that
Title: Re: Prime Number Program
Post by: ilian007 on November 17, 2009, 05:29:23 PM
Rockphorr when I tried the code with your changes it is printing all the indexes not only the primes maybe I did it wrong .. 
Title: Re: Prime Number Program
Post by: ilian007 on November 17, 2009, 11:34:54 PM
Dedndave and all the others thank you for giving me(us) some more examples and methods for doing the program more efficient. That is definitely a good learning expirience and is very helpfull.

Thanks :)