• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

orium

Teste de primalidade

3 mensagens neste tópico

Acabei de escrever um teste de primalidade, implementado da maneira "ingenua", com umas pequenas optimizaçoes.

O codigo em si e' em assembly, mas esta "embebido" em C (caso contrario teria pouca utilidade pratica).

E' bastante rápido (não fosse escrito em assembly), quando o objectivo e' apenas saber se uma quantidade (+/-) pequena de numeros são primos.

Da' tambem para ter uma ideia de como se pode optimizar algumas funcoes de C usando assembly.

#include <stdbool.h>
#include <math.h>

bool
prime(int n)
{
bool r;
int sqrt_n;

if (n == 2)
	return true;

if (n < 2
    || !(n%2))
	return false;

/* All prime numbers above 3 are of form 6n-1 or 6n+1,
 * So...
 */
if (n > 3)
	if ((n-1)%6 
	    && (n+1)%6)
		return false;

sqrt_n=(int)ceil(sqrt(n));

asm("movb $1, %0\n"        /* r=true; */
    "movl $3, %%ebx\n"     /* count=3 */
    "start:\n"
    "cmpl %2, %%ebx\n"     /* if count > sqrt(n): */
    "jg end_prime\n"       /*     prime!!! */
    "movl $0, %%edx\n"     /* for the div */
    "movl %1, %%eax\n"     /* for the div */
    "divl %%ebx\n"         /* %edx=%edx:%eax mod %%ebx */
    "cmpl $0, %%edx\n"     /* if n%count == 0: */
    "je end_comp\n"        /*     composite!!! */
    "addl $2, %%ebx\n"     /* count+=2 */
    "jmp start\n"
    "end_comp:\n"
    "movb $0, %0\n"        /* r=false; */
    "end_prime:\n"
    :"=&r" (r)                 /* output */
    :"r" (n), "r" (sqrt_n) /* input */
    :"%eax", "%ebx",
     "%edx"                /* trashed */
	);

return r;
}

Considerem o codigo GPL3.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Só espero que não vás para as IOI's fazer optimizações em assembly  ;):)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora