Prime Number Program

[dedndave]

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

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

[dedndave]

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"

[MichaelW]

the 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) = n² + n + 41

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

In my test I used the FPU to calculate n from n², and the complete calculation involved more than "a few lines", so I'm not sure that this is the intended method.

[dedndave]

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

[ilian007]

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

[ilian007]

I think I have no life. I did spent about 20hours this weekend for assembly :( My dog will leave me (expression dont have one)

[raymond]

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.

[ilian007]

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...

[sinsi]

32-bit, uncommented, incomplete

Code Select Expand


    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.

the lack of enthusiasm from other members

Dave, don't forget rule 9.

[Rockphorr]

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

[Rockphorr]

If my tonight time will free I will have done it.

[dedndave]

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

[veronicak5678]

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!

[dedndave]

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"

[veronicak5678]

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.