0
\$\begingroup\$

I'm trying to make a small program which takes a number (form 1 to 1000) and shows the primes between 2 and that number. Right now I have a quite functioning program (except a couple of bugs), but the problem is that it needs a lot of cycles. In the worst case scenario (limit = 1000) it takes roughly 2 million cycles to complete.

So I'm asking you guys what could be optimized.

Please note I have developed it from scratch and already optimized what I could think of (took 4.5 million cycles before).

BTW, the prime finding algorithm I used is the Sieve of Eratosthenes.

Here is the code:

            .area PROG (ABS)

        .org 0x100
        .globl program

keyboard    .equ    #0xFF02
screen .equ #0xFF00

limit:  .word 0
limit2000:  .word 0
limitx2:    .word 0
num:    .word 0
numorg: .word 0
countread:  .word 0
cont:   .word 2 ;conter for the load loop
contt:  .word -2 ;used for offset over X pointer
contn:  .word -2000
contnt: .word -2000
primeA: .word 1
primeB: .word 1
primeC: .word 1
square1:    .word 1
square2:    .word 1
squareo:    .word 1
valX:   .word 2000

tmp:    .byte 0
tmp2:   .word 0
tmp3:   .word 0
temp:   .byte 0

program:

ldx #2000
start:
    ldb keyboard
    cmpb    #'\n
    beq end
    cmpb    #0x7F
    beq backspace
    subb    #0x30
    stb tmp
    ldd limit
    lda #10
    mul
    std tmp2
    clra
    ldb tmp
    std tmp3
    ldd tmp2
    addd    tmp3
    std limit
    std ,X++
    ldb countread
    decb
    stb countread
    bra start

backspace:
    lda #8
    sta screen
    sta screen
    lda #' 
    sta screen
    sta screen
    lda #8
    sta screen
    sta screen
    ldb countread
    cmpb    #0
    beq start
    lda #8
    sta screen
    lda #' 
    sta screen
    lda #8
    sta screen
    ldd ,--x
    ldd -2,x
    std limit
    ldb countread
    incb
    stb countread
    bra start

end:
    lda #'\0
    sta ,X
    ldb countread
    cmpb    #0
    beq empty
    andcc   #0b11111011
    ldd limit
    addd    #2000
    std limit2000
    addd    limit2000
    std limitx2
    ldd limit
    ldx #2000
    bra load

empty:
    orcc    #0b00000100
    puls    A,PC

load:
    ldd     cont
    std     ,x++
    addd    #1
    std     cont
    ldd     contn
    subd    #2
    std     contn
    ldd     cont
    cmpd    limit
    blo     load

    ldd     contn
    std     contnt
    ldd     contn
    addd    #2
    bra     findNextPrime

ponerX0:
    ldx     #2000
    bra     ctd3

findNextPrime:
    leax    2,x
    ldx     #2000
    findnp:
        ldd     primeA
        addd    #1
        std     primeA
        ldd     contt
        addd    #2
        std     contt
        ldd     d,x
        cmpd    #0
        beq     findnp
        std     primeA
        bra     deleteMultiples

square:
    ldd     square1
    subd    #1
    std     square1
    ldd     square2
    addd    primeB
    std     square2
    cmpd    limit
    lbhs    printPrimes
    ldd     square1
    cmpd    #1
    bne     square
    bra     ctd2

deleteMultiples:
    std square1
    std square2
    std primeB
    bra square
    ctd2:
        ldd square2
        std primeB
        std primeC
        ldd #0
        std valX
        ldd primeA
        cmpd    #2
        bne ponerX0
        ctd3:
            ldd square2
            lslb
            rola
        ctd:
            leax    2,x
            subd    #2
            std primeC
            ldd valX
            addd    #2
            std valX
            ldd primeC
            cmpd    #4
            bne ctd
        ldd #0
        std ,x
        deleteNum:
            ldd primeA
            lslb
            rola
            delete1Num:
                leax    2,x
                subd    #2
                std primeC
                ldd valX
                addd    #2
                std valX
                ldd primeC
                cmpd    #0
                bne delete1Num
                ldd #0
                std ,x
                ldd valX
                cmpd    limitx2
                lbhs    findNextPrime
                bra deleteNum

printPrimes:
    ldd #-2
    std cont
    ldx #2000
    printPrimesL:
        ldd cont
        addd    #2
        std cont
        ldd d,x
        std num
        cmpd    #0
        bne printString
        ldd cont
        cmpd    limitx2
        blo printPrimesL
        lbra finish

printString: 
    ldd num
    std numorg
    cmpd #500
    lblo less500
    cmpd #700
    blo less700
    cmpd #900
    blo less900
    std temp
    ldb #'9 
    stb screen
    ldd temp
    subd #900
    lbra twoDigits

