Uma otimização interessante para testar se um valor é primo

[fredericopissarra]

Artigo original: https://is.gd/sDQ7Oa

Esse é um dos exercícios mais comuns na área acadêmica: Dizer se um número é primo ou não. Existe a maneira tradicional, a maneira rápida e a maneira super rápida… As duas primeiras eram minhas velhas conhecidas e já falei delas aqui, eis um resumão:

O método tradicional é dividir todos os valores inferiores ao número n, sob teste, até chegarmos a 2 e se o resto de qualquer uma das divisões der zero, isso indica uma divisibilidade e, portanto, o valor não é primo:

int isPrime( unsigned int n )
{
  unsigned int i;
 
  // casos especiais... 3 e 2 são primos, mas 1 e 0 não são!
  if ( n <= 3 )
    return ! ( n < 2 );
 
  for ( i = 2; i < n; i++ )
    if ( ( n % i ) == 0 )
      return 0;
  
 return 1;
}

O método rápido reduz o a quantidade de iterações do loop porque só precisamos verificar a divisibilidade de valores inferiores ou iguais à raiz quadrada de n. Isso é baseado na propriedade comutativa e do princípio fundamental da aritmética: 2*3 é a msma coisa que 3*2, então não precisamos testar os dois casos. Ainda, qualquer valor pode ser fatorado em primos… Outro detalhe importante para o teste é que só existe um valor par primo: 2, todos os demais são ímpares:

int isPrime( unsigned int x )
{
  unsigned int i, s;
 
  if ( n <= 3 )
    return ! ( n < 2 );
 
  // Apenas 2 é um valor par primo!
  if ( n % 2 == 0 ) 
    return 0;

  // Só precisaremos testart até a raiz quadrada...
  s = sqrt(n);
 
  // Não precisamos testar a divisibilidade por nenhum valor par.
  for ( i = 3; i <= s; i += 2 )
    if ( ( n % i ) == 0 )
      return 0;
 
  return 1;
}

Quando você acha que achou o código mais rápido possível algum detalhe te supreende. O código acima pode ser acelerado um bocado se pensamos que se o valor n é divisível por 6, então ele é divisível por 3 e por 2 e, portanto, não é primo. De outro modo, podemos retirar valores que, divididos por 6, resultam em restos 2, 3 ou 4, já que, com toda certeza, eles não são primos (ou são divisíveis por 2 ou 3):

int isPrime(unsigned int n)
{
  unsigned int i, s;
 
  if (n <= 3)
    return ! ( n < 2 );
 
  // Mais um caso especial... Se for divisível por 2 ou 3, não é primo!
  if ( ( n % 2 ) == 0 || ( n % 3 ) == 0)
    return 0;
  
  s = sqrt(n);
  
  for ( i = 5; i <= s; i += 4 )
  {
    if ( ( n % i ) == 0)
      return 0;
 
    i += 2
 
    if ( ( n % i ) == 0)
      return 0;
  }
 
  return 1;
}

O código acima executa o loop cerca de 3 vezes mais rápido que o código anterior e é matematicamente correto. Claro, existe o problema de que duas divisões são feitas no loop, mas o compilador tende a otimizar isso…

PS: Lembrando que existe um outro método, rápido, mas que consome muita memória: Trata-se do “Crivo de Eastótenes” que encontra os valores primos tentando as divisões com os valores primos anteriormente encontrados (até a raiz quadrada de n, como acima)… O “Crivo” é o método mais rápido, mas como eu disse, tem o potencial de consumir MUITA memória, porque precisamos manter um array com os valores previamente encontrados.

[fredericopissarra]

PS: Eu não pensei nesse terceiro método. Ele me foi apresentado num forum, onde duvidei bastante da "correção" matemática dele. Mas, acaba que o troço tá certo mesmo... Vivendo e aprendendo...

[trevizan]

Em 02/11/2019 em 11:10, fredericopissarra disse:

