J'écris un programme qui essaie de trouver la valeur minimale de k> 1 telle que la kème racine de a et b (qui sont toutes deux données) égale un nombre entier.
Voici un extrait de mon code, que j'ai commenté pour clarification.
int main()
{
// Declare the variables a and b.
double a;
double b;
// Read in variables a and b.
while (cin >> a >> b) {
int k = 2;
// We require the kth root of a and b to both be whole numbers.
// "while a^{1/k} and b^{1/k} are not both whole numbers..."
while ((fmod(pow(a, 1.0/k), 1) != 1.0) || (fmod(pow(b, 1.0/k), 1) != 0)) {
k++;
}
À peu près, j'ai lu dans (a, b), et je commence à partir de k = 2 et incrémente k jusqu'aux kèmes racines de a et b sont tous deux congruents à 0 mod 1 (ce qui signifie qu'ils sont divisibles par 1 et donc des nombres entiers).
Mais, la boucle tourne indéfiniment. J'ai essayé de faire des recherches et je pense que cela pourrait être lié à une erreur de précision; cependant, je ne suis pas trop sûr.
Une autre approche que j'ai essayée est de changer la condition de boucle pour vérifier si le plancher d'un ^ {1 / k} est égal à un ^ {1 / k} lui-même. Mais encore une fois, cela fonctionne indéfiniment, probablement en raison d'une erreur de précision.
Est-ce que quelqu'un sait comment je peux résoudre ce problème?
EDIT: par exemple, quand (a, b) = ( 216, 125), je veux avoir k = 3 car 216 ^ (1/3) et 125 ^ (1/3) sont tous deux des entiers (à savoir, 5 et 6).
3 Réponses :
Les nombres flottants ne sont pas des nombres réels mathématiques. Le calcul est "approximatif". Voir http://floating-point-gui.de/
Vous pouvez remplacer le test fmod (pow (a, 1.0 / k), 1)! = 1.0 par quelque chose comme fabs (fmod (pow (a, 1.0 / k), 1) - 1.0)> 0.0000001 (et jouez avec divers 𝛆 au lieu de 0.0000001 ; voir aussi std :: numeric_limits :: epsilon mais utilisez-le avec précaution, car pow peut donner des erreurs dans ses calculs, et 1.0 / k injecte également des imprécisions - les détails sont très complexes, plongez dans les spécifications IEEE754 ).
Bien sûr, vous pouvez (et devriez probablement) définir votre fonction bool near_equal (double x, double y) (et l'utiliser à la place de == , et utiliser sa négation au lieu de ! = ).
En règle générale, ne testez jamais l'égalité des nombres flottants (c'est-à-dire == ), mais considérez plutôt une distance assez petite entre eux; autrement dit, remplacez un test comme x == y (respectivement x! = y ) par quelque chose comme fabs (xy) fabs (xy)> EPSILON ) où EPSILON est un petit nombre positif, d'où le test d'un petit L 1 distance (pour l'égalité, et une distance suffisamment grande pour l'inégalité).
Et évitez les virgules flottantes dans les problèmes d'entiers.
En fait, prédire ou estimer la précision en virgule flottante est très difficile. Vous pouvez envisager des outils tels que CADNA . Mon collègue Franck Védrine est un expert des analyseurs de programmes statiques pour estimer les erreurs numériques (voir par exemple son Présentation TERATEC 2017 sur Fluctuat ). C'est un sujet de recherche difficile, voir aussi l'article de D.Monniaux les pièges de la vérification calculs en virgule flottante etc.
Et les erreurs en virgule flottante dans certains cas < / a> a coûté des vies humaines (ou la perte de milliards de dollars). Recherchez des détails sur le Web. Il y a des cas où tous les chiffres d'un nombre calculé sont faux (car les erreurs peuvent s'accumuler, et le résultat final a été obtenu en combinant des milliers d'opérations)! Il existe une relation indirecte avec la théorie du chaos , car de nombreux programmes peuvent avoir une instabilité numérique .
OK, j'ai compris. Mais juste une chose - la condition de boucle ne devrait-elle pas être "fabs (fmod (pow (a, 1.0 / k), 1) - 1.0)> = 0.0000001", puisque nous voulons continuer à boucler alors que l'instruction n'est pas vraie?
également en valeur absolue, nous devrions soustraire 0,0 plutôt que 1,0, non? puisqu'ils seraient congruents à 0 mod 1? juste pour être sûr...
Il s'agit de calculer une distance. Vous pouvez même utiliser une distance euclidienne , mais cela prend plus de temps à être calculé.
Oui. actuellement, le booléen teste si la valeur de fmod (pow (a, 1.0 / k), 1) est dans epsilon de 1. mais ne devrait-il pas tester si elle est dans epsilon de 0? puisque nous voulons que la condition while soit évaluée à "false" quand ils sont tous les deux des entiers, ce qui se produit précisément lorsque les kèmes racines de a et b sont égales à 0 mod 1, pas 1 mod 1
Vous voulez que fmod (pow (a, 1.0 / k), 1) (appelez cela x ) soit suffisamment différent de 1.0 (appelez-le y ). Vous voulez donc que fabs (x-y) soit plus grand que certains EPSILON
Mais alors le code se brise lorsque, par exemple, (a, b) = (5764801, 1679616). Il devrait renvoyer k = 4 puisque les quantités (5764801) ^ (1/4) et (1679616) ^ (1/4) sont toutes deux des entiers (à savoir, 49 et 36). Cependant, lorsque nous avons k = 4, la valeur de 5764801 ^ (1/4) mod 1 est égale à 0 et la quantité fabs (x - y) est égale à 1. Puisque cette valeur est supérieure à epsilon, la première expression booléenne devient " vrai, "et la boucle continue pour toujours
Aucune des deux erreurs dans le lien que vous fournissez n'était des erreurs en virgule flottante. Le premier était à virgule fixe. Le second était la conversion en un entier trop étroit (pour lequel le format source n'est pas pertinent, car toute conversion d'une valeur en un type dans lequel elle ne peut pas être représentée est une erreur, quelle que soit la façon dont la valeur source est représentée).
Comme d'autres l'ont mentionné, comparer des valeurs à virgule flottante pour l'égalité est problématique. Si vous trouvez un moyen de travailler directement avec des entiers, vous pouvez éviter ce problème. Une façon de le faire est d'élever les entiers à la puissance k au lieu de prendre la racine k e. Les détails sont laissés à titre d’exercice pour le lecteur.
Ce n'est pas un problème de programmation mais un problème mathématique:
si
aest un réel, etkun entier positif, et sia ^ (1./k)est un entier, alorsaest un entier. (sinon le but est de jouer avec une erreur d'approximation)
L'approche la plus rapide peut donc être de vérifier d'abord si a et b sont des nombres entiers, puis de faire un décomposition prime telle que a = p 0 e 0 * p < sub> 1 e 1 * ..., où p i sont des nombres premiers distincts.
Notez que, pour qu'un 1 / k soit un entier, chaque e i doit également être divisible par k. En d'autres termes, k doit être un diviseur commun du e i . La même chose doit être vraie pour les puissances premières de b si b 1 / k doit être un entier.
Ainsi, le plus grand k est le le plus grand diviseur commun de tous les e i des deux a et b .
Avec votre approche, vous aurez des problèmes avec les grands nombres. Toutes les virgules flottantes binaires64 IIEEE 754 (le cas du double sur x86) ont 53 bits significatifs. Cela signifie que tous les doubles supérieurs à 2 53 sont des nombres entiers.
La fonction pow (x, 1. / k) donnera la même valeur pour deux x différents, de sorte qu'avec votre approche vous aurez nécessairement une fausse réponse , par exemple les nombres 5 5 * 2 90 et 3 5 * 2 120 sont exactement représentables par double. Le résultat de l'algorithme est k = 5 . Vous pouvez trouver cette valeur de k avec ces nombres mais vous trouverez également k = 5 pour 5 5 * 2 90 -2 49 et 3 5 * 2 120 , car pow (5 5 * 2 90 -2 49 , 1. / 5) == pow (5 5 * 2 90 ). Démo ici
D'un autre côté, comme il n'y a que 53 bits significatifs, la décomposition en nombre premier du double est triviale.
Avec des nombres à virgule flottante, il est déraisonnable de tester l’égalité. Voir floating-point-gui.de
Pourquoi une valeur de retour est-elle testée par rapport à
1.0et l'autre uniquement par rapport à0?Lire ericlippert.com/2014/03/05/how- to-debug-small-programs pour obtenir des conseils sur le débogage de votre code.
Valeur minimale de k ou valeur minimale de 1 / k (qui correspond à la valeur maximale de k)? Ce dernier semble plus intéressant et donc plus susceptible d'être le problème réel à résoudre.
(J'ai vu que vous avez supprimé votre question sur la somme de deux entiers . Pour ce que ça vaut, j'ai essayé de corriger mon code pour gérer l'exemple de compteur que vous avez trouvé. Ici: ideone.com/JKRkqy )