Je cherche le moyen le plus rapide de déterminer si une valeur longue
est un carré parfait (c'est-à-dire que sa racine carrée est un autre entier) :
Math.sqrt()
][1]
intégrée, mais je me demande s'il n'existe pas un moyen de le faire plus rapidement en
en se limitant au domaine des entiers uniquement.Voici la façon très simple et directe dont je procède actuellement :
public final static boolean isPerfectSquare(long n)
{
if (n < 0)
return false;
long tst = (long)(Math.sqrt(n) + 0.5);
return tst*tst == n;
}
Note : J'utilise cette fonction dans de nombreux problèmes du Projet Euler. Ainsi, personne d'autre n'aura jamais à maintenir ce code. Et ce genre de micro-optimisation pourrait faire la différence, car une partie du défi consiste à réaliser chaque algorithme en moins d'une minute, et cette fonction devra être appelée des millions de fois dans certains problèmes
J'ai essayé les différentes solutions au problème :
Après des tests exhaustifs, j'ai trouvé que l'ajout de 0.5
au résultat de Math.sqrt() n'est pas nécessaire, du moins pas sur ma machine.
Le fast inverse square root était plus rapide, mais il donnait des résultats incorrects pour n >= 410881. Cependant, comme suggéré par BobbyShaftoe, nous pouvons utiliser le hack FISR pour n < 410881.
La méthode de Newton est un peu plus lente que Math.sqrt()
. Ceci est probablement dû au fait que Math.sqrt()
utilise quelque chose de similaire à la méthode de Newton, mais implémenté dans le matériel, ce qui le rend beaucoup plus rapide qu'en Java. De plus, la méthode de Newton nécessite toujours l'utilisation de doubles.
Une méthode de Newton modifiée, qui utilisait quelques astuces pour n'utiliser que des nombres entiers, nécessitait quelques bidouillages pour éviter les débordements (je veux que cette fonction fonctionne avec tous les nombres entiers signés positifs de 64 bits), et elle était toujours plus lente que Math.sqrt()
.
Le découpage binaire était encore plus lent. Cela est logique car le chop binaire nécessite en moyenne 16 passages pour trouver la racine carrée d'un nombre de 64 bits.
D'après les tests de John, l'utilisation d'instructions ou
est plus rapide en C++ que l'utilisation d'un switch
, mais en Java et C#, il ne semble pas y avoir de différence entre ou
et switch
.
J'ai également essayé de créer une table de consultation (comme un tableau statique privé de 64 valeurs booléennes). Ensuite, au lieu de l'instruction switch ou or
, j'ai simplement dit if(lookup[(int)(n&0x3F)]) { test } else return false;
. À ma grande surprise, cette méthode était (à peine) plus lente. C'est parce que les limites des tableaux sont vérifiées en Java.
[1] : https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/Math.html#sqrt(double)
Je pensais aux moments horribles que j'ai passés dans le cours d'analyse numérique.
Et puis je me souviens qu'il y avait cette fonction qui circulait sur le net à partir du code source de Quake :
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // wtf?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
return y;
}
qui calcule une racine carrée, en utilisant la fonction d'approximation de Newton (je ne me souviens pas du nom exact).
Il devrait être utilisable et pourrait même être plus rapide, il provient d'un des jeux phénoménaux d'id software !
Il est écrit en C++ mais il ne devrait pas être trop difficile de réutiliser la même technique en Java une fois que vous avez compris l'idée :
Je l'ai initialement trouvé à : http://www.codemaestro.com/reviews/9
La méthode de Newton expliquée sur wikipedia : http://en.wikipedia.org/wiki/Newton%27s_method
Vous pouvez suivre le lien pour plus d'explications sur son fonctionnement, mais si cela ne vous intéresse pas beaucoup, alors c'est en gros ce dont je me souviens en lisant le blog et en suivant le cours d'analyse numérique :
* (long*) &y
est essentiellement une fonction rapide de conversion en long pour que les opérations sur les entiers puissent être appliquées sur les octets bruts.0x5f3759df - (i >> 1);
est une valeur de départ pré-calculée pour la fonction d'approximation.* (float*) &i
convertit la valeur en virgule flottante.y = y * ( threehalfs - ( x2 * y * y )
itère à nouveau la valeur sur la fonction.La fonction d'approximation donne des valeurs plus précises au fur et à mesure que vous itérez la fonction sur le résultat. Dans le cas de Quake, une itération est "suffisante", mais si ce n'était pas le cas pour vous... alors vous pourriez ajouter autant d'itérations que nécessaire.
Cela devrait être plus rapide parce qu'il réduit le nombre d'opérations de division effectuées dans l'enracinement au carré naïf à une simple division par 2 (en fait une opération de multiplication * 0.5F
) et le remplace par un nombre fixe d'opérations de multiplication à la place.
Si vous effectuez un découpage binaire pour essayer de trouver la "bonne" racine carrée, vous pouvez assez facilement détecter si la valeur que vous avez obtenue est suffisamment proche pour le dire :
(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1
Donc, après avoir calculé n^2
, les options sont :
n^2 = cible
: fait, retourne vrai.n^2 + 2n + 1 > cible > n^2
: vous êtes proche, mais ce n'est pas parfait : return falsen^2 - 2n + 1 < cible < n^2
: idemtarget < n^2 - 2n + 1
: coupure binaire sur un n
inférieurtarget > n^2 + 2n + 1
: coupure binaire sur un n
supérieur(Désolé, ceci utilise n
comme votre estimation actuelle, et target
pour le paramètre. Je m'excuse pour la confusion)
Je ne sais pas si cela sera plus rapide ou non, mais ça vaut le coup d'essayer.
EDIT : Le découpage binaire n'a pas besoin de prendre en compte toute la gamme d'entiers, ni (2^x)^2 = 2^(2x)
, donc une fois que vous avez trouvé le bit le plus haut dans votre cible (ce qui peut être fait avec un truc de bit-twiddling ; j'ai oublié exactement comment) vous pouvez rapidement obtenir une gamme de réponses potentielles. Attention, un découpage binaire naïf ne prendra toujours que 31 ou 32 itérations.
Si vous voulez de la rapidité, étant donné que vos entiers sont de taille finie, je pense que la méthode la plus rapide consisterait à (a) partitionner les paramètres par taille (par exemple, en catégories selon le plus grand ensemble de bits), puis à vérifier la valeur par rapport à un tableau de carrés parfaits dans cette plage.