PS: Eu não pensei nesse terceiro método. Ele me foi apresentado num forum, onde duvidei bastante da "correção" matemática dele. Mas, acaba que o troço tá certo mesmo... Vivendo e aprendendo...

Muito interessante, acho que consigo explicar como funciona de uma forma complementar.

 

Esse algoritmo pula os ímpares múltiplos de três no momento que incrementa quatro no contador (i+=4) , a partir do número nove, visto que a divisibilidade por três já foi testada.

 

Desta forma:

testa o 5; // valor inicial

testa o 7; //após incrementar i+=2

pula o 9; //ao incrementar i+=4

testa o 11; //após incrementar i+=4

testa o 13; //após incrementar i+=2

pula o 15; //ao incrementa i+=4

testa o 17; //após incrementar i+=4

testa o 19; //após incrementar i+=2

pula o 21; //ao incrementa i+=4

... e assim por diante.

Note que comparado a abordagem que você descreveu anteriormente, em um ciclo de três testes (if ( ( n % i ) == 0) ) um teste é eliminado . Assim, é possível eliminar 1/3 dos testes a serem executados.

[bratergames]

Poxa eu achei o Tio Fred de novo...eu tava no grupo do facebook dele e voltei a estuar comp esse semestre agora estou apenas nos mips da vida.

Muito bom te achar aqui tio fred.

[fredericopissarra]

Já eu, @bratergames, nunca parei de estudar e estou com os ARM da vida, mas não "apenas"... ?
Tio Fred só sumiu do facebook (nunca mais entro naquela bosta) e do discord do mente binária...

[trevizan]

Olás!

Fiquei pensando como seria estender a estratégia de eliminar os testes de ímpares múltiplos de três para também eliminar os testes dos múltiplos de cinco.

Cheguei ao seguinte algoritmo. Este executa cerca de 13% mais rápido que o algoritmo anterior e cerca de 47% mais rápido que o algoritmo que só considera a raiz quadrada.

int isPrime(unsigned int n)
{
  unsigned int i, s;

  if (n <= 5)
    return (n  == 2 || n == 3 || n == 5);

 
  // Mais um caso especial... Se for divisível por 2, ou por 3, ou por 5, não é primo!
  if ( ( n % 2 ) == 0 || ( n % 3 ) == 0 || ( n % 5 ) == 0)
    return 0;

  s = sqrt(n);


  for ( i = 7; i <= s; i += 6 )
  {

    if ( ( n % i ) == 0)
      return 0;
   
    i += 4;
    if ( ( n % i ) == 0)
      return 0;
  
    i += 2;
    if ( ( n % i ) == 0)
      return 0;
  
    i += 4;
    if ( ( n % i ) == 0)
      return 0;
  
    i += 2;
    if ( ( n % i ) == 0)
      return 0;
  
    i += 4;
    if ( ( n % i ) == 0)
      return 0;
  

    i += 6;
    if ( ( n % i ) == 0)
      return 0;
  
    i += 2;
    if ( ( n % i ) == 0)
      return 0;
  
  }
 
  return 1;
}

 

[fredericopissarra]

Well... Talvez, temos que verificar (a validade do algoritmo anterior é um cadinho mais complicada do que eu postei - desse ai, eu não sei)...
Mas, de qualquer maneira, temos que parar em algum lugar, não? Senão o algoritmo degenera para o crivo de Erastótenes.

[trevizan]

Basicamente eu vi quais valores  precisavam ser testados (os que não eram múltiplos de 2, 3 ou 5) a partir do número 7 e notei que essa sequência de incremento se repetia (como um padrão):

4, 2, 4, 2, 4, 6, 2 e 6.

Validei os resultados de 2 a pouco mais de 32 mil e não apresentou nenhum  retorno incorreto para o intervalo. 

 

Enfim,  o problema é que a complexidade de todos esses algoritmos ainda é da ordem de grandeza de raiz quadrada de n, ou seja,  ainda é alta.

 

