Bonjour.

Je suis débutant en programmation C++ mais je programme depuis longtemps dans d'autres langages.
Je suis en train de développer un programme qui fait un tas de calcul pour trouver des racines carrées entières de triangles rectangle (l'hypoténuse donc) en faisant a² + b² = c² puis RACINE(c)

Après plusieurs recherches, j'ai pu obtenir les infos suivantes :
Si un chiffre termine par 2, 3, 7, ou 8, alors il n'a pas de racine carré entière.

De ce fait, avant de faire la multiplication des 2 autres cotés, je vérifie leur dernier chiffre et prévoit si le résultat sera un 2, 3, 7 ou 8.
Ex : un triangle de coté 1 et 4, 1² + 4² = 17 => pas de racine carrée entière. Donc si "a" termine par 1 et "b" par 4, je ne fais pas ma racine.

J'en arrive à un code dans ce style :

Et bizarrement, pour le calcul de 3 244 750 501 de racines carrés (3 milliards), il est plus rapide de ne pas utiliser cette technique que de faire les opérations suivantes :

c'est la version simple, auparavant j'étais parti sur une solution par tableau dans ce style que j'initialisais au démarrage du programme :

Puis je testai ceci :

(Après 3 essais, on passe de 59s à 46s avec et sans cette "optimisation", la version optimisée est donc plus lente).

Comment cela se fait alors qu'on élimine 1 281 876 741 d'opérations ? Je pensais que la racine carrée était couteuse mais moins qu'une vérification de numéro.

Merci.

Question annexe, j'avais préalablement codé cela en C# mais sur un bench entre 2 bornes, là où il me fallait 50s pour faire mes opérations, je fais les mêmes en 730ms en c++. Pourquoi y'a t-il un tel gap de performance ?

Merci beaucoup.

Premature optimization is the root of all evil
attribué à Donald Knuth
 
 
 
En bref: Ton compilateur va largement optimiser ton code en modifiant à droite et à gauche (mais sans changer le comportement final), voir la doc (GCC: option -Os, -O0 à -O3). Il faudrait donc déjà voir au niveau assembleur. Aussi une instruction n'est pas égal à un cycle d'horloge en x64. En plus un truc aussi "banal" que sqrt() c'est en hardware que cela se fait et depuis un bon moment, donc nettement moins coûteux que ton code (soft). Et même si ça serait en soft, la fonction sqrt() de la lib' standard est optimisée au max déjà.
 
Pour finir, le C# je ne connais pas, mais ça doit être interprété "just in time" ou quelque chose du genre, du coup bah c'est (beaucoup) plus lent.

Merci pour ta réponse.
 
Que la fonction sqrt() soit traité en hardware, je l'accepte mais entre faire très vite et ne pas faire, j'aurai largement parié que ne pas faire serait + rapide.
Ce sont des if TRES simple qui comparent entre eux des int de taille 1, je suppose très peu couteux en CPU.
 
Egalement, c'est parce que c'est toujours trop long que je cherche à éviter un maximum de calcul.
J'avais d'abord codé tout ça en python, mais trop lent. J'ai ensuite rajouté les optims, ça a réduit considérabelement le temps d'exécution.
Je l'ai ensuite passé en C# (code compilé en x64 avec le SDK .net 7.0) mais toujours trop lent.
J'ai donc décidé de passer en c++ et là enfin je note une vrai différence mais j'ai aussi noté que les optim qui fonctionnaient en python et C# ne fonctionne plus en c++.

Je pense que dans mon cas, on est ici :  
https://fr.wikipedia.org/wiki/Prédi [...] _de_boucle
 
Mon code étant dans une boucle, je pense que le compilateur prédit mon test "result is int" et évite de faire les calculs pour les valeurs de a et b qui ne satisferont pas ce test.

Tu peux fournir un exemple qui compile?
 
De manière générale, optimiser trop tôt c'est mal, cf. citation... Que cherches-tu à faire pour avoir besoin d'autant de racines² en peu de temps? Et quels sont tes contraintes au niveau temps etc exactement?

Bon mea culpa, erreur de ma part.
 
Erreur dans mon code, en mettant les bonnes valeurs et en appliquant une autre optimisation dans une boucle (éviter un changement de type, ça parait rien mais sur 1.5 milliards d'opérations, je gagne rien qu'avec ça 12s), je passe de 50s à 29s.

 
C'est plus du test qu'autre chose donc rien d'intéressant pour le moment.

Comme je disais, il faudrait regarder le code assembleur généré par le compilateur. Il n'y a pas d'instruction "changement de type de variable" p.ex.; par contre selon le(s) type(s) de variable(s) qu'on utilise le compilateur - surtout si les optimisations sont activés voir à fond (-O3) - va générer du code totalement différent.
 
De manière générale, je ne citais pas Knuth sans raison. Il ne faut surtout pas se croire plus malin que le compilateur et "optimiser" au détriment de la lisibilité etc. Après tout dépend de ce qu'on fait, écrire un programme "normal" ou un pilote très bas niveau avec une fonction qui sera potentiellement exécutée des dizaines de milliers de fois chaque seconde...

et par curiosité le dernier chiffre de ton nombre, tu le récupères comment?

et encore un mot clé utile: profiler
 
Par contre je me souviens plus du nom du profiler livré avec GCC , mais la doc te le dira.

Je fais modulo 10 avant ma 1ere itération de boucle que je stocke dans une variable. Ensuite comme j'incrémente mon compteur de boucle de 1, je fais également +1 à ma variable et quand j'arrive à 10 je la remets à 0. Ca ne fait qu'une somme par boucle, moins couteux qu'un %10 à chaque itération de boucle.

Mais s'il y a moins couteux, je suis preneur. Genre (je pense pas que ça existe mais idéalement ce serait) définir un type de donnée qui prend au minimum 0 et au maximum 9. Quand ça dépasse 9, dépassement de capacité => retour à 0. J'économise 1 condition.

Concernant le profiler, je suis sous Visual Studio 2022 par habitude faisant du C# à côté.

Dans les optims intéressantes, j'ai vu qu'un chiffre ne peut donner une racine entière que si la somme de ses numéros (jusqu'à obtenir qu'un seul numéro) est égale à 0, 1, 4, 7 ou 9.
Avec ce code, on fait ça en très peu de temps, beaucoup moins que des boucles que j'ai pu voir :

Bien que ça fonctionne très bien que que cela me diminue les calculs de 1.5 milliards à 800 000 000, ça reste + couteux que de faire les 700 000 000 millions de racines carrés, donc le code est commenté.

Egalement, on sait qu'un nombre qui termine par un nombre de 0 impair n'a pas de racine carré entière (ex : 1000, 950, 25000). Ca me permet d'économiser encore environ 50 000 000 de racines carrés mais ça implique au moins division en plus à chaque boucle et donc plus lent.

Preneur cependant s'il y a des méthodes pour prédire des racines carrés non entière.

En fait, ce que tu cherches, ça serait pas les triplets de Pythagore ?
https://fr.wikipedia.org/wiki/Triplet_pythagoricien

Plus précisément des briques d'Euler.
Les formules permettant de générer des triplets de Pythagore (d'après mes tests) ne permettent pas d'obtenir toutes les briques ex :
la brique avec un coté a=85;b=132;c=720 ne "sort" pas avec les formules données. En fait le duo 85/720 ne sort pas.
Mais je peux surement me tromper.

Bizarre, si on fait a/c + b/c, on trouve pas 1. Or, si j'ai bien compris l'article, ça devrait.
Cela dit, quand je fais 85²+132², je ne trouve pas 720². D'ailleurs, ton triangle n'est pas constructible car a+b est < c. Or, pour qu'un triangle soit constructible, il faut que a+b > c (c étant l’hypoténuse)

Erreur de ma part, je me base sur cette image pour ne pas me tromper dans mon programme :

Donc la formule me trouve les duo suivants :
a=85;b=132;d=157
a=85;b=3612;d=3613

Il ne m'a pas trouvé
a=85;b=720;d=725

Ce trio me permet pourtant de construire la brique d'euler  suivante :
a=85;b=132;c=720

Mais je me répète, je peux avoir fait des erreurs.

Je comprends pas trop : tu cherches les triplets a, b, d ou les triplets a, c, e ?
Cela dit, ça change pas grand chose. a,b,d et a,c,e sont des triplets de Pythagore.
Pour un "a" donné, ça va conditionner b et c, donc d et e.

J'aurai dû envoyer l'image avant pour éviter les confusions mais oui, je cherche des trios
a, b, d
a, c, e
b, c, f
Voici mon code en utilisant la formule de wikipedia :
a=m²-n², b=2mn, c=m²+n² (d dans mon cas)

Jamais dans la console j'ai le "On est la" alors que ce trio existe.

Tiens donc, ce gars était maçon aussi...
 
Pardon.

T'as regardé le § "Génération algébrique et géométrique" dans l'article de Wikipedia ?
 
Edit : le § "Généralisation" devrait aussi t'aider

et un autre truc très important: Les types de variables à virgule flottante (autrement dit float, double) ne permettent pas de représenter exactement certains nombres. Tu pourrais avoir un résultat de calcul genre 720,000000000000000000001 mais ta comparaison est ==720 donc elle sera fausse, même si il s'agit en quelque sort d'une "tolérance" dûe au type de variable. Wikipédia devrait te renseigner sur cette histoire aussi.
 
(Je sais pas si dans ton cas concrèt c'est le problème mais il faut le savoir...)

Vu qu'il cherche des nbs entiers, il pourrait arrondir ses nbs au millième pour contrer le pb des floats lors des comparaisons.

Ceci est un "vieux" programme en C# qui ne m'a pas donné satisfaction, je suis parti sur la solution en C++ et je ne travail pratiquement qu'avec des entiers sauf pour faire la racine carré.
Cependant, je pars sur une idée de matrice pour voir ce que ça donne.

 
Ca y est, je rencontre le soucis que tu remontes mais je ne comprends pas tellement pourquoi.
Ex :  
long double a = 132;
long double numIteration = 5

Résultat attendu : 13.2
Résultat obtenu: 13.1999999999999999
 
Comment gérer ce problème ?
J'ai le même soucis avec le type float ou double.
 
Merci

Déjà tu devrais te renseigner sur les types de variables. Le long double ça doit être du 128 bits ou je sais pas quoi, en tout cas c'est "gros" et pas commun. Et perso j'ai bien 13.2 avec ton bout de code, mais aussi un gros warning (tu les a activés en fait au niveau de ton compilateur? obligatoire!)

Faudrait déjà creuser ça... Sinon cette histoire dont on parle est liée au fait comment sont représentés les nombres à virgule flottante. Si tu te sens bien et psychologiquement stable tu peux demander IEEE754 à Wikipédia, mais je déconseille. (Autrement dit, c'est très très complexe).
 
 
N'ayant toujours pas compris ce que tu cherches au final je ne pourrais te donner des conseils précis, mais globalement
-utiliser le type de variable le plus petit possible
-utiliser des entiers ou de la virgule FIXE autant que possible
-passer en float qu'à la "fin" pour le résultat final (à définir )
-surtout ne pas optimiser sans raison valable (ce qui ne veut pas dire faire n'importe quoi, mais faut pas se croire plus malin que le compilateur...)
 
Bon après je viens du monde des µC 8 bits où les float c'est gros comme une montagne au niveau exigences, autrement dit j'ai tendance à faire très attention aux types de variables etc. Regarde aussi à ce propos stdint.h .

Il veut trouver tous les triplet permettant de faire des briques d'Euler, la version 3D des triplet de Pythagore si j'ai bien compris.
A mon avis, niveau algo, il devrait d'abord générer tous les triplets de Pythagore du petit côté de sa brique (donc les triangles ABD) et ensuite, pour chaque triplet, chercher les autre triplets de Pythagore pour le triangle ACE (A étant déjà trouvé).

Sinon, tu peux résoudre le système de 3 équations donné sur cette page : https://fr.wikipedia.org/wiki/Brique_d%27Euler
J'espère que tu cherches pas la brique parfaite, parce que l'article dédié dit que pour l'instant, personne a trouvé  

En tattonant, j'ai pondu un super algo de 4 lignes qui génère en très peu de calcul tous les triplets de pythagore pour un nombre donné sans tester tous les nombres possibles (donc pas de brute force) et sans aucune racine carré.
Je vais tenter de résoudre le soucis des virgules car cela me bloque pour le moment. Je connaissais ces soucis car je les avait rencontré dans de vieilles version d'Excel (excel 99 ou 2000) et je sais qu'il y a des soucis pour représenter des nombres à virgule en binaire. Mais je ne pensais pas que cela était toujours le cas (tout du moin je pensais que le compilateur je gérai correctement).
En tout cas merci pour votre aide.
 
Voici ce que j'obtiens en créant un nouveau projet C++ dans visual studio 2022 en utilisant la dernière vesion de C++ (version 20 il me semble).
 
@rat de combat, j'ai le même soucis que ce soit en float ou double.

C'est le comportement normal des binaires à virgule flottante, "13.2" n'est pas une valeur représentable donc t'as un truc qui s'en rapproche au maximum.

Les jeunes lisent plus Goldberg?

Certains jeunes sortant d'IUT GEII ou d'une école d'ingé en informatique ne connaissent plus le masquage de bits, alors un truc aussi pointu que la représentation des nbs à virgule  

Pour comparer tes doubles tu ne peux pas utiliser une comparaison stricte, mais plutôt avec un seuil de tolérance.
 

 
As-tu réussi à faire ce que tu voulais ?  
Le sujet est intéressant, et je ne connaissais pas non plus les briques d'Euler.
 
C'est bien justement les petits jeunes qui veulent bien essayer d'optimiser même si c'est souvent un poil trop tôt, ça change des djeuns nodejs  

Sérieux? Aie.

Faut les former à la vraie vie, du CRUD.

Ben oui    
Note qu'une de mes stagiaires que j'ai eu (bac+5) issue d'une école d'ingé en télécom ne connaissait pas non plus

on perds clairement en compétences plus on avance