Skip to content

Calcul de nombres premiers

February 9, 2010

Je m’intéresse aussi bien à Mike Brant qu’au calcul des nombres premiers. Sous JAVA, j’avais écrit un programme afin de calculer rapidement les nombres premiers. Son algorithme était assez simple: je calcule un nombre premier puis je le mémorise. Ensuite, pour tester les nombres premiers suivants, je tente la division par les nombres premiers calculés auparavant. Cette technique donne d’assez bon résultats.

Cependant, il existe beaucoup plus astucieux. Certains connaissent sûrement le crible d’Érastothène. Un algorithme est disponible en anglais sur un site américain dédié aux mathématiques (cliquez ici). Il permet de calculer très rapidement des nombres premiers. Le principal souci du crible est le calcul des premiers nombres (2, 3, 5, 7, etc.) qui demande un peu de temps. Sinon, le code en JAVA est extrêmement simple puisque la classe BitSet permet de stocker le crible facilement.

Le code généré est le suivant:

package com.oxande.primes;

import java.math.BigInteger;
import java.util.BitSet;

public class Eratosthenes {
 BitSet a = null;

 public BitSet calculateFor(int n) {
  BitSet a = new BitSet(n);
  a.clear(1);
  for (int i = 2; i < n; i++){
   a.set(i);
  }
  int p = 2;
  while ((p * p) < n) {
   int j = p * p;
   while (j < n) {
    a.clear(j);
    j = j + p;
   }

   do {
    p++;
   } while (!a.get(p));
 }
 return (a);
}

 public static void main( String[] args ){
   int n = 300000000;
   Eratosthenes appli = new Eratosthenes();
   BitSet a = appli.calculateFor(n);
   for( int i = 2; 1 < n; i++){
    if( a.get(i) ){
     System.out.println( i );
    }
   }
 }
}

L’astuce consiste bien entendu à stocker le crible sous la forme d’un tableau de bits représentant tous les nombres. Cette solution amusante est extrêmement économique, rapide et simple. Ainsi pour savoir si le nombre 953 est premier, on vérifie la 953ème position dans le champ de bits (100 octets permettent de stocker le criblage pour les nombres de 1 à 800).

Le tour est joué. Bien entendu, il s’agit de l’algorithme brut de décoffrage. En jouant sur la mémoire maximale de heap (-Xmx1G par exemple), on peut calculer les nombres premiers jusqu’à 2 milliard (231-1).

Avec un peu d’astuce, il est possible de calculer jusqu’à 4 milliard (232-1) en supprimant les nombres pairs (divisibles par deux): cela va permettre de diviser par deux l’espace de stockage donc permettre d’avoir 232 entrées dans le tableau de bits. Cela nous demande seulement 2Go divisé par 8 soit environ 256Mo de heap pour le calcul.

Mais bien des ordinateurs peuvent aller plus loin: la plupart des ordinateurs modernes possèdent 2 ou 4Go de mémoire vive (sans parler du swap). Donc un ordinateur classique pourra sans problème calculer tous les nombres premiers de 2 à 34 milliards. Pour cela, BitSet doit être modifié pour que l’index accepte un type long (au lieu de int). Pour cela, le plus simple est de créer une classe ExtendedBitSet qui permet de passer des valeurs de type long.

Pour créer cette nouvelle classe, la solution la plus simple n’est pas d’étendre la classe de base mais de l’utiliser en créant une classe qui va créer un tableau de BitSet. Le codage devient très simple comme le montre le code ci-dessous:

package com.oxande.primes;

import java.util.BitSet;

public class ExtendedBitSet {
	BitSet array[] = null;

	public static final long STORAGE_SIZE = (1 << 30);
	int blocks;

	public ExtendedBitSet(long n, boolean state) {
		int blocks = (int)(n / STORAGE_SIZE) + 1;
		array = new BitSet[blocks];
		for( int i = 0; i < array.length; i++){
			if( i == array.length - 1 ){
				int remaining = (int)(n - ((n / STORAGE_SIZE) * STORAGE_SIZE)) + 1;
				array[i] = new BitSet(remaining);
			}
			else {
				array[i] = new BitSet( (int)STORAGE_SIZE );
			}
			array[i].set(0, array[i].size(), state );
		}
	}

	private BitSet getBlock(long n){
		int blk = (int)(n / STORAGE_SIZE);
		return array[blk];
	}