Eu preciso estudar melhor o crivo de Erastótenes para opinar,  mas a primeira vista a abordagem me parece bem diferente e o ganho de desempenho não compensa a limitação de valor máximo que pode ser testado.

Daí talvez seja mais interessante brincar com coisas mais sérias, como o teste de Fermat ou AKS, que apresentam complexidade logarítmica.

[fredericopissarra]

Não estou dizendo que sua aproximação está errada ou que seja ruim. Só o que estou dizendo é que, talvez, ela possa falhar em algum momento. Limitar os testes a uma faixa que "dá certo" não quer dizer que o algoritmo vai funcionar para toda a faixa... A otimização que postei (que não foi minha, vi num forum e achei interessante) funciona para qualquer valor N, inteiro, de qualquer precisão...

O sujeito que bolou isso percebeu que quando um valor é primo e é maior que 4, ele pode ser expresso por 6n+/-k (onde k={0..5}, ou seja, k=n mod 6)... mas, k não pode ser 0, 2, 3 ou 4 (senão teremos valor par [k=0,2,4] ou divisível por 3 [k=3]). Assim, k só pode ser 1 ou 5. Agora, tomemos n=1 e obteremos 5 (6*1-1) e 7 (6*1+1), e 1 (6*1-5) e 11 (6*1+5). Esses são candidatos a primazia... Se você fizer n=2 (n+1), teremos 11 (6*2-1), 13 (6*2+1), 7 (6*2-5) e 17 (6*2+5). Claramente (e podemos comprovar isso por congruência) testes com k=5 são cobertos pelos mesmos testes onde k=1 e podemos descartar k=5.

Dai, o testes de primazia só precisam ser feitos com 6n-1 e 6n+1. Por isso o loop começa em 5, avançamos k em 2 unidades (de -1 para +1), testamos o próximo e testamos de novo... avançamos 4 unidades (por causa do 6n) e fazemos tudo de novo...

O que descrevi acima é uma prova por "indução matemática" e é garantido que o resultado seja o mesmo para qualquer N... Teríamos que provar, de maneira semelhante, que sua aproximação é válida para qualquer N inteiro positivo e é isso que eu não tenho certeza (porque não pensei à respeito) que esteja correto.

Quanto ao crivo de Erastótenes. Basicamente ele realiza as divisões apenas com os valores prímos previamente encontrados, no loop, mas precisa armazená-los num grande array. Esse é o método mais "rápido" (e um pouquinho mais complicado), mas potencialemente usa muita memória para isso. No caso, mesmo não usando arrays, a cadeia de testes ficaria muito grande e é bom lembrar que cada divisão é LENTA. Uma rotina com 2 divisões não é cria lá grande perda de velocidade, mas uma com 8 divisões dentro do loop tem o potencial de ser bem lenta.

[[]]ão
Fred

[jweyrich]

Pra quem gosta desse desafio, recomendo dar uma olhada (ou estudada) num algoritmo chamado "Sieve of Eratosthenes".

Acho que ainda é a implementação mais rápida para teste de primalidade. Ele usa essa a técnica descrita pelo Fred e expande com algumas outras.

Bastante teoria dos números e fatoração!

Dei uma leve estudada nesse algoritmo quando precisei estudar (quebra de) criptografia e "de quebra" acabei em fatoração pesada, gcd, etc. Cheguei a sonhar com uma idéia de quebrar os certificados digitais gerados pela openssl. Aí eu acordei! haha :D No mês seguinte publicaram um bug no OpenSSH relacionado à constante RSA_F4 :O

De qualquer forma os insights foram muito valiosos.

[fredericopissarra]

O "crivo de Erastótenes" é um dos mais antigos algoritmos para teste primazia (século II A.E.C.). O teste anterior, diferente do crivo, não exige armazenamento temporário (array). O uso de um array é ruim para testes com valores muito altos. Claro, estou falando do algoritmo original.