pgl10
Messages postés380Date d'inscriptionsamedi 18 décembre 2004StatutMembreDernière intervention29 octobre 2023
-
2 mai 2016 à 13:56
pgl10
Messages postés380Date d'inscriptionsamedi 18 décembre 2004StatutMembreDernière intervention29 octobre 2023
-
10 mai 2016 à 18:06
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
Bonjour CptPingu,
Merci beaucoup pour cette liste de corrections et d'améliorations. C++ est un langage riche qui continue de s'enrichir. Parfois, on peut se demander s'il est plus facile d'apprendre les nouveautés du langage ou bien d'oublier les habitudes anciennes devenues obsolètes ! Mais quand on regarde bien ce qu'apportent les instructions C++11 c'est le plus souvent une plus grande facilité de programmation, exemples : vector, array, auto, ... Ce petit programme a permis des remarques utiles, tant mieux ! Le visiteur qui le souhaite peut réutiliser le crible d'Eratosthène optimisé pour les nombres impairs. Remerciements.
Bonjour Hbouia,
Merci pour vos remarques. Je ne connais pas Python, je m'en remets à vous à ce sujet.
Bonjour tous,
Pour utiliser le crible d'Eratosthène au delà de la limite des entiers 32 bits, il faut compiler en mode x64 et non pas en mode Win32.
hbouia
Messages postés112Date d'inscriptionmardi 30 juillet 2013StatutMembreDernière intervention22 novembre 202212 9 mai 2016 à 20:28
Bonjour Pgl10,
J'aime beaucoup vos contributions sur site et c'est généreux de votre part de les partager : ça nous permet, nous lecteurs occasionnels de nous instruire et je vous en félicite particulièrement. Je suis sûr que si vos programmes son traduits en langage Python, vous aurez encore plus de lecteurs et en plus vous pourriez nous faire bénéficier de vos méthodes d'accélération des calculs pour certains algorithmes.
Exemple, tout bêtement j'ai essayé de traduire votre programme de la suite polynomiale de de degré 4 pour fournir les 43 premiers termes entiers tous premiers et distincts 2 à 2.
Comme ces des nombres sont tous relativement petits (en nombre de chiffres) :
En python et pour les non initiés, ce qui suit suffirait (Etes vous d'accord ?) :
# -*- coding: utf-8 -*-
"""
@author: bouia-has (Created on Mon May 09 18:45:23 2016)
biblio : http://codes-sources.commentcamarche.net/source/101467-polynome-et-nombres-premiers
"""
import numpy as np
def u(n): return 28080037+n*(-4984701+n*(331416+n*(-9777+n*108)))
def estPremier(n):
if n in [2,3]: return True
sqrn=int(np.sqrt(n+0.1))+1
for k in range(3,sqrn,2):
if n%k==0: return False
return True
for n in range(100):
un=u(n)
if not estPremier(un): break
print n,' : ',un,True
Cordialement et enchanté de vous avoir lu
HB
cptpingu
Messages postés3837Date d'inscriptiondimanche 12 décembre 2004StatutModérateurDernière intervention28 mars 2023123 Modifié par cptpingu le 6/05/2016 à 16:12
Bonjour.
Quelques remarques:
Péfère la notation 0xFF à '\0xFF', qui a le mérite d'être aussi clair, mais d'être plus concise (et qui ne bug pas sur ce site, puisque les '\' sont "mangés" dans ton exemple).
Vu que c'est du C++, il n'est pas nécessaire d'allouer quoi que ce soit explicitement. Préfère l'utilisation de vecteur de taille fixe (std::vector + resize) qui remplace une allocation + un memset. Pour des tableaux dont la taille est connue avant la compilation, on utilise std::array.
Attention au VLA (variable length array, qui consiste à créer un tableau de taille fixe via une donné variable, ex: std::cin >> n; int tab[n]), car c'est officiellement géré en C, mais pas garantie en C++. De toute façon, quand on utilise un VLA, c'est qu'on pourrait utiliser un std::vector à la place.
Les variables globales, ce n'est pas très propre (risque de code "spaghetti"), mais les constantes globales, il n'y a aucun problème avec.
Pour savoir si un nombre est pair, au lieu de faire "nb % 2", il est (théoriquement) plus rapide de faire: "nb & 1". Je pense tout de même qu'un bon compilateur saura détecter ce cas et faire cette optimisation de lui même.
Au lieu de faire des "erreur + exit", utilise directement "assert", c'est exactement fait pour cela.
Attention 0xFF rentre dans un "unsigned char" [0,255], mais pas dans un "char" [-127,128] (tes valeurs dans les tableaux C0 et C1 "débordent").
Préfère "\n" à "std::endl", sauf pour le dernier. En effet, un std::endl fait deux choses: un "\n" + un std::flush. Il ne faut donc pas en abuser.
Je te propose une version modifiée de ton code (en C++11, avec en bonus un petit chrono):
#include <iostream>
#include <iomanip>
#include <vector>
#include <array>
#include <cstdint>
#include <cassert>
#include <chrono>
#define ASSERT_MSG(Cond, Msg) assert(Cond && Msg)
namespace
{
typedef std::vector<unsigned char> crible_type;
// crible[] contient les bits utiles du crible.
// le crible ne concerne que les nombres impairs:
// crible[0] pour 1 à 15, crible[1] pour 17 à 31, etc.
const int64_t NCCMAX = 34359738367; // (2^35)-1
const unsigned char C0[] = {0xFE, 0xFD, 0xFB, 0xF7, 0xEF, 0xDF, 0xBF, 0x7F};
const unsigned char C1[] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};
// Crible d'Eratosthène
// Uniquement les positifs impairs présents et traités dans le crible
void eratosthene(int64_t ncc, crible_type& crible)
{
int64_t t = 1 + (ncc - 1) / 16;
crible.resize(t, 0xFF);
crible[0] = 0xFE; // 1 n'est pas premier
// On marque les multiples impairs de 3
for (int64_t j = 9; j <= ncc; j += 6)
crible[j >> 4] = crible[j >> 4] & C0[(j >> 1) & 7];
int64_t i = 5;
int64_t i2 = 25;
int64_t s = 2;
// On marque les multiples de i non multiples de 2 et 3
while (i2 <= ncc)
{
if ((crible[i >> 4] & C1[(i / 2) & 7]) != 0x00)
{
for (int64_t j = i2, t = s; j <= ncc; j = j + t * i, t = 6 - t)
crible[j >> 4] = crible[j >> 4] & C0[(j >> 1) & 7];
}
i = i + s;
i2 = i * i;
s = 6 - s;
}
}
// Retourner true si le nombre k est premier et false si k est composé.
bool isprem(int64_t k, int64_t ncc, const crible_type& crible)
{
if (k < 2 || k > ncc)
return false;
if (!(k & 1))
return k == 2;
if ((crible[k >> 4] & C1[(k >> 1) & 7]) == 0x00)
return false;
return true;
}
void usage(const char** argv)
{
std::cout << "Usage: " << argv[0] << " <ncc> <list of nums>" << std::endl;
}
} //namespace
int main(int argc, const char** argv)
{
if (argc < 3)
{
usage(argv);
return 1;
}
// n est le degré du polynôme à vérifier
int n = argc - 3;
std::vector<int64_t> a(n + 1, 0);
// limite de l'intervalle [1, ncc] de calcul du crible
int64_t ncc = std::stoll(argv[1]);
ASSERT_MSG(ncc > 0, "Invalid ncc!");
ASSERT_MSG(ncc <= NCCMAX, "ncc can't be > to nccmax!");
for (int i = 0; i <= n; ++i)
a[i] = std::stoll(argv[n - i + 2]);
std::cout << "\nVérification de la formule:\n\np(x) = ";
if (n > 1) std::cout << a[n] << "*x" << n;
if (n == 1) std::cout << a[n] << "*x";
if (n == 0) std::cout << a[n];
for (int i = n - 1; i >= 0; i--)
{
if (a[i] == 0) continue;
if (a[i] > 0) std::cout << "+";
if (i > 1) std::cout << a[i] << "*x" << i;
if (i == 1) std::cout << a[i] << "*x";
if (i == 0) std::cout << a[i];
}
std::cout << "\n\n";
auto start = std::chrono::system_clock::now();
// crible d'Eratosthene pour les entiers impairs de 1 à ncc
crible_type crible;
eratosthene(ncc, crible);
std::array<int64_t, 65> r;
int k = 0;
for (int x = 0; x < 65; ++x)
{
// calcul de p=p(x)=an*x^n+...+a1*x+a0
int64_t p = 0;
for (int i = n; i >= 0; i--)
p = p * x + a[i];
r[x] = p;
// calcul de la multiplicité m de p
int m = 1;
for (int j = 0; j < x; j++)
if (r[j] == p)
++m;
// si on préfère exclure en tant que nombres premiers
// les entiers négatifs quand ils sont premiers en valeur absolue
// il suffit de mettre en commentaire l'instruction suivante:
if (p < 0)
p = -p;
if (isprem(p, ncc, crible))
{
++k;
// on affiche le k-ième nombre premier
std::cout << std::setw(5) << k << " x = " << std::setw(3) << x
<< " p(x) = " << std::setw(12) << r[x] << " (premier)";
if (m > 1)
std::cout << std::setw(4) << m;
}
else
{
// on affiche un nombre composé
std::cout << " x = " << std::setw(3) << x
<< " p(x) = " << std::setw(12) << r[x] << " ";
if (m > 1)
std::cout << std::setw(4) << m;
}
std::cout << "\n";
}
auto end = std::chrono::system_clock::now();
const int elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
std::cout << "Elapsed time: " << elapsed << " ms" << std::endl;
return 0;
}
Modifié par pgl10 le 10/05/2016 à 18:26
Merci beaucoup pour cette liste de corrections et d'améliorations. C++ est un langage riche qui continue de s'enrichir. Parfois, on peut se demander s'il est plus facile d'apprendre les nouveautés du langage ou bien d'oublier les habitudes anciennes devenues obsolètes ! Mais quand on regarde bien ce qu'apportent les instructions C++11 c'est le plus souvent une plus grande facilité de programmation, exemples : vector, array, auto, ... Ce petit programme a permis des remarques utiles, tant mieux ! Le visiteur qui le souhaite peut réutiliser le crible d'Eratosthène optimisé pour les nombres impairs. Remerciements.
Bonjour Hbouia,
Merci pour vos remarques. Je ne connais pas Python, je m'en remets à vous à ce sujet.
Bonjour tous,
Pour utiliser le crible d'Eratosthène au delà de la limite des entiers 32 bits, il faut compiler en mode x64 et non pas en mode Win32.
9 mai 2016 à 20:28
J'aime beaucoup vos contributions sur site et c'est généreux de votre part de les partager : ça nous permet, nous lecteurs occasionnels de nous instruire et je vous en félicite particulièrement. Je suis sûr que si vos programmes son traduits en langage Python, vous aurez encore plus de lecteurs et en plus vous pourriez nous faire bénéficier de vos méthodes d'accélération des calculs pour certains algorithmes.
Exemple, tout bêtement j'ai essayé de traduire votre programme de la suite polynomiale de de degré 4 pour fournir les 43 premiers termes entiers tous premiers et distincts 2 à 2.
Comme ces des nombres sont tous relativement petits (en nombre de chiffres) :
En python et pour les non initiés, ce qui suit suffirait (Etes vous d'accord ?) :
Cordialement et enchanté de vous avoir lu
HB
Modifié par cptpingu le 6/05/2016 à 16:12
Quelques remarques:
Je te propose une version modifiée de ton code (en C++11, avec en bonus un petit chrono):