less900:
    cmpd #800
    blo less800
    std temp
    ldb #'8     
    stb screen
    ldd temp
    subd #800
    lbra twoDigits
less800:
    std temp
    ldb #'7     
    stb screen
    ldd temp
    subd #700
    lbra twoDigits
less700:
    cmpd #600
    blo less600
    std temp
    ldb #'6     
    stb screen
    ldd temp
    subd #600
    lbra twoDigits
less600:
    std temp
    ldb #'5     
    stb screen
    ldd temp
    subd #500
    lbra twoDigits
less500:
    cmpd #300
    blo less300
    cmpd #400
    blo less400
    std temp
    ldb #'4 
    stb screen
    ldd temp
    subd #400
    lbra twoDigits
less400:
    std temp
    ldb #'3 
    stb screen
    ldd temp
    subd #300
    lbra oneDigit
less300:
    cmpd #200
    blo less200
    std temp
    ldb #'2
    stb screen
    ldd temp
    subd #200
    lbra twoDigits
less200:
    cmpd #100
    blo twoDigits
    std temp
    ldb #'1
    stb screen
    ldd temp
    subd #100
twoDigits:
    cmpd #50
    blo less50
    cmpd #70
    blo less70
    cmpd #90
    blo less90
    std temp
    ldb #'9 
    stb screen
    ldd temp
    subd #90
    lbra oneDigit
less90:
    cmpd #80
    blo less80
    std temp
    ldb #'8 
    stb screen
    ldd temp
    subd #80
    lbra oneDigit
less80:
    std temp
    ldb #'7 
    stb screen
    ldd temp
    subd #70
    lbra oneDigit
less70:
    cmpd #60
    blo less60
    std temp
    ldb #'6 
    stb screen
    ldd temp
    subd #60
    lbra oneDigit
less60:
    std temp
    ldb #'5
    stb screen
    ldd temp
    subd #50
    lbra oneDigit
less50:
    cmpd #30
    blo less30
    cmpd #40
    blo less40
    std temp
    ldb #'4 
    stb screen
    ldd temp
    subd #40
    lbra oneDigit
less40:
    std temp
    ldb #'3 
    stb screen
    ldd temp
    subd #30
    lbra oneDigit
less30:
    cmpd #20
    blo less20
    std temp
    ldb #'2
    stb screen
    ldd temp
    subd #20
    lbra oneDigit
less20:
    cmpd #10
    blo less10
    std temp
    ldb #'1
    stb screen
    ldd temp
    subd #10
    bra oneDigit
less10:
    std temp
    ldd numorg
    cmpd #10
    blo oneDigit
    ldb #'0
    stb screen
    ldd temp
oneDigit:
    addd #48
    stb screen
    ldb #' 
    stb screen
    lbra    printPrimesL


finish: clra
        sta 0xFF01
        .org 0xFFFE
        .word program
\$\endgroup\$
3
  • \$\begingroup\$ If you want fastest, then use this tool to generate a sequence of primes between 1 and 1000, then write another program that loads this sequence into memory, and when given a range simply selects from the pre-generated sequence. Selecting a range from an array should be a few hundred cycles, not millions, and is likely to be the most optimal solution. \$\endgroup\$
    – Software Engineer
    Commented May 1, 2016 at 16:37
  • \$\begingroup\$ This is for an assignment and we are forbidden from using such methods. No precalculated data. \$\endgroup\$
    – Dr. House
    Commented May 1, 2016 at 18:31
  • \$\begingroup\$ Please read meta.stackexchange.com/a/5222/213556 \$\endgroup\$
    – Simon Forsberg
    Commented May 4, 2016 at 21:49

1 Answer 1

Reset to default
2
\$\begingroup\$

As a general observation (my 6809 assembly has become rather rusty after 30 years), you're using only half the register set and doing a lot of loads & stores from and to memory for your scalars. Try figuring out whether you can employ the Y and U registers usefully, especially in your inner loops.

Your square: section looks like you're performing a very slow multiplication, which is several sorts of wrong:

  • The 6809 is the rare 8-bit microprocessor that has a hardware multiplication instruction.
  • Even without a hardware instruction, there are considerably faster ways to multiply.
\$\endgroup\$
1
  • \$\begingroup\$ You're right about the "square". I don't know why but I thought I would need to calculate squares of numbers larger than 255 so I couldn't use the MUL instruction. But thinking about it the largest square I'm going to need to calculate is 37, so I can use MUL. Thanks for that. I'll look into the rest of what you said later this week (no time right now). Thanks. \$\endgroup\$
    – Dr. House
    Commented May 2, 2016 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.