Author Topic: Sieve of Eratosthenes - Print Prime Numbers  (Read 16007 times)

Offline Mathi

  • Jr. Member
  • *
  • Posts: 82
  • Country: in
    • Win32NASM
Sieve of Eratosthenes - Print Prime Numbers
« on: January 26, 2012, 06:39:32 PM »
Sieve of Eratosthenes:
Algorithm for finding all prime numbers up to MAX LIMIT (2^32 - 1). (ASM implementation).

Reference:
http://www.algorithmist.com/index.php/Prime_Sieve_of_Eratosthenes.cpp

Reference for Integer sqroot:
http://www.azillionmonkeys.com/qed/sqroot.html

Usage : Sieve  <integer>

eg:
C:\NASM> Sieve 13
2
3
5
7
11
13
Number of Primes = 6

Code: [Select]
;;;;C++ Version for Reference
;;;;http://www.algorithmist.com/index.php/Prime_Sieve_of_Eratosthenes.cpp
;;;;#include <cmath>
;;;;#include <vector>
;;;;
;;;;/*primes is a list of primes, n is all the primes you want to generate.. from 2 to n*/
;;;;void genPrimes(vector<int>&primes,int n){
;;;; for(int i=2;i<=n;i++){
;;;; int root=int(sqrt(i))+1;    /*remember the square root*/
;;;; bool found=false;       /*prime found?*/
;;;; for(vector<int>::const_iterator it = primes.begin();it!=primes.end()&& *it<root;it++){
;;;; if(i% *it==0){found=true;break;} /*this is not prime*/
;;;; }
;;;; if(!found)primes.push_back(i); /*this is a prime*/
;;;; }
;;;;}

;;;;  Reference for isqrt
;;;;  http://www.azillionmonkeys.com/qed/sqroot.html

;;;;*********************
;;;;Assemble with :
;;;;nasm -fobj Sieve.asm

;;;;Link with
;;;;alink -c -oPE -subsys con Sieve

;;;;Usage eg: Sieve 2000
;;;;*********************


%include "win32n.inc"

;;================================
;; MACRO  str2int     int2str by Written by mastercpp.
;;================================
%macro str2int 1
        push    ebx ;
        push    esi ;
        push    edi ;
        mov ebx, 0
        mov ecx, 0
        xor eax,eax
        mov ebx,0000000Ah
        mov esi, %1
        %%ConvertLoop:
        movzx ecx,byte [esi] ;Zeichen laden.
        test ecx,ecx
        jz  short %%ExitConvertLoop ;0 => Exit
        inc esi
        sub cl,30h ;0-9...
        mul ebx ;Ergebnis * 10
        add eax,ecx ;+ nächste Ziffer
        jmp short %%ConvertLoop
        %%ExitConvertLoop:
        pop     edi
        pop     esi
        pop     ebx
%endmacro

%macro int2str 2
        push    ebx ;
        push    esi ;
        push    edi ;
        %%start:
        mov  eax, %1
        xor  ecx, ecx
        mov  ebx, 000ah
        %%DecConvert:
        xor  edx,  edx
        div  ebx
        add  edx,  0030h
        push edx
        inc  ecx
        or   eax,  eax
        jnz  short %%DecConvert
        mov  edi,  %2
        mov edx,ecx
        %%SortDec:
        pop   eax
        stosb
        loop  %%SortDec
        mov eax, 0h
        stosb
        pop     edi
        pop     esi
        pop     ebx
%endmacro
;;================================
;; mastercpp  end macros
;;================================

extern GlobalAlloc
import GlobalAlloc kernel32.dll

extern GlobalFree
import GlobalFree kernel32.dll

extern ExitProcess
import ExitProcess kernel32.dll

extern GetStdHandle
import GetStdHandle kernel32.dll

extern WriteFile
import WriteFile kernel32.dll

extern GetCommandLineA
import GetCommandLineA kernel32.dll


global ..start
segment .bss USE32

buffer resb 32


segment .data USE32
PrimeListHdl dd 0;
Root dd 0;
FoundFactor dd 0
input1 db "1000",0
value dd 0
consolehdl dd 0
byteswritten dd 0
noofprimes dd 0
newline db 10
newlineLEN equ 1

message1 db "Number of Primes = "
MSG1_LEN equ $-message1
message2 db "Usage : Sieve <integer>    ",13,10,"MAX 2^32 - 1 ",13,10
MSG2_LEN equ $-message2

segment .code USE32 class=code

