Sunday, October 16, 2011

Prime algorithm in assembler

One of the greatest strengths of assembly language is the extreme compactness of code. Digging though my old files I found this gem that prints all prime numbers under 2^32. The COM file size is 165 bytes. That's right! You could memorize the bytes if you wanted to and hand assemble it.

The algorithm is not sieve (which would create 2^31 locations and strike off multiples of primes). Rather this is a space optimized algorithm that repeatedly divides each number n from 2 to sqrt(n) to determine if a number is prime. This algorithm uses no additional storage than the 165 bytes to hold the code.

.model tiny
        org     100h
main    proc
        xor     eax,eax
        mov     al,3
        call    isprime
        jnc     @@m1
        call    printdword
        call    printcrlf
        inc     eax
        jnz     @@m2

        mov     ax,4c00h
        int     21h
main    endp

isprime proc
        mov     esi,eax         ; save number
        xor     ecx,ecx
        mov     ebx,ecx
        mov     edx,ecx         ; edx = 0
        call    sqrt
        mov     cx,ax           ; save sqrt
        mov     bl,2            ; ebx = 2 (divisor)
        mov     eax,esi         ; restore number
        cmp     ecx,ebx         ; is sqrt < divisor?
        jl      @@i4            ; yes, no need to divide any more
        div     ebx
        or      edx,edx
        jz      @@i1
        xor     edx,edx
        inc     ebx
        jnz     @@i2
        jmp     @@i3
isprime endp

sqrt    proc
        push    ebx
        push    ecx

        xor     ecx,ecx
        mov     ebx,ecx
        inc     ebx
        sub     eax,ebx
        jl      @@s1
        inc     cx
        inc     ebx
        jmp     @@s2
        mov     ax,cx

        pop     ecx
        pop     ebx
sqrt    endp

printdword      proc
        xor     ebx,ebx
        mov     cx,bx
        mov     bl,10
        xor     edx,edx
        div     ebx
        push    dx
        inc     cx
        or      eax,eax
        jnz     @@p1
        pop     ax
        add     al,'0'
        mov     dl,al
        mov     ah,02
        int     21h
        loop    @@p2

printdword      endp

printcrlf       proc
        mov     dl,13
        mov     ah,02
        int     21h
        mov     dl,10
        mov     ah,2
        int     21h
printcrlf       endp
        end     start