Sums and Products of Primes - solution (FR)

Sums and Products of Primes - solution (FR)

Sums and Products of Primes - solution (FR)

Mihai Moraru Thibaut Patel

22 mai 2011

1 Objectif

Pour ce second problème, nous devons chercher un produit de k nombres premiers consécutifs qui est égal à un delta près à une somme de k autres nombres premiers consécutifs.

Nous avons compris peu après le début de notre travail qu’il était impossible de fournir une solution qui terminait dans un temps raisonnable pour toutes les entrées possibles (contrairement au premier problème du concours). Cela nous a poussé à choisir plusieurs jeux de tests pour pousser les performances de notre solutions sur différents aspects.

Nous avons ensuite dégagé quelques cas limites : par exemple k ne peut être supérieur ou égal à 16, sinon le produit dépasse 264.

 

2 Solution développée

D’un point de vue général, nous proposons une solution qui utilise une fenêtre glissante sur les k-produits. À partir d’un k-produit, nous cherchons les k-sommes qui sont suffisamment proches du k-produit.

Pour rechercher ces sommes, on trouve la borne inférieur par le calcul suivant :

formula1.png

On cherche les k-1 nombres premiers supérieurs à BorneInf, ce qui nous permet de remplir notre buffer cyclique. On parcours alors les nombres premiers en se déplaçant vers les nombres plus petits (à gauche) puis vers les nombres plus grands (à droite). De chaque côté, on s’arrête dès que :

formula2.png

3 Test de primalité

Un des points les plus importants est d’avoir un test de primalité déterministe et rapide. Nous avons donc utilisé une suite de tests dans le but d’optimiser notre preuve de primalité. À la fin de chaque étape, on sait si le nombre est composé ou probablement premier, jusqu’à la dernière étape qui prouve la primalité d’un nombre.

  • On commence par tester successivement la division par les N premiers nombres premiers (ces nombres sont calculés au lancement du programme).
  • Ensuite si le nombre est suffisamment petit, on utilise des tests dits « a-SPRP » (strong probable-prime base a). Nous avons trouvé une publication prouvant cette méthode (http ://priv.ckp.pl/wizykowski/ sprp.pdf).
  • Ensuite nous souhaitons éliminer un maximum de nombres non premiers, dans le but de gagner du temps de calcul. Nous utilisons donc le test de Miller Rabin, pour n’avoir à l’étape suivante que des nombre probablement premiers.
  • Enfin, nous réalisons un test simple et déterministe, c’est à dire que pour chaque nombre entre 2 et la racine carrée du nombre à tester, on teste si la division donne un entier.

 

4 Améliorations du test de primalité envisageables

Nous avons disposé de beaucoup moins de temps pour ce problème que pour le précédent (à cause de la période d’examens de l’INSA), nous avions donc quelques idées que nous n’avons pas eu le temps d’implémenter complètement.

Concernant le test de primalité, nous nous sommes penchés sur le seul test déterministe en temps polynomial qui existe à nos jours : AKS. Nous avions commencé à l’implémenter mais faute de temps nous n’avons pas pu développer la partie concernant la gestion des polynômes.

Une autre idée était de remplacer tous les tests par l’algorithme BPSW dont l’efficacité a été prouvée expérimentalement pour des nombres inférieurs à 264. Mais cela impliquait d’implémenter en plus l’algorithme de Lucas-Selfridge.

5 Parallélisation

Nous avons utilisé la librairie TBB car elle nous avais satisfait au premier problème, cela nous permet de gagner du temps de développement en utilisant la même bibliothèque ainsi que la même structure (Body/Range).

Avec la parallélisation de notre programme, nous avons du faire attention à l’écriture à l’écran. En effet, les threads écrivent directement sur stdout, sans passer par une structure de donnée (ce que nous avions fait pour le premier programme). Nous avons pour cela utilisé un mutex. Il s’est avéré que l’utilisation d’un mutex qui se débloque une fois qu’il sort de sa portée est plus user-friendly qu’avec la programmation système Linux ou VxWorks.

Il nous a fallu aussi changer notre algorithme de base pour prendre en compte les séquence qui se situe à cheval entre deux intervalles. En effet, notre implémentation découpe l’espace de recherche en plusieurs intervalles traités en parallèle.

Per informazioni complete sulle ottimizzazioni del compilatore, consultare l'Avviso sull'ottimizzazione