Dans un concours de programmation, j'ai résumé les pièges auxquels j'étais accro et comment les éviter, ainsi que ma propre réflexion sur les erreurs de la méthode Math.sqrt de Java.
La méthode sqrt de la classe Java Math est une méthode qui peut trouver la racine carrée d'une valeur numérique donnée par le type double, et est souvent utilisée lors de l'exécution de calculs numériques.
Cependant, bien sûr, il existe des divergences dans les résultats.
Dans de nombreux cas, le résultat sera négligeable, mais dans certains cas, l'erreur sera non négligeable.
Dans cet article, je vais vous montrer quelques-uns des cas que j'ai rencontrés et vous donner des exemples pour les éviter.
Dans un concours de programmation auquel j'ai participé, j'avais besoin d'écrire le code suivant.
Étant donné un entier positif $ a $ qui satisfait $ a \ leq 10 ^ {18} $, je veux trouver la valeur maximale de $ b $ qui satisfait $ b ^ {2} <a $.
Voici le code que j'ai écrit en premier. (Ajouté le 9 avril 2018) Comme vous l'avez souligné dans les commentaires, ce code est un peu inutile. «Exemple de version corrigée du code» a été ajouté à la fin.
sample1.java(Extrait)
private static long floorSqrt (long a) {
long b = (long)Math.sqrt(a);
if (b*b == a) {
return b-1;
} else {
return b;
}
}
Je vais vous expliquer brièvement.
À première vue, cela semble fonctionner, mais le code ci-dessus ne fonctionne pas.
(Ajouté le 9 avril 2018) Comme vous l'avez souligné dans les commentaires, ce code est un peu inutile. «Exemple de version corrigée du code» a été ajouté à la fin.
sample1.java
public class Sample1 {
public static void main(String[] args) {
System.out.println("lessThanSqrt (99)=" + lessThanSqrt (99));
System.out.println("lessThanSqrt (100)=" + lessThanSqrt (100));
System.out.println("lessThanSqrt (999999999)=" + lessThanSqrt (9999999999L));
System.out.println("lessThanSqrt (10000000000)=" + lessThanSqrt (10000000000L));
System.out.println("lessThanSqrt (999999999999999999)="+lessThanSqrt (999999999999999999L));
System.out.println("lessThanSqrt (1000000000000000000)=" + lessThanSqrt (1000000000000000000L));
}
private static long lessThanSqrt (long a) {
long b = (long)Math.sqrt(a);
if (b*b == a) {
return b-1;
} else {
return b;
}
}
Le résultat de l'exécution de l'exemple de code ci-dessus est le suivant.
lessThanSqrt (99)=9
lessThanSqrt (100)=9
lessThanSqrt (999999999)=99999
lessThanSqrt (10000000000)=99999
lessThanSqrt (999999999999999999)=1000000000
lessThanSqrt (1000000000000000000)=999999999
Si la valeur est extrêmement élevée, le résultat est étrange.
La cause de cela peut être comprise en examinant le résultat de l'exécution de l'exemple de code ci-dessous.
sample1_1.java
public class Sample1_1 {
public static void main(String[] args) {
System.out.println(Math.sqrt(99999999999999L));
System.out.println(Math.sqrt(100000000000000L));
System.out.println(Math.sqrt(9999999999999999L));
System.out.println(Math.sqrt(10000000000000000L));
System.out.println(Math.sqrt(999999999999999999L));
System.out.println(Math.sqrt(1000000000000000000L));
}
}
Résultat d'exécution
9999999.99999995
1.0E7
1.0E8
1.0E8
1.0E9
1.0E9
En regardant les résultats ci-dessus, si $ n> 8 $, les résultats de $ \ sqrt {10 ^ {2n}} $ et $ \ sqrt {10 ^ {2n} -1} $ sont les mêmes. Je suis.
Il s'agit d'un problème de précision de type double.
En ce qui concerne la précision du type double, étant donné que seuls 15 chiffres environ d'informations peuvent être conservés, il n'est pas possible de conserver des informations avec un plus grand nombre de chiffres, ce qui entraîne une erreur par rapport à la valeur d'origine.
Dans la plupart des cas, l'effet est faible, mais si le nombre de chiffres de la partie fractionnaire est égal à 9, le nombre de la partie entière peut changer en raison d'une erreur.
La situation ci-dessus est susceptible de se produire lors du calcul de la racine carrée d'un grand nombre.
Vous trouverez ci-dessous le code qui prend en compte les problèmes de l'exemple de code 1 et ajoute une logique pour corriger l'erreur. (Ajouté le 9 avril 2018) Comme vous l'avez souligné dans les commentaires, ce code est un peu inutile. «Exemple de version corrigée du code» a été ajouté à la fin.
sample2.java
public class Sample2 {
public static void main(String[] args) {
System.out.println("lessThanSqrt (99)=" + lessThanSqrt (99));
System.out.println("lessThanSqrt (100)=" + lessThanSqrt (100));
System.out.println("lessThanSqrt (999999999)=" + lessThanSqrt (9999999999L));
System.out.println("lessThanSqrt (10000000000)=" + lessThanSqrt (10000000000L));
System.out.println("lessThanSqrt (999999999999999999)="+lessThanSqrt (999999999999999999L));
System.out.println("lessThanSqrt (1000000000000000000)=" + lessThanSqrt (1000000000000000000L));
}
private static long lessThanSqrt (long a) {
long b = longSqrt(a);
if (b*b == a) {
return b-1;
} else {
return b;
}
}
private static long longSqrt (long a) {
long b = (long)Math.sqrt(a);
//Si la valeur obtenue est au carré et dépasse la valeur d'origine
//Parce que l'erreur est 1 plus grande
//Renvoie la valeur moins 1 pour corriger l'erreur
if(b*b > a) {
b--;
}
return b;
}
}
Résultat d'exécution
lessThanSqrt (99)=9
lessThanSqrt (100)=9
lessThanSqrt (999999999)=99999
lessThanSqrt (10000000000)=99999
lessThanSqrt (999999999999999999)=999999999
lessThanSqrt (1000000000000000000)=999999999
Vous pouvez maintenant obtenir les bons résultats.
Non limité à + sqrt, en général, lors de l'exécution de calculs de type virgule flottante, il est nécessaire de prendre en compte les erreurs. Si vous ne gérez généralement pas trop les types à virgule flottante, vous avez tendance à manquer de considération, alors soyez prudent.
Voici une correction de la partie inutile de l'exemple de code en un code efficace.
Sample1Modified.java(Extrait)
private static long lessThanSqrt (long a) {
return (long)Math.sqrt(a-1);
}
Sample2Modified.java(Extrait)
private static long lessThanSqrt (long a) {
return longSqrt(a-1);
}
Il suffit de prendre $ \ sqrt {a-1} $ sans diviser la casse.
Recommended Posts