Discussion :

[Invité]

Bonjour à toutes et à tous,

J'ai a décomposer des nombres (sur 32 bits, non-signés, c'est en C : unsigned int) en grande quantité (en pur C). Au début je faisais une boucle qui testait tout les nombres premiers jusqu'à sqrt(n), bref, la solution sale retenu a été de compiler une grosse fonction avec tous les nombres jusqu'à sqrt(2^32) avec la macro suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
#define DEC(a) while ( !(nb % a) ) {nb /= a; dest[i++] = a;} if (nb < a*a) {if(nb > 1) dest[i++] = nb; return i;}

Equivalent a :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
#define DEC(a)
while ( !(nb % a) )
{
    nb /= a;
    dest[i++] = a;
}
if (nb < a*a)
{
    if(nb > 1)
         dest[i++] = nb;
    return i;
}

Même si le gain de temps a été substantiel (je suis passé de 19 minutes à 5 minutes sur un Intel Centrino 2,10 GHz avec deux coeurs et deux threads pour 1 millions d'éléments) je voudrait savoir s'il n'y a pas un moyen de diminuer le nombre de nombres testés ? existe-t-il des théorèmes sur le sujet qui diminuerait le nombre de candidats potentiels ?

Pour votre aide,
Par avance,
Merci.

[kwariz]

Salut,

il existe différents algorithmes pour décomposer un entier en facteur premier : cf http://en.wikipedia.org/wiki/Integer...ation#See_also external links, ou http://en.wikipedia.org/wiki/Pollard's_rho_algorithm (jeter un oeil en bas de page) pour avoir quelques débuts de pistes.

Sinon si tu tiens à garder ton algo et si le a parcourt les premiers alors je ne vois pas trop ... 2^16 reste abordable.

Si ton a ne parcourt pas les premiers, le plus simple est sans doute de ne prendre que 2 et tester les 2n-1, -> tu ne testes que 1/2=50%
ou 2,3 puis 6n+/-1, -> tu ne testes que 2/6=33%
ou d'une manière plus générale mais plus longue 2,3,5, [7,11,13,17,19,23,29], puis 30n+{1 plus les premiers de la liste entre crochets}, -> 8/30= 26.7%
cela peut aisément se généraliser plus loin et se tuner au mieux ...
Tu prends le nombre P=produit de i=1 à n de pn, où pn est le nième nombre premier (p1=2), tu testes avec chaque premier < P, puis P*k+1 puis P*k+(chaque premier entre p(n+1) et P)
avec P=2x3x5x7=210, tu as 46 premiers < 210, tu auras une liste qui te fera tester (46-4+1)/210=20.5% soit 2.5 fois moins (en gros) que tester que les impairs
...

[pseudocode]

la solution sale retenu a été de compiler une grosse fonction avec tous les nombres jusqu'à sqrt(2^32) avec la macro suivante

Ca doit faire pas mal de mémoire consommée. Autant carrément y stocker l'arbre de décomposition des entiers 32bits.

[kwariz]

Non ça n'en fait pas tant que ça ... Il faut stocker les nombres premiers jusqu'à 2^16=65536, il y en a dans les 7000 a peu près, avec des entiers sur 32 bits ça fait moins de 60ko.

[Invité]

Bonjour,

Merci de vos réponses.
kwariz j'ai regardé du côté de Pollard (et de brent par extension) j'ai tenté quelques implémentations il se trouve que les algos sont plus lent que mon premier algo.

pseudocode il y en a exactement 6542 et, même compilé l'exécutable prends 80 ko de mémoire vive et ne pèse "que" 784 ko, c'est acceptable. Par contre ta question (et la réponse de kwariz) on retenu mon attention : les nombres que j'avais générés n'étaient pas tous premiers. Bref, en refaisant un générateur correcte je suis tombé à 8 secondes ce qui est déjà beaucoup plus acceptable.

kwariz ton dernier paragraphe m'intrigue.

Voici ce que je comprends :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
nps : liste des nombres premiers
P = 1
Pour k de nps
    P = P*k
    i = 1
    TantQue nps[i] < P+1
        Test avec nps[i]
    FinTantQue
Fin Pour

En fait je me suis embrouillé, aurais-tu la gentillesse de ré-expliquer, j'avoue que je suis un peu limité.

Par avance,
Merci.

[kwariz]

Oui ... parfois quand je réponds tard je ne suis pas très clair
J'espère l'être un peu plus maintenant.

En fait on part sur des algos par division (qui sont plus ou moins un équivalent de crible).

Tout d'abord, ton algo qui utilise une liste complète des nombres premiers inférieurs à 2^16 est optimal pour décomposer par divisions des nombres inférieurs à 2^32.

Si tu devais décomposer des entiers de 64bits par exemple, il faudrait que tu stockes dans les 240.10^6 de nombres premiers inférieurs à 2^32 (à 32bit l'entier ça te fait dans les un peu moins de 1Go le tableau, à 64bit l'entier le double ), cela est encore faisable avec les capacités actuelles mais devient un peu limite (quoique, mais le plus long sera de générer cette liste).

Donc au lieu de tester séquentiellement avec les "vrais" nombres premiers on va se contenter d'une liste qui va tous les contenir, mais aussi en contenir d'autres qui ne seront pas premiers, avec l'idée que cette liste est générable très facilement à la demande (enfin plus facilement que de chercher le premier suivant).

La plus simple de ces listes est tout simplement la liste des entiers. Pas très efficace ...
On peut se dire, tous les premiers sont impairs sauf 2, donc on teste avec 2, puis on ne teste plus que les nombres n=2*k+1 -> sur on ne teste plus que 1 nombre sur 2 au lieu de tous : on "gagne" 50%
On peut faire mieux en remarquant qu'un nombre premier plus grand que 6 est obligatoirement de la forme 6k+1 ou 6k+5 (dans la littérature on trouve souvent 6k+1 et 6k-1, comme 5=-1 mod 6). Donc le test devient : on teste avec 2,3,5 (le premiers plus petits que 6), puis les nombres de la forme 6k+1 et 6k+5. L'idée est de remarquer qu'il y a comme un motif ...
On prend 6=2x3, on teste avec 2,3,5 : les premiers plus petits que 6, puis on a une liste de nombres de la forme 6k+1 et 6k+5 : on fait 6k plus 1 et plus tous les premiers plus petits que 6 et plus grands que les diviseurs premiers de 6={2,3}.
Que se passe-t-il alors avec 30 ? 30=2x3x5 (dans la littérature on trouve l'appelletion primorielle : factorielle avec les nombres premiers)
Même motif :
30=2x3x5
première phase on détermine la liste des premiers plus petits que 30 :
L=2,3,5,7,11,13,17,19,23,29, je souligne ceux qui sont plus grands que le plus grand diviseurs premier de 30. J'appelle L' l'ensemble des premiers soulignés auquel on ajoute l'élément 1 :
L'=1, 7,11,13,17,19,23,29
Deuxième phase on teste avec les premiers de L
Troisième phase on teste avec les nombres n de la forme n=30k+i où i est un élément de L'.
La boucle ne teste "plus" que 8=|L'| nombres sur 30 soit 27% des nombres de la solution naïve. On ne loupe aucun nombre premier, mais on teste certains nombres qui ne le sont pas comme 77=2*30+17.
Comment est-on sûr de ne louper aucun premier ? Imaginons qu'il existe un nombre premier p>30 que l'on ne génère pas. Par division euclidienne on trouve p=30k+k' avec k'<30, forcément k' n'est pas premier (puisqu'on ne le génère pas il n'est pas dans L', il ne peut pas non plus être égal à 2,3 ou 5 sinon p ne serait pas premier) k' pas premier et plus petit que 30 donc il possède un facteur premier inférieur à sqrt(30)=5.xxx => impossible sinon p ne serait pas premier : en raisonnant par l'absurde on prouve que l'on génère tous les premiers (mais pas que).


En continuant, avec Pi le ième nombre premier, on obtient quelque chose comme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
A le nombre à factoriser
P=produit i de 1 à n Pi
L=liste des premiers inférieurs à P
L'={1} U liste des premiers > Pn et <P
Pour tous les p de L faire
  DEC(A,p)
max=sqrt(A) div P
pour i de 1 à max faire
  pour tous les p de L' faire
    DEC(A,P*i+p)
    si (A=1) alors sortir du pour i
si (A!=1) alors A est premier -> le rajouter à la liste des facteurs

Bon en gros ...

En espérant que ces explications étaient claires

[pseudocode]

pseudocode il y en a exactement 6542 et, même compilé l'exécutable prends 80 ko de mémoire vive et ne pèse "que" 784 ko, c'est acceptable. Par contre ta question (et la réponse de kwariz) on retenu mon attention : les nombres que j'avais générés n'étaient pas tous premiers. Bref, en refaisant un générateur correcte je suis tombé à 8 secondes ce qui est déjà beaucoup plus acceptable.

Ah, ok. A la lecture de ton post j'ai cru que tu avais pris TOUT les entiers jusqu'a 2^16, et pas seulement les nombres premiers.

[Invité]

merci, c'était très claire