Le Double Piégeux
Autres langues : English Español Deutsch 日本語 한국어 Português 中文
Ce texte est une traduction de l’article original de mon ami, Maksim Pelevin. Si vous êtes à l’aise avec la lecture en russe, vous pourriez trouver d’autres articles intéressants dans son blog.
Vous le savez déjà :
Le type de données double n’est pas très précis
Renforçons cette compréhension en résolvant un problème sur CodeWars.
Énoncé du problème
La tâche telle que décrite sur CodeWars est la suivante :
Votre tâche est de construire un bâtiment, qui sera une pile de n cubes. Le cube en bas aura un volume de n^3, le cube au-dessus aura un volume de (n-1)^3 et ainsi de suite jusqu’au sommet qui aura un volume de 1^3.
On vous donne le volume total m du bâtiment. Étant donné m, pouvez-vous trouver le nombre n de cubes que vous devrez construire ?
Le paramètre de la fonction findNb sera un entier m
et vous devez retourner l’entier n tel que
n^3 + (n-1)^3 + … + 1^3 = m si un tel n existe ou -1 s’il n’existe pas de tel n.
Solution naïve
La solution la plus directe utilisant des boucles serait quelque chose comme :
public static long findNb(long m) {
long n = 0, totalVolume = 0;
while (totalVolume < m) {
totalVolume += ++n * n * n;
}
return totalVolume == m ? n : -1;
}Solution mathématique
À l’université, j’ai appris les séries mathématiques et les méthodes pour calculer leurs sommes, alors voici ma tentative de solution mathématique.
Je ne me souviens plus des formules, mais heureusement, Wolfram Alpha est là pour aider. Pour obtenir la formule, lançons la requête suivante : n^3, n = 1 to k.
Les résultats nous indiquent que :
Substituons m au côté gauche de l’équation,
puis appliquons la propriété de la racine carrée
et multiplions les deux côtés de l’équation par deux.
Après simplification, nous obtenons :
Écrire le code
Voici une solution pour l’équation ci-dessus, écrite en Java :
public static long findNb(long m) {
double res = Math.sqrt(m);
double d = 1 + 8 * res;
double n = (Math.sqrt(d) - 1) / 2;
return n - Math.floor(n) == 0 ? (long) n : -1;
}Résultats
Il s’avère que ce code retourne un résultat incorrect pour un sous-ensemble des données de test.
Cette incohérence est visible, par exemple, lorsque
vous passez 1646842954019151682L en entrée.
Lors du calcul d’une racine carrée en Java, vous pouvez obtenir un résultat qui n’est pas totalement précis. Regardons :
System.out.println(String.format("%.30f", Math.sqrt(1646842954019151682L)));
// output 1283293791.000000000000000000000000000000
// correct 1283293791.00000000038962239473657673134031176401122912...Évidemment, la sortie et la réponse correcte sont différentes. Fin !
Conclusion
La solution la plus techniquement correcte et potentiellement la plus rapide n’est pas toujours la meilleure à choisir. Cela peut ne pas surprendre un développeur expérimenté, mais les nouveaux en programmation pourraient chercher la cause de l’erreur pendant un bon moment.
Si vous vous demandez comment corriger le problème avec la solution mathématique,
une approche est d’utiliser BigDecimal . Ce code passe tous les tests :
public static long findNb(long m) {
MathContext mc = new MathContext(64);
BigDecimal res = BigDecimal.valueOf(m).sqrt(mc);
BigDecimal d = res.multiply(BigDecimal.valueOf(8)).add(BigDecimal.ONE);
BigDecimal n = d.sqrt(mc).subtract(BigDecimal.ONE).divide(BigDecimal.valueOf(2));
return Objects.equals(n, n.setScale(0, RoundingMode.FLOOR)) ? n.longValue() : -1;
}… et un petit bonus : pouvez-vous deviner lequel des suivants est true ,
et lequel est false ?
(1646842954019151681L == 1646842954019151682D)(1646842954019151681L == (long) 1646842954019151682D)