..start:

; hStdOut = GetstdHandle( STD_OUTPUT_HANDLE)
push    dword STD_OUTPUT_HANDLE
call    [GetStdHandle]
mov     [consolehdl], eax   

;; Command line parsing - START
call [GetCommandLineA]
mov esi,eax

NextChar:
lodsb
cmp al,' '
jnz CheckNull
jmp SkipSpaces
CheckNull:
cmp al,0
jnz NextChar

;;; No Parameter - print usage text
push    dword 0
push    dword byteswritten
push    MSG2_LEN
push    dword message2
push    dword [consolehdl]
call    [WriteFile]

push dword 0
call [ExitProcess]

SkipSpaces:
lodsb
cmp al,' '
jz SkipSpaces

dec esi
;; Command line parsing - END
str2int esi


mov [value],eax

push eax
call IntegerLn   ;;calculate Integer Logarithm.
add esp,4

mov ebx,eax
mov eax, 2
test ebx,ebx
jz AllocateMemory
xor edx,edx
mov eax,[value]
div ebx  ;;; EAX stores the quotient of N/Ln(N)

AllocateMemory:
shl eax,1  ;;;Multiply by 2.   Just to make sure we have enough memory
imul eax,4 ;;;  N number of DWORDS

push eax
push dword GPTR
call [GlobalAlloc]
mov [PrimeListHdl],eax
mov edi,eax

mov ecx,2
StartDivisorLoop:
cmp ecx,[value]
jg ExitDivisorsLoop

push edi  ;;;  Save EDI
push ecx  ;;;  Save ECX


mov eax,ecx
push eax
call IntegerSqrt
add esp,4
inc eax
mov [Root],eax
mov dword[FoundFactor],0

pop ecx   ;;;  Restore ECX
pop edi

mov esi,[PrimeListHdl]
StartInnerLoop:
lodsd
test eax,eax
jnz CheckLessThanRoot
jmp CheckFoundFactor
CheckLessThanRoot:
cmp eax,[Root]
jge CheckFoundFactor

push ecx

xchg eax,ecx
xor edx,edx
div ecx

pop ecx

test edx,edx
jnz NotFactor
mov dword[FoundFactor],1
jmp CheckFoundFactor

NotFactor:
jmp StartInnerLoop
CheckFoundFactor:

cmp dword[FoundFactor],1
jz NotPrime
mov eax,ecx
stosd
NotPrime:
inc ecx
jmp StartDivisorLoop
ExitDivisorsLoop:

mov eax,0
stosd

mov esi,[PrimeListHdl]

xor ebx,ebx
PrintLoop:

        lodsd
test eax,eax
jz ExitOut
        int2str eax,buffer

pusha

; WriteFile( hstdOut, message, length(message), &bytes, 0);
push    dword 0
push    dword byteswritten
push    edx
push    buffer
push    dword [consolehdl]
call    [WriteFile]

; WriteFile( hstdOut, "\n", 2, &bytes, 0);
push    dword 0
push    dword byteswritten
push    dword 1
push    newline
push    dword [consolehdl]
call    [WriteFile]

popa
inc ebx
jmp PrintLoop

ExitOut:
mov [noofprimes],ebx

push    dword 0
push    dword byteswritten
push    MSG1_LEN
push    message1
push    dword [consolehdl]
call    [WriteFile]

int2str [noofprimes],buffer

push    dword 0
push    dword byteswritten
push    edx
push    buffer
push    dword [consolehdl]
call    [WriteFile]

push dword [PrimeListHdl]
call [GlobalFree]

push dword 0
call [ExitProcess]

IntegerLn:
push ebp
mov ebp,esp
xor ecx,ecx
mov eax,[ebp+8]

DivideBy2:
shr eax,1
test eax,eax
jz IntegerLn_exit
inc ecx
jmp DivideBy2

IntegerLn_exit:
mov eax,ecx
leave
ret

IntegerSqrt:
push ebp
mov ebp,esp

xor edi,edi
mov ebx,0x8000
mov ecx,15
startloop:
mov esi,edi
shl esi,1
mov edx,esi
add edx,ebx
shl edx,cl
dec ecx

cmp eax,edx
jl shiftrightb
add edi,ebx
sub eax,edx

shiftrightb:
shr ebx,1
cmp ebx,0
jg startloop
mov eax,edi
leave
ret

I have attached a version using nagoa macros too.
« Last Edit: February 09, 2012, 08:18:06 PM by Mathi »