Remarque : Une participation au défi de @David_Burnham a été soumise avant la date limite, mais elle a été bloquée par ma messagerie. Je ne l'ai découverte qu'après la publication de l'article original. Je mets à jour les résultats pour refléter les modifications apportées.
Merci à tous ceux qui ont soumis du code pour le Défi 2. La notation était un défi, certains codes étant plus performants pour les petites valeurs, d'autres pour les grandes. Le tableau ci-dessous présente les résultats pour chaque partie du défi. Trois exécutions ont été réalisées pour estPrime , 1 000 nombres impairs aléatoires à 5 chiffres non divisibles par 5, des nombres impairs à 8 et 9 chiffres non divisibles par 5, et des nombres impairs à 12 à 15 chiffres non divisibles par 5. Les résultats étaient basés sur les deux dernières conditions. Les points ont été répartis entre les défis : 1,5 point pour le premier , 1 pour le deuxième et 0,5 pour le troisième . Les temps des soumissions les plus rapides sont également indiqués (en secondes).
@leelaim a exécuté isPrime(Small) aussi rapidement que n'importe quel autre script JMP (+3 points). @landon a utilisé la fonction d'affectation parallèle pour accélérer le script isPrime(Big). Deux entrées ont mis en cache leurs résultats pour obtenirPrimes en utilisant Espace de noms . Cette approche est utile lorsque les résultats doivent être consultés plusieurs fois (les temps d'exécution sont toutefois basés sur des résultats non mis en cache). Ces quatre entrées sont présentées ci-dessous.
Voici le classement après deux défis :
Le défi 3 sera publié le mercredi 1er juin.
Le défi 2 demandait de trouver des nombres premiers de deux manières. Étant donné un entier positif n , il fallait trouver : 1) n nombres premiers ou 2) tous les nombres premiers inférieurs à n . Commençons par 2), car c'est plus facile à mettre en œuvre. La méthode la plus simple pour trouver des nombres premiers est la division par essai. En partant de 2 comme candidat et d'un ensemble vide de nombres premiers, vérifiez si un nombre de l'ensemble actuel divise uniformément le nombre candidat. Si ce n'est pas le cas, ajoutez-le à l'ensemble des nombres premiers et continuez avec le nombre candidat suivant. Comme il n'y a rien dans l'ensemble des nombres premiers au départ, 2 est ajouté. En vérifiant 3, il ne divise rien dans {2} et est ajouté à l'ensemble des nombres premiers. Le nombre 4, en revanche, divise quelque chose dans {2,3} et n'est pas ajouté. Un exemple d'implémentation est présenté ci-dessous.
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = [];
For(i=2,i<=n,i++,
For(j=2,j<=N Row(primeSet),j++,
If(Mod(i,j)==0, Break());
);
If(j>N Row(primeSet),primeSet = primeSet |/ i);
);
primeSet;
);
Cette approche présente plusieurs avantages : elle est facile à comprendre, le code est concis et s'adapte facilement aux deux défis de recherche de nombres premiers. Malheureusement, elle est extrêmement lente. Trouver les nombres premiers inférieurs à 100 000 m'a pris 19,43 secondes .
Une approche légèrement plus complexe consiste à utiliser un crible. Plutôt que de tester un nombre pour déterminer sa primalité, les cribles testent les nombres hors de cette primalité. Le plus ancien et le plus connu est le crible d'Ératosthène . Commencez par supposer que tout est premier. En commençant par 2 comme premier nombre premier, trouvez tous les nombres qui le divisent uniformément et retirez-les de l'ensemble des nombres premiers. Continuez avec le nombre suivant encore dans l'ensemble des nombres premiers. Vous trouverez ci-dessous une version non optimisée.
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = J( n, 1, 1 );
primeSet[1] = 0;
For( i = 2, i <= n, i++,
For( j = i, j <= n / i, j++,
primeSet[j * i] = 0
)
);
Loc( primeSet );
);
L'avantage le plus évident est la rapidité. Mon temps pour trouver tous les nombres premiers inférieurs à 100 000 a été de 0,2811 s, soit environ 70 fois plus rapide, et de 3,4025 s pour 1 000 000. Le code reste concis et facile à comprendre. Un inconvénient mineur est la nécessité de créer un vecteur pour suivre les nombres non premiers (c'est-à-dire qu'il est impossible d'agrandir la liste par concaténation – ce qui, nous le verrons plus tard, n'est pas forcément un avantage). Cela complique la recherche de n nombres premiers, car on ne connaît pas précisément la taille du vecteur nécessaire.
Voici deux versions optimisées. La première commence par supprimer tous les multiples de deux, puis boucle uniquement sur les nombres impairs à partir de 3. Sqrt( n ) est utilisé pour la borne supérieure de la boucle externe, car tous les nombres non premiers inférieurs à 100 auront déjà été éliminés. Par exemple, pour trouver tous les nombres premiers inférieurs à 100, il suffit de filtrer jusqu'à 10. Les nombres filtrés pour tout nombre premier supérieur à 10 seront le produit de ce nombre premier par un nombre inférieur à 10, qui aura été éliminé par un autre nombre premier (par exemple, 11*5 est éliminé avec le tamis pour 5, 11*9 avec le tamis pour 3, etc.). Ces améliorations réduisent le temps d'exécution de plus de moitié, pour atteindre 1,3545. La seconde montre l'avantage d'utiliser les opérations matricielles de JSL pour la boucle interne, avec des temps de 0,01625 pour 1 000 000 et 2,6694 pour 100 000 000, soit une amélioration de près de 100 fois !
getPrimes2 = Function( {n}, {primeSet,i,j},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
For( i = 3, i <= Sqrt( n ), i+=2,
For( j = i, j <= n / i, j++,
primeSet[j * i] = 0
)
);
Loc( primeSet );
);
getPrimes2 = Function( {n}, {primeSet,i,j,upper},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
i = 3;
upper = Sqrt(n);
For(i=3,i<=upper,i+=2,
If(primeSet[i] == 1,
primeSet[(i*2)::n::i] = 0;
);
);
Loc( primeSet );
);
Pouvez-vous faire mieux ? Le crible d'Atkin est théoriquement plus efficace et a été implémenté dans Exemple de nombres premiers Atkins.JSL et Primes Atkins (optimisées).JSL . Le premier offre une implémentation non optimisée et plus facile à comprendre (2,236 s pour 1 000 000). Il est meilleur que la version non optimisée d'Ératosthène. La version optimisée, en revanche, n'a pas pu surpasser Ératosthène optimisé (4,914 s pour 100 000 000). De plus, il est beaucoup plus long et complexe, tant sur le plan programmatique que théorique.
Qu'en est-il de la lecture d'un tableau de nombres ? Bien que cela ne soit pas dans l'esprit de l'écriture d'un algorithme, je n'ai pas dit que c'était impossible. @Craige_Hales a fourni une solution utilisant cette approche. Étant donné que le problème spécifiait que n ne devait pas dépasser 1e8, la taille du script contenant les valeurs compressées nécessitait plus de 4 millions de caractères de code, 4,6 Mo d'espace disque et environ 5,5 secondes de chargement, quelle que soit la taille de n . C'était plus lent que les autres solutions. Bien qu'il ne soit ni le plus rapide ni le plus court, j'ai inclus le script de Craige en raison de son approche unique du problème, de son utilisation de la compression et de Parallel Assign .
Trouver n nombres premiers est un problème plus complexe. En supposant que vous utilisiez un crible, vous devrez créer un vecteur de valeurs jusqu'au n- ième nombre premier. Pour ce faire, une borne supérieure pour cette valeur doit être estimée. Toute sous-estimation doit être évitée, car elle peut nécessiter de réexécuter tout ou partie de l'algorithme pour trouver les valeurs non criblées. Le fichier « Estimation de la valeur n-ième nombre premier.jmp » présente six estimations différentes. Est1 illustre un cas où les valeurs sont sous-estimées pour un petit nombre n . De nombreuses estimations ne s'appliquent qu'à n supérieur à une valeur spécifique et il convient de fournir des estimations alternatives dans ces cas. Est2 est efficace pour n ≥ 13 et Est3 l'améliore pour les valeurs plus élevées. Malheureusement, les bornes efficaces sont rarement simples. Est4 a été utilisé dans le fichier « Primes fast submission.jsl » . Bien qu'il ne soit pas aussi performant et sous-estime les valeurs très élevées de n , il est simple et facile à mémoriser. Il est 5 a été dérivé à l'aide de la méthode non linéaire avec les valeurs réelles. Est6 améliore Il est 5 en perturbant légèrement les valeurs afin qu'aucune valeur du tableau ne soit sous-estimée. Il n'est pas garanti qu'il n'y ait pas de sous-estimation entre 100 et 1e8. Les autres colonnes du tableau indiquent les sous-estimations/surestimations pour chaque technique.
La détermination de la primalité pourrait suivre un chemin similaire à la génération de nombres premiers. Étant donné un nombre x , vous pourriez laisser i = 2. Si Mod( n , i ) == 0 , arrêtez, sinon incrémentez i . Continuez jusqu'à ce que Mod( n , i ) == 0 ou i == n . Le code ci-dessous bénéficie de la vérification de i impair uniquement après le test initial à i = 2 et de l'arrêt lorsque i > = Ceiling(Sqrt( n )) .
isPrime = Function({inVals},{i,j,outVec,nextVal,uBound},
outVec = J(N Row(inVals),1,-1);
For(i=1,i<=N Row(inVals),i++,
nextVal = inVals[i];
If(Mod(nextVal,2) == 0,
outVec[i] == 0;
,//ELSE
j = 3;
uBound = Ceiling(Sqrt(nextVal));
While(j < uBound & Mod(nextVal,j) != 0, j+=2);
If(j >= uBound, outVec[i] = 1,outVec[i] = 0);
)
);
outVec;
);
Le script ci-dessus prend environ 1,4 seconde pour vérifier les 1 000 nombres à huit et neuf chiffres dans le tableau Tableau des grands nombres.jmp ( Petit ).
Pour améliorer encore cela, vous pouvez générer un vecteur de nombres premiers (jusqu'à Ceiling(Sqrt( n )) ) et les parcourir.
getPrimes = Function( {n}, {primeSet,i,j,upper},
primeSet = J( n, 1, 1 );
primeSet[4::n::2] = 0;
primeSet[1] = 0;
i = 3;
upper = Sqrt(n);
For(i=3,i<=upper,i+=2,
If(primeSet[i] == 1,
primeSet[(i*2)::n::i] = 0;
);
);
Loc( primeSet );
);
isPrime = Function({inVals},{i,j,outVec,primeVec,nextVal},
outVec = J(N Row(inVals),1,-1);
primeVec = getPrimes(Ceiling(Sqrt(Max(inVals))));
For(i=1,i<=N Row(inVals),i++,
nextVal = inVals[i];
j=1;
While(j < N Row(primeVec) & Mod(nextVal,primeVec[j]) != 0, j++);
If(j >= N Row(primeVec), outVec[i]=1,outVec[i]=0);
);
outVec;
);
Cela réduit le temps de plus de moitié, à moins de 0,6 seconde.
Deux remarques générales pour améliorer la vitesse : lorsqu'une valeur de matrice doit être utilisée plusieurs fois, il est plus rapide d'affecter la valeur à une variable, en utilisant la variable plutôt que la matrice indexée. Bien que cela puisse allonger le code, cela permet de gagner du temps. Essayez ceci en remplaçant nextVal dans le code ci-dessus par sa valeur de matrice indexée ( inVals[i] ). Deuxièmement, Lieu et la concaténation de matrices ralentissent à mesure que la taille de la matrice augmente. Si vous pouvez travailler avec une matrice triée, Loc trié effectue une recherche binaire et est beaucoup plus rapide. Consultez le fichier Speed testing matrix operations.jsl pour des exemples supplémentaires sur le référencement et la concaténation de matrices.
Trouver des nombres premiers dans la colonne des grands nombres ( Grand ) est plus problématique. Trouver les 10 premiers prend environ 1,9 seconde. À ce stade, il faut recourir à un algorithme spécialisé pour les améliorer. Miller-Rabin (MR) est une technique couramment utilisée et relativement simple à mettre en œuvre pour tester la primalité. Une version déterministe est fournie dans millerRabin1.jsl . MR repose sur l'exponentiation modulaire et il faut veiller à éviter les erreurs de dépassement de capacité. À lui seul, MR met 5,28 secondes pour traiter les 1 000 grands nombres. Vous serez peut-être surpris d'apprendre que MR est plus lent que le premier algorithme isPrime ci-dessus (2,34 secondes) pour traiter les petits nombres. Cela est probablement dû au fait que son efficacité de calcul augmente avec la taille des nombres, ce qui suggère une amélioration : testez jusqu'à une certaine taille de nombre premier en utilisant l'étape 2) ci-dessus. Si le nombre est premier, arrêtez. Sinon, passez à MR. Cette approche est disponible dans millerRabin2.jsl . Des réglages ont été effectués pour trouver le nombre idéal de nombres premiers à vérifier. Le temps a ainsi été divisé par deux, pour atteindre 2,33 secondes.
