Teste de desempenho com números primos em C [C/C++]

Teste de desempenho com números primos em C

Publicado por Andre Miguel (última atualização em 12/07/2011)

[ Hits: 9.458 ]

Download primos.c

Download 1291342736.primos_time_ext_17.c (versão 2)

0 0

Denuncie Favoritos Indicar

Estendendo o assunto de teste de desempenho com números primos em BASH que publiquei antes http://www.vivaolinux.com.br/script/Teste-de-desempenho-com-numeros-primos-em-BASH
tive um tempinho e codifiquei também em C.

Desta vez não compilei no SO do servidor, mas em desktop Windows com GCC mesmo.

No período de quase uma hora rodando num Celeron D com 1 GB de memória, obtive UM resultado:

Primo 1410065413
Primo 1410065441
Primo 1410065443

O Desktop apresenta alguns momentos de "stall", travamento, mas bem de leve. Tipo ao digitar demora pra sair do buffer.

Vou compilar no servidor e executar com `time` como fiz com o BASH.

Testem o desempenho e divirtam-se!

Versões atualizadas deste script

Versão 2 - Enviado por Andre Miguel em 03/12/2010

Changelog: Segue atualização do programa de primos em C.

Quem baixou a primeira versão: http://www.vivaolinux.com.br/script/Teste-de-desempenho-com-numeros-primos-em-C e teve paciência de deixar rodando horas até achar um primo de 11 dígitos, percebeu que dava um pau de especie de "estouro de buffer" de variável, fazendo o resultado a ser expresso com 11 dígitos, retornar apenas 10.

Após 9 meses (nasceu ^.^!) fiz a correção. isso se devia ao fato de tratar variáveis (long long int) como simplesmente (int), sem querer. Explico. Se você incrementar com ++ ou decrementar com -- o GCC estava assumindo como (int), mesmo operando sobre (long long int), o que me fez alterar para, por exemplo, "j=j-1LL".

Versão do GCC: gcc version 4.4.1 [gcc-4_4-branch revision 150839] (SUSE Linux)
Versão da GLIB: glibc-2.10.1-10.4.i686

Fiz uns incrementos com as funções da time.h e timeb.h para retornar o tempo passado a cada iteração em segundos. Coloquei alguns comentários no código-fonte e um helpzinho esdrúxulo.

NOTA: a intenção não é necessariamente ser eficiente (como tal é o propósito da TI), mas estressar a utilização de uma máquina, por meio de iterações matemáticas simples e sucessivas e debugar possíveis gargalos, tipo cache, mesmo o processador, enfim, tudo que possa causar latência em retornar processamento crítico, concorrente ou de sistemas de tempo-real REALMENTE críticos e tal.

Tente rodar com strace, com parâmetros parecidos com o truss do Solaris:

strace -failedD ./exec_primos_time_ext_17 1 10

# Sim, foi a décima-sétima tentativa de fazer funcionar o programa direito :P

Exemplo resumido do que consegui num Intel i5:
Primo 10000000019 diff:49.1974500 min ts ini:1290431045.656 ts fim:1290433997.503
Primo 10000000033 diff:34.7964667 min ts ini:1290433997.503 ts fim:1290436085.291
Primo 10000000061 diff:68.3464667 min ts ini:1290436085.291 ts fim:1290440186.079
Primo 10000000069 diff:18.9710000 min ts ini:1290440186.079 ts fim:1290441324.339
Primo 10000000097 diff:67.2385000 min ts ini:1290441324.339 ts fim:1290445358.649
Primo 10000000103 diff:14.8446833 min ts ini:1290445358.649 ts fim:1290446249.330
Primo 10000000121 diff:44.4549333 min ts ini:1290446249.330 ts fim:1290448916.626
Primo 10000000141 diff:48.9059500 min ts ini:1290448916.626 ts fim:1290451850.983
Primo 10000000147 diff:14.5078667 min ts ini:1290451850.983 ts fim:1290452721.455

Postem aí o que conseguiram. Depois postarei o que consegui em alguns servidores mais parrudos...

Abraços.

Download 1291342736.primos_time_ext_17.c

Esconder código-fonte

#include <stdio.h>
int main(){
  int j, primo = 0;
  unsigned long i=0;
  
  for ( i=10000000000; i <= 999999999999; i++){
//  for ( i=10; i<=99; i++ ){
    j=i;
    primo=0;
    for ( j=i; j>=1; j-- ){
      if ( i%j == 0 ){
        primo++;
        if ( primo > 2 ){
          j=1;
        }
        else{
          if ( primo == 2 && j == 1 ){
            printf("Primo %d\n", i);
          }
        }
      }
    }
  }
}

Scripts recomendados

Fazendo o somatório de 1 até N

Lista encadeada em C

inputAst

Super Thiagout (Breakout) - O Jogo

Usando medidas de comprimento

Comentários

[1] Comentário enviado por elgio em 18/03/2010 - 09:23h

#include <stdio.h>
#include <math.h>

/* Compilar com gcc -lm prog.c -o prog
*
* -lm: linkar biblioteca math
* */
int main()
{
unsigned long int j, fim, primo;
unsigned long i = 0;

for (i = 1000000000; i <= 99999999999; i++) {
fim = 1;
if ((i&1) == 0){ // numero par não é primo, exceto o 2
continue;
}

fim = (int)sqrt((double)i); // se não tiver divisor até a raiz quadrada, é primo
fim = (fim+1) | 1; // transformando o fim em IMPAR, se não era

primo = 1;
for (j = 3; j <= fim; j+=2) {
/* laço vai até raiz quadrada e só tenta divisore impares*/

if ((i % j) == 0) {
primo=0;
break; // não é primo, pois divide por j. Aborta o laço
}
}
if (primo) {
printf ("Primo %u\n",i);
}
}
}

Em um processador 64 bits 2.5Ghz, para achar o primeiro primo
- tua versão: 46 segundos
- esta versão: menos de 1 segundo

Veja, se ao dividir observa-se que o numero divide por 5, acabou!
Porque perder tempo tentando por 6, 7, 8, ... se já se sabe que ele não é um número primo?

0 0

[2] Comentário enviado por uberalles em 18/03/2010 - 15:47h

excelente, amigão! vou usar o seu e retorno.
Valeu.

e pessoal, só uma desatenção minha: o segundo número não tem 11 dígitos, mas 12 :(
10000000000
999999999999

0 0