; Program liczy liczby pierwsze w przedziałach 2-10, 2-100, ..., 2-100.000 ; ; Autor: Bogdan D. ; kontakt: bogdandr (at) op (dot) pl ; ; kompilacja: ; ; nasm -f elf ile_pier.asm ; ld -s -o ile_pier ile_pier.o ; ; Copyright (C) 2005-2007 Bogdan 'bogdro' Drozdowski, bogdandr @ op . pl ; ; Ten program jest wolnym oprogramowaniem; mozesz go rozpowszechniac ; i/lub modyfikowac zgodnie z licencja GNU Lesser General Public License ; (GNU LGPL) w wersji wydanej przez Fundacje Wolnego Oprogramowania; ; wedlug wersji 3 Licencji lub (jesli wolisz) jednej z pozniejszych wersji. ; ; Ten program jest udostepniany z nadzieja, ze bedzie uzyteczny, lecz ; BEZ JAKIEJKOLWIEK GWARANCJI; nawet domyslnej gwarancji PRZYDATNOSCI ; HANDLOWEJ albo PRZYDATNOSCI DO OKRESLONYCH ZASTOSOWAN. W celu uzyskania ; blizszych informacji - Licencja GNU Lesser General Public License. ; ; Z pewnoscia wraz z niniejszym programem otrzymales tez egzemplarz ; Licencji GNU Lesser General Public License; jesli nie - napisz do ; Fundacji Wolnego Oprogramowania: ; Free Software Foundation ; 51 Franklin Street, Fifth Floor ; Boston, MA 02110-1301 ; USA section .text global _start _start: ; poczatek... xor ebx, ebx ; EBX = liczba, ktora sprawdzamy, czy ; jest pierwsza. Zaczynamy od 3. Ponizej jest ; 3 razy "inc" (zwieksz o 1). Najpierw ; EBX=0, bo "xor rej,rej" zeruje dany rejestr xor edi, edi ; EDI = biezacy licznik liczb pierwszych xor ecx, ecx ; ECX = stary licznik liczb (z poprzedniego ; przedzialu). Chwilowo, oczywiscie 0. inc ebx ; EBX = 1 mov esi, 10 ; ESI=biezacy koniec przedziału: 10, 100, itd inc edi ; EDI=1. uwzgledniamy 2, ktora jest ; liczba pierwsza inc ebx ; EBX=2, pierwsza liczba bedzie = 3 petla: ; petla przedzialu cmp ebx, esi ; czy koniec przedzialu? (ebx=liczba, ; esi=koniec przedzialu) jae pisz ; EBX >= ESI - idz do sekcji ; wypisywania wynikow mov ebp, 2 ; EBP - liczby, przez ktore bedziemy dzielic. ; pierwszy dzielnik = 2 inc ebx ; zwiększamy liczbę. EBX=3. Będzie to ; pierwsza sprawdzana spr: ; petla sprawdzania pojedynczej liczby mov eax, ebx ; EAX = sprawdzana liczba xor edx, edx ; EDX = 0 div ebp ; EAX = EAX/EBP (EDX byl rowny 0), ; EDX=reszta z dzielenia or edx, edx ; instrukcja OR tak jak wiele innych, ; ustawi flagę zera ZF ; na 1, gdy jej wynik byl zerem. ; W tym przypadku pytamy: czy EDX jest zerem? jz petla ; jezeli dzieli się bez reszty (reszta=EDX=0), ; to nie jest liczba pierwsza ; i należy zwiekszyc liczbe sprawdzana (ebx) inc ebp ; zwiekszamy dzielnik cmp ebp, ebx ; dzielniki az do liczby jb spr ; liczba > dzielnik - sprawdzaj dalej ta ; liczbe. Wiem, że mozna bylo sprawdzac tylko ; do SQRT(liczba) lub LICZBA/2, ale ; wydluzyloby to program i brakowalo mi juz ; rejestrow... juz: ; przerobilismy wszystkie dzielniki, zawsze ; wychodzila reszta, ; wiec liczba badana jest pierwsza inc edi ; zwiekszamy licznik liczb znalezionych jmp short petla ; sprawdzaj kolejna liczbe az do konca przedzialu ;=========================================== ; sekcja wypisywania informacji pisz: push ebx ; zachowujemy modyfikowane a wazne rejestry push ecx mov eax, 4 mov ebx, 1 mov ecx, przedzial mov edx, dlugosc_przedzial int 80h ; wypisujemy informacje o przedziale mov eax, esi ; EAX=ESI=koniec przedzialu call _pisz_ld ; wypisz ten koniec (EAX) mov eax, 4 mov ebx, 1 mov ecx, dwuk mov edx, 1 int 80h ; wypisujemy dwukropek pop ecx add ecx, edi ; dodajemy poprzednia ilosc znalezionych ; liczb pierwszych mov eax, ecx ; EAX = ilosc liczb pierwszych od 2 do ; konca biezacego przedzialu call _pisz_ld ; wypisujemy te ilosc. pop ebx ;=========================================== cmp esi,100000 ; 10^5 jb dalej ; ESI > 100.000? Tak - koniec, ; bo dalej liczy zbyt dlugo koniec: mov eax, 4 mov ebx, 1 mov ecx, przedzial mov edx, 1 int 80h ; wypisujemy znak nowej linii xor ebx, ebx ; kod wyjscia = 0 mov eax, 1 int 80h ; wyjscie z programu dalej: mov eax, esi ; EAX=ESI shl eax, 3 ; EAX = EAX*8 shl esi, 1 ; ESI=ESI*2 add esi, eax ; ESI = ESI*2 + EAX*8 = ESI*2 + ESI*8=ESI*10. ; Znacznie szybciej niż "MUL" xor edi, edi ; biezacy licznik liczb jmp petla ; robimy od poczatku... ;************************************** _pisz_ld: ;we: EAX=liczba bez znaku do wypisania push ebx push ecx ; zachowujemy modyfikowane rejestry push edx push eax push esi xor esi, esi ; SI=0. Bedzie wskaznikiem w ponizszy bufor. mov ecx, 10 ; bedziemy dzielic przez 10, aby uzyskiwac ; kolejne cyfry. Reszty z dzielenia pojda do ; bufora, potem beda wypisane wspak, bo ; pierwsza reszta jest przeciez cyfra jednosci _pisz_ld_petla: xor edx, edx ; EDX=0 div ecx ; EAX = EAX/ECX, EDX = reszta, ktora miesci ; sie w DL, bo to jest tylko jedna ; cyfra dziesietna. or dl, '0' mov [_pisz_bufor+esi], dl ; Cyfra do bufora. inc esi ; Zwieksz numer komorki w buforze, do ktorej ; bedziemy teraz pisac or eax, eax ; EAX = 0 ? jnz _pisz_ld_petla ; Jesli nie (JNZ), to skok do poczatku petli _pisz_ld_wypis: mov eax, 4 mov ebx, 1 lea ecx, [_pisz_bufor+esi-1] mov edx, 1 int 80h dec esi ; zmniejsz wskaznik do bufora. jnz _pisz_ld_wypis ; Jesli ten wskaznik (SI) nie jest zerem, ; wypisuj dalej pop esi ; odzyskaj zachowane rejestry pop eax pop edx pop ecx pop ebx ret ; powrot z procedury ;************************************** section .data _pisz_bufor times 20 db 0 ; miejsce na cyfry dla procedury przedzial db 10,'Przedzial 2-' dlugosc_przedzial equ $ - przedzial dwuk db ':'