Test "être un carré" en C++

[chamO007]

Bonjour.
Je suis novice en C++ mais j'ai dû me résoudre à l'utiliser pour une recherche isolée.
Je dois tester plusieurs millions de fois si un nombre est un carré.
Ce nombre e, déclaré long long, doit être tel que e/23 soit un carré.
Dois-je demander est_carre(e/23) ou est_carre(23*e) pour une meilleure efficacité ?
Voici ma procédure :

bool est_carre(long long n) {
    long long racine = sqrt(n);
    return racine * racine == n;
}

Merci pour toute remarque utile.
-----

[Bounoume]

bonjour,
pas d'avis des spécialistes de programmation... alors... sur de vieux souvenirs.... et sans garantie aucune

la fonction sqrt() prend en entrée des nombres en virgule flottante
https://learn.microsoft.com/fr-fr/cp...?view=msvc-170
et elle renvoie aussi un nombre en virgule flottante.....
ainsi pas moyen de savoir directement si la racine est un entier (donc le nombre entier initial était bien un carré)

le type de variable que tu fournis en entrée (entier long) n'est pas en virgule flottante , ni float ni double ni long double....-> transtypage nécessaire-> pas sûr que ça soit automatique, donc accepté directement par le compilateur gcc....
les types de variables: https://c.developpez.com/cours/berna...node16.php#329

et surtout selon que la racine retournée et entière ou décimale plus ou moins approchée, le nombre en entrée est un carré parfait ou il ne l'est pas....
il faut donc savoir si la racine retournée est un entier ou un nombre décimal....
comment faire?
il y a une fonction qui extrait la partie entière d'un flottant
https://learn.microsoft.com/fr-fr/cp...?view=msvc-170
ça aussi
https://learn.microsoft.com/fr-fr/cp...?view=msvc-170
dans les 2 cas, si (exprimée en flottant long double) la partie entière retournée est égale au nombre à tester, alors c'est que le nombre en entrée était déjà un entier....
si en entrée le nombre a des décimales, alors celles-ci sont supprimées dans le retour... et alors ça produira une différence....

alors tu pourrais faire

bool est_carre(long double n)
          {
            # extraire la racine carrée exacte ou approchée
            long double rac= sqrt(n);
            # tester si rac est un  entier 
            if(trunc(rac)==rac) return true else return false;
           };

[Bounoume]

correction de la directive commentaire // (pas # )

bool est_carre(long double n)
          {
            // extraire la racine carrée exacte ou approchée
            long double rac= sqrt(n);
            // tester si rac est un  entier 
            if(trunc(rac)==rac) return true else return false;
           };

[chamO007]

Merci de me guider vers cette solution. Je vais la tester...

[A voir en vidéo sur Futura]

[WizardOfLinn]

Attention quand même aux erreurs d'arrondis dans les calculs en virgule flottante, surtout si on a commencé par diviser par 23 avant d'appeler la fonction, l'algorithme doit garantir qu'aucune réponse ne peut être faussée par des erreurs d'arrondi.
Si e est un entier, commencer par tester e % 23 == 0 (modulo), sans conversion en flottant. Si le test est positif, on peut en toute sécurité diviser par 23.
Il est garanti que m = e/23 est un entier et on cherche n entier tel que m = n*n.

[chamO007]

Merci, j'y avais pensé. La preuve :

long long e = c * c - a * a;
        if (e % 23 == 0) {
            if (est_carre(e * 23) && est_carre(e + c * c)) {
                return std::make_pair(c, a);
            } else ... {

Par précaution, j'ai remplacé e/23 par e*23 car si l'un est un carré, il en est de même de l'autre. Et c'est plus rapide !

Voilà l'état actuel de ma procédure :

bool est_carre(long long n) {
    long double racine = sqrt(n);
    return (trunc(racine) == racine);
}

Je crois qu'on ne peut pas faire plus court.

[vgondr98]

Est-ce que pré calculer tous les nombres carré peut être une option ? Si tu calcules les 1000 premiers carrés, le dernier e² vaut 23 000 000 et si tu calcules les 10 000 premiers carrés, le dernier e² vaut 2 300 000 000.
Ensuite, il suffit de vérifier que ton nombre à tester est dans la liste ou pas.
Çà c'est si vérifier la présence d'un nombre dans une liste est plus rapide que la fonction sqrt.

[vgondr98]

Quel est le besoin de le faire en C++ au fait ?

BigInteger f = new BigInteger("10000").multiply(new BigInteger("10000")).multiply(new BigInteger("23")).multiply(new BigInteger("23"));

		for (int j = 0; j < 100000000; j++) {//5 secondes
			BigInteger g = f.sqrt().multiply(f.sqrt());
			g.equals(f);
		}
		
		System.out.println("fini");

En java, tester 100 million de fois, prend 5 secondes.

[iznobe]

Bonjour , ce n' est pas parceque le code est plus court que ce sera plus rapide pour obtenir le résultat , surtout sur des millions d ' itérations de la fonction ou forcément un millième de seconde de différence sur la fonction , va impacter au final le temps de calcul et donc les ressources utilisées .

si tu ne dois tester que des entiers , alors je commencerai par tester si la division par 23 retour un modulo = à 0 , si ce n' est pas le cas , alors tu peux directement répondre que ce n ' est pas un carré .
si c ' est le cas , tu enchaines pour vérifier si c ' est bien un carré .
Avec cette approche , tu auras un code plus long , mais bien plus performant , car la division par 23 va éliminer une énorme partie des appels au code ci-dessus qui sera bien plus gourmand en ressources qu ' une simple division et test de condition .
En supposant que j' ai bien compris ce que tu essaies de faire ...



Ensuite selon l ' amplitude des carrés a vérifier , peut être qu ' une approche liste comme décrite ci-dessus peut être plus efficace , a tester .