Quel est le moyen le plus rapide de déterminer si la racine carrée d'un entier est un entier ?

Le moyen le plus rapide de déterminer si la racine carrée d'un entier est un entier

Description du problème

Je recherche le manière la plus rapide Méthode pour déterminer si un entier long est un carré parfait (c'est-à-dire que sa racine carrée est un autre entier) :

1. Je l'ai fait en utilisant la fonction Math.sqrt() intégrée, mais je suis curieux de savoir s'il existe un moyen de le faire en utilisant des champs entiers, augmentant ainsi la vitesse.


2. Il n'est pas pratique de maintenir une table de recherche (puisqu'il y a environ 2^31,5 entiers dont les carrés sont inférieurs à 2⁶³).

Voici la façon très simple et directe de procéder maintenant :

{<br> if (n < 0)</p><div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">return false;

Copier après la connexion

long tst = (long)(Math.sqrt(n) 0.5);
return tst*tst == n;
}

_{Remarque : j'utilise cette fonction dans de nombreux problèmes du projet Euler. Par conséquent, il n’y aura aucune maintenance sur ce code à l’avenir. Et cette micro-optimisation peut réellement faire la différence, car une partie du défi consiste à prendre moins d'une minute pour terminer chaque algorithme, alors que cette fonction doit être appelée des millions de fois dans certains problèmes.}

---

J'ai essayé différentes solutions à ce problème :

• Après des tests exhaustifs, j'ai trouvé qu'ajouter 0,5 au résultat de Math.sqrt() n'est pas nécessaire, du moins sur ma machine.


• La racine carrée inverse rapide est plus rapide que Math.sqrt() mais donne des résultats incorrects pour n >= 410881. Cependant, comme l'a suggéré BobbyShaftoe, nous pouvons utiliser le hack FISR pour n
• La méthode de Newton est beaucoup plus lente que Math.sqrt(). C'est probablement parce que Math.sqrt() utilise quelque chose de similaire à la méthode de Newton, mais est implémentée matériellement et donc beaucoup plus rapide qu'en Java. De plus, la méthode de Newton nécessite toujours l’utilisation de nombres à virgule flottante double précision.
entier signé positif de 64 bits), et il est plus lent que Math.sqrt().

• La recherche binaire est encore plus lente. Cela est logique, puisqu'une recherche binaire nécessite en moyenne 16 passes pour trouver la racine carrée d'un nombre de 64 bits.


• Selon les tests de John, l'utilisation d'une instruction or est plus rapide que l'utilisation d'un commutateur en C, mais en Java et C#, il ne semble y avoir aucune différence entre un or et un commutateur.


• J'ai également essayé de créer une table de recherche (sous forme de tableau statique privé de 64 booléens). Ensuite, au lieu d'utiliser une instruction switch ou or, je dirais simplement if(lookup[(int)(n&0x3F)]) { test } else return false;. À ma grande surprise, c'est (légèrement) plus lent. En effet, les limites du tableau sont vérifiées en Java.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!