Bonjour,
La question est dans le titre, je voudrai écrire une fonction optimisée me renvoyant si la racine carrée d'un nombre est un nombre entier ou non, mais je ne sais pas comment m'y prendre ?
Merci.
Bonjour,
La question est dans le titre, je voudrai écrire une fonction optimisée me renvoyant si la racine carrée d'un nombre est un nombre entier ou non, mais je ne sais pas comment m'y prendre ?
Merci.
Bonjour,
Est-ce un exercice scolaire ou est-ce juste pour le défi ?
Je ne pense pas qu'il y ait plus efficace, pour répondre à cette question, que calculer directement la racine dudit nombre. C'est une opération arithmétique qui ressemble à la division euclidienne sur papier et dont la complexité est proportionnelle au nombre de chiffres. En revanche, si tu sais que la racine est déjà contenue dans un intervalle limité de nombres entiers (par exemple entre 1 et 100), alors tu peux procéder par dichotomies successives, comme quand tu recherches une valeur dans une liste, à ceci près que tu compareras à x² au lieu de x seul (calculer le produit de x à chaque itération est trivial).
Non ce n'est pas un exercice scolaire, il y a longtemps que j'ai quitté l'école, je fais juste des recherches personnelles (à temps perdu) sur les nombres premiers , et mes recherches m'ont amené à savoir si une racine carré d'un nombre et entier ou non.
J'utilise la fonction sqrt() de math.h mais ça ne me permet pas de savoir si le nombre est entier ou non, il doit surement y avoir une astuce simple pour savoir ça.
Si. sqrt() te renvoie un double, c'est-à-dire un nombre réel, qui lui peut être entier ou pas.
Si tu veux savoir si un réel, float ou double, est entier en lui-même, indépendamment des différentes fonctions, tu peux par exemple utiliser rint() qui arrondit un réel à l'entier le plus proche. Il te suffit alors d'écrire if (x == rint(x))
Hello,
Si tes nombres en entrée sont des flottants, alors tu peux éliminer tous ceux qui ne sont pas entiers.
Il est aussi certainement possible d'éliminer rapidement certains nombres avec une lookup table : en décimal on sait qu'un carré se termine par 0, 1, 4, 5, 6 ou 9, c'est surement (j'ai pas la démonstration, mais ça me semble logique) pareil en binaire.
Il est aussi possible de stocker tous les carrés (si les nombres que tu testes sont dans un petit intervalle bien sur).
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42 inline unsigned int fastSqrt(unsigned int n) { // http://blog.quenta.org/2012/09/0x5f3759df.html float nhalf = 0.5f * n; int i = int(n); i = 0x1fbd1df5 - (i >> 1); float x = *(float*)&i; x = x*(1.5f-(nhalf * x * x)); return unsigned int(x); } inline bool isSqrtInt(unsigned int n) { // exemple avec une table vérifiant les 3 derniers bits (8 entrées) // ça peut bien sur s'agrandir, en gardant une taille raisonnable pour que // la table tienne entièrement en cache L1. // 8 bits -> 256 entrées -> 1ko, 2ko en 64 bits (? sizeof(bool) == 1, mais ça sera aligné sur 4/8 octets) // est probablement une taille correcte. // seuls les 3 bits de poids faible du résultat sont importants // 000 x 000 = 000 // 001 x 001 = 001 // 010 x 010 = 100 // 011 x 011 = 001 // 100 x 100 = 000 // 101 x 101 = 001 // 110 x 110 = 100 // 111 x 111 = 001 static const bool lut[] = { true, // 000 true, // 001 false, // 010 false, // 011 true, // 100 false, // 101 false, // 110 false // 111 }; if(lut[n & 7]) { unsigned int sq = fastSqrt(n); return sq*sq == n; } return false; }
Bonjour
La démonstration est facile: un chiffre entier se terminant par 0, 1, 2, 3, 4, 5, 6, 7, 8 ou 9, son carré se terminera par 0, 1, 4, 9, 6, 5, 6, 9, 4 ou 1 soit 0, 1, 4, 5, 6 ou 9.
Une démonstration ne se fait pas obligatoirement qu'avec des x et des y. Si l'ensemble de départ est un ensemble fini et dénombrable, alors t'as tout à fait le droit d'examiner chaque élément de l'ensemble de départ pour regarder s'il vérifie la propriété à démontrer. Et si tous la vérifient alors QED.
Généralement les propriétés à démontrer se font sur des ensembles infinis donc là, forcément, on est obligé de symboliser les éléments par des lettres. Mais quand on a la chance de tomber sur un cas fini, alors faut pas laisser passer l'occasion de briller facilement
Sinon pour la question initiale ben puisqu'on ne travaille qu'avec des entiers, moi j'éliminerais l'utilisation des flottants (toujours très longue) et je calculerais la racine carrée entière du nombre initial. Ca, ça peut se faire avec la formule de Heron (limite de la suite Un+1=1/2(Un+N/Un))
Code c : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 unsigned short racine2(unsigned long n) { unsigned long U[3]={0, 0, 1}; // Les 3 derniers calculs Un if (n == 0 || n == 1) return n; // Elimine les cas triviaux while (1) { U[0]=U[1]; // Décalage 3 derniers calculs U[1]=U[2]; U[2]=(U[1] + n/U[1]) >> 1; // Calcule le résultat actuel (Un). Un décalage de bits donne le même résultat qu'une divison par 2. // Si le dernier calcul est égal à un des deux précédents, on a atteint la limite de la suite if (U[2] == U[1] || U[2] == U[0]) return U[2]; } }
Bon, j'ai quand-même dû adapter aux nombres entiers. Parce qu'avec des flottants suffit de ne comparer que l'avant dernier élément de la suite avec le dernier mais avec des entiers, faut regarder les deux avant-derniers (sinon on tombe dans une boucle infinie x-1/x+1).
Et en plus le calcul n'est pas parfait. Par exemple, pour 35, il renvoie 6. La logique et les règles de calcul voudraient qu'il renvoie 5 mais les aléas de la suite (qui alterne avec pluspetit/plus grand) font qu'à ce moment c'était sur un "plus grand".
Toutefois pour les carrés parfait le calcul semble bon (testé sur les 65536 premiers carrés).
Et en ce qui concerne le nombre d'itérations dans la recherche de la racine, la plus grande concerne la racine de 666465852 qui fait faire 21 itérations.
Ensuite suffit de regarder si le carré du nombre renvoyé est égal au nombre initial...
Sinon il y a une autre solution qui part de la plage de valeur des nombres traités. Si tu travailles avec des unsigned short (65536 valeurs), tu n'auras que 256 carrés parfaits. Donc facile à mettre dans un tableau puis ensuite regarder si un de tes nombres s'y trouve.
Si maintenant tu travailles avec des unsigned long (4294967296 valeurs) ça te fait 65536 carrés parfaits. Toujours possible mais plus long...
Mon Tutoriel sur la programmation «Python»
Mon Tutoriel sur la programmation «Shell»
Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
Et on poste ses codes entre balises [code] et [/code]
Partager