    public void clear(long bitIndex) {
    	if (bitIndex < 0)
    	    throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    	getBlock(bitIndex).clear( (int)(bitIndex % STORAGE_SIZE) );
    }

    public void set(long bitIndex) {
    	if (bitIndex < 0)
    	    throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    	getBlock(bitIndex).set( (int)(bitIndex % STORAGE_SIZE) );
    }

    public boolean get(long bitIndex) {
    	if (bitIndex < 0)
    	    throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

    	return getBlock(bitIndex).get( (int)(bitIndex % STORAGE_SIZE) );
    }
}

L’initialisation permet de créer un tableau initialisé à 1 (true) ou 0 (false). Du coup, le calcul reste assez trivial comme le montre notre nouvelle classe ci-dessous. Vous remarquerez la prise en compte des nombres pairs dans les méthodes get(), set() et clear(): ainsi un octet permet de coder 16 nombres (on utilise la classe Eratosthene2 pour coder cette astuce afin que la classe de gestion de bit reste générique et puisse être réutilisé si nécessaire).

package com.oxande.primes;

import java.text.DecimalFormat;

public class Eratosthenes2 {

	ExtendedBitSet a;

	public void set( long i ){
		if( (i & 1L) == 1L ){
			a.set( (i-1) / 2 );
		}
		else {
			throw new IllegalArgumentException("can not clear even numbers");
		}
	}

	public boolean get( long i ){
		if( (i & 1L) == 0 ){
			if( i == 2 ) return true;
			return false;
		}
		return a.get( (i-1) / 2 );
	}

	public void clear( long i ){
		if( (i & 1L) == 1L ){
			a.clear( (i-1) / 2 );
		}
	}

	public void calculateFor(long n) {
		a = new ExtendedBitSet(n / 2 + 1, true );
		clear(1);

		long p = 3;
		while( (p*p) < n) {
			long j = p*p;
			while (j < n) {
				clear(j);
				j = j + p;
			}

			do {
				p++;
			} while (!get(p));
		}
	}

	public static void main( String[] args ){
		long n = 0x100000000L;
		Eratosthenes2 appli = new Eratosthenes2();
		appli.calculateFor(n);
		for( int i = 1; i < n; i++){
			if( appli.get(i) ) System.out.println( i );
		}
	}

}

Bien évidemment, on a considéré le crible d’Eratosthène au niveau mémoire vive. Or, il est extrêmement simple de sauvegarder nos BitSet sur disque (d’autant plus qu’ils sont accédés en séquence ce qui provoque une assez forte optimisation du code). Si on considère un disque actuel de 256Go utiles (une fois formaté), on peut donc calculer les nombres premiers de 2 à 256x1024x1024x1024x16 = 28+10+10+10+6 = 244 soit 17 592 186 044 416. Impressionnant, n’est ce-pas? Surtout pour un algorithme inventé vers -240 avant J.C.!

Une fois le crible déterminé, on peut savoir si un nombre contenu dans cette borne est premier ou non avec la lecture d’un seul octet sur le disque! Bien entendu, c’est surtout un exercice amusant à moins que votre but final soit de casser les clés RSA.
Pour le calcul des nombres de Mersenne, on pourra calculer les 8 premiers en peu de temps. En revanche, peu d’espoir de vérifier le dernier connu par cette méthode (243112609-1).

Cet article peut sembler bien ennuyeux pour ceux qui ne s’intéressent pas aux nombres premiers. Mais c’est surtout sur la partie optimisation que ce simple code JAVA présente un intérêt: il montre à quel point la variété des classes disponibles en JAVA permet d’implémenter rapidement des algorithmes et combien, à partir d’une idée simple, on arrive à une puissance incroyable. On rejoint par là, le concept Simpler is better déjà évoqué dans un précédent article.

Pour les gens intéressés, j’ai créé l’implémentation via un VirtualBitSet qui permet de stocker les images de bits sur disque sans utiliser de mémoire vive. La classe Eratosthene2 reste inchangée. Pour information, le premier passage pour calculer le criblage du nombre 3 prend environ 2 heures avec n = 103 079 215 104 (calcul sur un espace disque de 6Go) ce qui est tout à fait correct pour une machine comme la mienne.

Advertisements

From → Other

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: