Moyen le plus rapide pour déterminer si la racine carrée d'un entier est un entier

je suis assez en retard à la partie, mais j'espère fournir une meilleure réponse; plus court et (en supposant mon benchmark est correct) aussi beaucoup plus rapide .

long goodMask; // 0xC840C04048404040 computed below
{
    for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i);
}

public boolean isSquare(long x) {
    // This tests if the 6 least significant bits are right.
    // Moving the to be tested bit to the highest position saves us masking.
    if (goodMask << x >= 0) return false;
    final int numberOfTrailingZeros = Long.numberOfTrailingZeros(x);
    // Each square ends with an even number of zeros.
    if ((numberOfTrailingZeros & 1) != 0) return false;
    x >>= numberOfTrailingZeros;
    // Now x is either 0 or odd.
    // In binary each odd square ends with 001.
    // Postpone the sign test until now; handle zero in the branch.
    if ((x&7) != 1 | x <= 0) return x == 0;
    // Do it in the classical way.
    // The correctness is not trivial as the conversion from long to double is lossy!
    final long tst = (long) Math.sqrt(x);
    return tst * tst == x;
}

le premier test prend la plupart des non-carrés rapidement. Il utilise une table de 64 éléments empaquetés dans une longue, il n'y a donc pas de coût d'accès au tableau (contrôles indirects et limites). Pour uniformément aléatoire long , il y a une probabilité de 81,25% de finir ici.

le deuxième test prend tous les nombres ayant un nombre impair de deux dans leur factorisation. La méthode Long.numberOfTrailingZeros est très rapide car il obtient JIT-ed dans une seule instruction i86.

après avoir laissé tomber les zéros de queue, le troisième test traite les nombres se terminant par 011, 101, ou 111 en binaire, qui ne sont pas des carrés parfaits. Il se soucie également des nombres négatifs et traite aussi 0.

Le test final revient à l'arithmétique double . Comme double a seulement 53 bits mantissa, la conversion de long en double inclut l'arrondissement pour les grandes valeurs. Néanmoins, le test est correct (à moins que la preuve est erronée).

essayer d'intégrer l'idée mod255 n'a pas réussi.

vous devrez faire une analyse comparative. Le meilleur algorithme dépend de la distribution de vos entrées.

votre algorithme peut être presque optimal, mais vous pourriez vouloir faire une vérification rapide pour écarter quelques possibilités avant d'appeler votre routine racine carrée. Par exemple, regardez le dernier chiffre de votre nombre en hexadécimal, en faisant un peu sage "et."Les carrés parfaits ne peuvent finir qu'en 0, 1, 4, ou 9 en base 16, donc pour 75% de vos entrées (en supposant qu'ils sont uniformément distribué), vous pouvez éviter un appel à la racine carrée en échange de quelques très rapide peu tourner.

Kip Référencé le code suivant implémentant le truc hex. Lors du test des numéros 1 à 100 000 000, ce code a couru deux fois plus vite que l'original.

public final static boolean isPerfectSquare(long n)
{
    if (n < 0)
        return false;

    switch((int)(n & 0xF))
    {
    case 0: case 1: case 4: case 9:
        long tst = (long)Math.sqrt(n);
        return tst*tst == n;

    default:
        return false;
    }
}

quand j'ai testé le code analogue en C++, il fonctionnait en fait plus lentement que l'original. Cependant, quand j'ai éliminé l'instruction switch, le HEX trick fait à nouveau le code deux fois. aussi vite.

int isPerfectSquare(int n)
{
    int h = n & 0xF;  // h is the last hex "digit"
    if (h > 9)
        return 0;
    // Use lazy evaluation to jump out of the if statement as soon as possible
    if (h != 2 && h != 3 && h != 5 && h != 6 && h != 7 && h != 8)
    {
        int t = (int) floor( sqrt((double) n) + 0.5 );
        return t*t == n;
    }
    return 0;
}

L'élimination de la déclaration de l'interrupteur a eu peu d'effet sur le code C#.

je pensais aux moments horribles que j'ai passés en cours D'analyse numérique.

et puis je me souviens, il y avait cette fonction encerclant le 'net à partir du code source du séisme:

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 essentiellement une racine carrée, en utilisant la fonction d'approximation de Newton (ne peut se rappeler le nom exact).

il devrait être utilisable et pourrait même être plus rapide, il est d'un des jeux du logiciel phénoménal id!

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 l'idée:

Je l'ai trouvé à l'origine à: http://www.codemaestro.com/reviews/9

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 la façon dont il fonctionne, mais si vous ne vous souciez pas beaucoup, alors c'est à peu près ce que je me souviens de la lecture du blog et de prendre le cours D'analyse numérique:

• le * (long*) &y est fondamentalement une fonction de conversion rapide en fonction longue de sorte que des opérations entières peuvent être appliquées sur les octets bruts.
• la ligne 0x5f3759df - (i >> 1); est une valeur prédéfinie pour la fonction d'approximation.
• le * (float*) &i convertit la valeur en point flottant.
• la ligne y = y * ( threehalfs - ( x2 * y * y ) ) itère bascialement la valeur sur la fonction à nouveau.

la fonction d'approximation donne des valeurs plus précises plus vous itérez la fonction sur le résultat. Dans le cas de Quake, une itération est "assez bonne", mais si ce n'était pas pour vous... ensuite, vous pouvez ajouter autant d'itération que vous avez besoin.

cela devrait être plus rapide parce qu'il réduit le nombre d'opérations de division effectuées en enracinement carré naïf jusqu'à une simple division par 2 (en fait une opération de multiplication * 0.5F ) et la remplacer par un nombre fixe d'opérations de multiplication.

Je ne suis pas sûr que ce soit plus rapide, ou même précis, mais vous pouvez utiliser racine carrée magique de John Carmack , algorithme pour résoudre la racine carrée plus rapidement. Vous pourriez probablement facilement tester cela pour tous les entiers 32 bits possibles, et valider que vous avez réellement obtenu des résultats corrects, car il est seulement une appoximation. Cependant, maintenant que j'y pense, utiliser des doubles est aussi approximatif, donc je ne sais pas comment cela pourrait entrer en jeu.

Si vous faites un binaire chop pour essayer de trouver le "bon" racine carrée, vous pouvez assez facilement détecter si la valeur que vous avez est assez proche pour dire:

(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1

donc, ayant calculé n^2 , les options sont:

• n^2 = target : fait, return true
• n^2 + 2n + 1 > target > n^2 : vous êtes proche, mais il n'est pas parfait: return false
• n^2 - 2n + 1 < target < n^2 : idem
• target < n^2 - 2n + 1 : cône binaire sur un bas n
• target > n^2 + 2n + 1 : cône binaire sur un haut n

(désolé, cela utilise n comme votre supposition actuelle, et target pour le paramètre. Excusez la confusion!)

Je ne sais pas si ce sera plus rapide ou pas, mais ça vaut le coup d'essayer.

EDIT: le chop binaire n'a pas à prendre dans l'ensemble gamme d'entiers, soit (2^x)^2 = 2^(2x) , donc une fois que vous avez trouvé le meilleur bit défini dans votre cible (ce qui peut être fait avec un tour de bit-twiddling; j'oublie exactement comment), vous pouvez obtenir rapidement une gamme de réponses potentielles. Attention, une chop binaire naïve ne prendra que 31 ou 32 itérations.

j'ai effectué ma propre analyse de plusieurs algorithmes dans ce fil et j'ai obtenu de nouveaux résultats. Vous pouvez voir ces vieux résultats dans l'historique éditer de cette réponse, mais ils ne sont pas exacts, car j'ai fait une erreur, et perdu du temps à analyser plusieurs algorithmes qui ne sont pas proches. Cependant, tirant des leçons de plusieurs réponses différentes, j'ai maintenant deux algorithmes qui écrasent le "gagnant" de ce fil. Voici l'essentiel que je fais différemment des autres:

// This is faster because a number is divisible by 2^4 or more only 6% of the time
// and more than that a vanishingly small percentage.
while((x & 0x3) == 0) x >>= 2;
// This is effectively the same as the switch-case statement used in the original
// answer. 
if((x & 0x7) != 1) return false;

cependant, cette ligne simple, qui la plupart du temps ajoute une ou deux instructions très rapides, simplifie grandement l'énoncé switch-case en un seul énoncé if. Cependant, il peut ajouter à l'exécution si de nombreux testé nombre considérable de puissance de deux facteurs.

les algorithmes ci-dessous sont les suivants:

• Internet - de Kip posté réponse
• Durron - Mon modifiée réponse à l'aide de l'un des passe-réponse à une base de
• DurronTwo -ma réponse modifiée en utilisant la réponse en deux passages (par @JohnnyHeggheim), avec quelques autres légères modifications.

voici un exemple d'exécution si les nombres sont générés en utilisant Math.abs(java.util.Random.nextLong())

 0% Scenario{vm=java, trial=0, benchmark=Internet} 39673.40 ns; ?=378.78 ns @ 3 trials
33% Scenario{vm=java, trial=0, benchmark=Durron} 37785.75 ns; ?=478.86 ns @ 10 trials
67% Scenario{vm=java, trial=0, benchmark=DurronTwo} 35978.10 ns; ?=734.10 ns @ 10 trials

benchmark   us linear runtime
 Internet 39.7 ==============================
   Durron 37.8 ============================
DurronTwo 36.0 ===========================

vm: java
trial: 0

et voici un échantillon runtime si il est exécuté sur le premier million de longueurs seulement:

 0% Scenario{vm=java, trial=0, benchmark=Internet} 2933380.84 ns; ?=56939.84 ns @ 10 trials
33% Scenario{vm=java, trial=0, benchmark=Durron} 2243266.81 ns; ?=50537.62 ns @ 10 trials
67% Scenario{vm=java, trial=0, benchmark=DurronTwo} 3159227.68 ns; ?=10766.22 ns @ 3 trials

benchmark   ms linear runtime
 Internet 2.93 ===========================
   Durron 2.24 =====================
DurronTwo 3.16 ==============================

vm: java
trial: 0

comme vous pouvez le voir, DurronTwo fait mieux pour de grandes entrées, parce qu'il obtient d'utiliser le tour de magie très souvent, mais obtient saboté par rapport au premier algorithme et Math.sqrt parce que les nombres sont tellement plus petits. Pendant ce temps, le plus simple Durron est un énorme gagnant parce qu'il n'a jamais à diviser par 4 beaucoup de fois dans le premier million de numéros.

Voici Durron :

public final static boolean isPerfectSquareDurron(long n) {
    if(n < 0) return false;
    if(n == 0) return true;

    long x = n;
    // This is faster because a number is divisible by 16 only 6% of the time
    // and more than that a vanishingly small percentage.
    while((x & 0x3) == 0) x >>= 2;
    // This is effectively the same as the switch-case statement used in the original
    // answer. 
    if((x & 0x7) == 1) {

        long sqrt;
        if(x < 410881L)
        {
            int i;
            float x2, y;

            x2 = x * 0.5F;
            y  = x;
            i  = Float.floatToRawIntBits(y);
            i  = 0x5f3759df - ( i >> 1 );
            y  = Float.intBitsToFloat(i);
            y  = y * ( 1.5F - ( x2 * y * y ) );

            sqrt = (long)(1.0F/y);
        } else {
            sqrt = (long) Math.sqrt(x);
        }
        return sqrt*sqrt == x;
    }
    return false;
}

et DurronTwo

public final static boolean isPerfectSquareDurronTwo(long n) {
    if(n < 0) return false;
    // Needed to prevent infinite loop
    if(n == 0) return true;

    long x = n;
    while((x & 0x3) == 0) x >>= 2;
    if((x & 0x7) == 1) {
        long sqrt;
        if (x < 41529141369L) {
            int i;
            float x2, y;

            x2 = x * 0.5F;
            y = x;
            i = Float.floatToRawIntBits(y);
            //using the magic number from 
            //http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
            //since it more accurate
            i = 0x5f375a86 - (i >> 1);
            y = Float.intBitsToFloat(i);
            y = y * (1.5F - (x2 * y * y));
            y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate
            sqrt = (long) ((1.0F/y) + 0.2);
        } else {
            //Carmack hack gives incorrect answer for n >= 41529141369.
            sqrt = (long) Math.sqrt(x);
        }
        return sqrt*sqrt == x;
    }
    return false;
}

et mon harnais de référence: (nécessite Google caliper 0.1-rc5)

public class SquareRootBenchmark {
    public static class Benchmark1 extends SimpleBenchmark {
        private static final int ARRAY_SIZE = 10000;
        long[] trials = new long[ARRAY_SIZE];

        @Override
        protected void setUp() throws Exception {
            Random r = new Random();
            for (int i = 0; i < ARRAY_SIZE; i++) {
                trials[i] = Math.abs(r.nextLong());
            }
        }


        public int timeInternet(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if(SquareRootAlgs.isPerfectSquareInternet(trials[j])) trues++;
                }
            }

            return trues;   
        }

        public int timeDurron(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if(SquareRootAlgs.isPerfectSquareDurron(trials[j])) trues++;
                }
            }

            return trues;   
        }

        public int timeDurronTwo(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if(SquareRootAlgs.isPerfectSquareDurronTwo(trials[j])) trues++;
                }
            }

            return trues;   
        }
    }

    public static void main(String... args) {
        Runner.main(Benchmark1.class, args);
    }
}

UPDATE: j'ai fait un nouvel algorithme qui est plus rapide dans certains scénarios, plus lent dans d'autres, j'ai obtenu différents benchmarks basés sur différentes entrées. Si nous calculons modulo 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241 , nous pouvons éliminer 97,82% des nombres qui ne peuvent pas être carrés. Cela peut être (en quelque sorte) fait en une ligne, avec 5 opérations bitwise:

if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;

L'indice est soit 1) le résidu, 2) le résidu + 0xFFFFFF , ou 3) le résidu + 0x1FFFFFE . Bien sûr , nous avons besoin d'une table de recherche pour les résidus modulo 0xFFFFFF , qui est d'environ un fichier de 3 Mo (dans ce cas stocké comme ASCII texte nombres décimaux, pas optimal mais clairement améliorable avec un ByteBuffer et ainsi de suite. Mais comme c'est un précalcul, ça n'a pas tellement d'importance. , Vous pouvez trouver le fichier ici (ou produisez-le vous-même):

public final static boolean isPerfectSquareDurronThree(long n) {
    if(n < 0) return false;
    if(n == 0) return true;

    long x = n;
    while((x & 0x3) == 0) x >>= 2;
    if((x & 0x7) == 1) {
        if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;
        long sqrt;
        if(x < 410881L)
        {
            int i;
            float x2, y;

            x2 = x * 0.5F;
            y  = x;
            i  = Float.floatToRawIntBits(y);
            i  = 0x5f3759df - ( i >> 1 );
            y  = Float.intBitsToFloat(i);
            y  = y * ( 1.5F - ( x2 * y * y ) );

            sqrt = (long)(1.0F/y);
        } else {
            sqrt = (long) Math.sqrt(x);
        }
        return sqrt*sqrt == x;
    }
    return false;
}

je le charge dans un boolean tableau comme ceci:

private static boolean[] goodLookupSquares = null;

public static void initGoodLookupSquares() throws Exception {
    Scanner s = new Scanner(new File("24residues_squares.txt"));

    goodLookupSquares = new boolean[0x1FFFFFE];

    while(s.hasNextLine()) {
        int residue = Integer.valueOf(s.nextLine());
        goodLookupSquares[residue] = true;
        goodLookupSquares[residue + 0xFFFFFF] = true;
        goodLookupSquares[residue + 0x1FFFFFE] = true;
    }

    s.close();
}

exemple d'exécution. Il a battu Durron (version un) dans chaque procès que j'ai couru.

 0% Scenario{vm=java, trial=0, benchmark=Internet} 40665.77 ns; ?=566.71 ns @ 10 trials
33% Scenario{vm=java, trial=0, benchmark=Durron} 38397.60 ns; ?=784.30 ns @ 10 trials
67% Scenario{vm=java, trial=0, benchmark=DurronThree} 36171.46 ns; ?=693.02 ns @ 10 trials

  benchmark   us linear runtime
   Internet 40.7 ==============================
     Durron 38.4 ============================
DurronThree 36.2 ==========================

vm: java
trial: 0

il devrait être beaucoup plus rapide d'utiliser méthode de Newton pour calculer la racine carrée entière , puis carré ce nombre et de vérifier, comme vous le faites dans votre solution actuelle. La méthode de Newton est à la base de la solution de Carmack mentionnée dans d'autres réponses. Vous devriez être capable d'obtenir une réponse plus rapide puisque vous êtes seulement intéressé par la partie entière de la racine, vous permettant d'arrêter l'algorithme d'approximation plus tôt.

une autre optimisation que vous pouvez essayer: si le racine numérique d'un nombre ne se termine pas en 1, 4, 7, ou 9 le nombre est pas un carré parfait. Cela peut être utilisé comme un moyen rapide d'éliminer 60% de vos entrées avant d'appliquer l'algorithme de racine carrée plus lent.

je veux que cette fonction fonctionne avec tous les positif 64-bit signed entiers

Math.sqrt() fonctionne avec des doubles comme paramètres d'entrée, de sorte que vous ne serez pas obtenir des résultats précis pour les entiers plus grands que 2^53 .

pour mémoire, une autre approche consiste à utiliser la décomposition primaire. Si chaque facteur de décomposition est égal, alors le nombre est un carré parfait. Donc ce que vous voulez est de voir si un nombre peut être décomposé comme un produit de carrés de nombres premiers. Bien sûr, vous n'avez pas besoin d'obtenir une telle décomposition, juste pour voir si elle existe.

d'abord construire une table de carrés de nombres premiers qui sont inférieurs à 2^32. C'est beaucoup plus petit qu'un tableau de tous les les entiers jusqu'à cette limite.

une solution serait alors comme ceci:

boolean isPerfectSquare(long number)
{
    if (number < 0) return false;
    if (number < 2) return true;

    for (int i = 0; ; i++)
    {
        long square = squareTable[i];
        if (square > number) return false;
        while (number % square == 0)
        {
            number /= square;
        }
        if (number == 1) return true;
    }
}

c'est un peu mystérieux. Ce qu'il fait est de vérifier à chaque étape que le carré d'un nombre premier diviser le nombre d'entrée. S'il le fait, alors il divise le nombre par le carré aussi longtemps qu'il est possible, pour enlever ce carré de la décomposition première. Si par ce processus, nous sommes arrivés à 1, alors le nombre d'entrée était une décomposition du carré des nombres premiers. Si le carré devient plus grand que le nombre lui-même, alors il n'y a aucun moyen que ce carré, ou n'importe quels carrés plus grands, peuvent le diviser, de sorte que le nombre ne peut pas être une décomposition de carrés de nombres premiers.

compte tenu de nos jours sqrt fait dans le matériel et la nécessité de calculer des nombres premiers ici, je suppose que cette solution est beaucoup plus lente. Mais il devrait donner de meilleurs résultats que solution avec sqrt qui ne fonctionnera pas plus de 2^54, Comme dit mrzl dans sa réponse.

un problème entier mérite une solution entière. Ainsi

faire une recherche binaire sur les entiers (non-négatifs) pour trouver le plus grand entier T tel que t**2 <= n . Puis tester si r**2 = n exactement. Cela prend du temps O(log n).

si vous ne savez pas comment binaire rechercher les entiers positifs parce que l'ensemble est illimité, c'est facile. Vous commencez par calculer votre fonction croissante f (au-dessus de f(t) = t**2 - n ) sur des puissances de deux. Lorsque vous si ça devient positif, vous avez trouvé une limite supérieure. Alors vous pouvez faire la recherche binaire standard.

il a été souligné que les derniers d chiffres d'un carré parfait ne peut prendre sur certaines valeurs. Le dernier chiffre d (en base b ) d'un numéro n est le même que le reste lorsque n est divisé par b d , ie. au point C n % pow(b, d) .

cela peut être généralisé à n'importe quel module m , c.-à-d. n % m peut être utilisée pour exclure un certain pourcentage de nombres de carrés parfaits. Le module que vous utilisez actuellement est 64, ce qui permet 12, c'est à dire. 19% de restes, comme carrés possibles. Avec un peu de codage, j'ai trouvé le module 110880, qui ne permet que 2016, c'est à dire. 1,8% de restes comme carrés possibles. Ainsi, selon le coût d'une opération de module (c.-à-d. division) et une recherche de table par rapport à une racine carrée sur votre machine, en utilisant ce module pourrait être plus rapide.

par ailleurs si Java a un moyen de stocker un tableau emballé de bits de la table de recherche, ne l'utilisez pas. 110880 mots 32 bits n'est pas beaucoup de RAM ces jours-ci et aller chercher un mot machine va être plus rapide que aller chercher un seul bit.

pour l'exécution, il faut très souvent faire quelques compromis. D'autres ont exprimé diverses méthodes, cependant, vous avez noté que le hack de Carmack était plus rapide jusqu'à certaines valeurs de N. alors, vous devriez vérifier le "n" et s'il est inférieur à ce nombre N, utilisez le hack de Carmack, sinon utilisez une autre méthode décrite dans les réponses ici.

c'est L'implémentation Java la plus rapide que j'ai pu trouver, en utilisant une combinaison de techniques suggérées par d'autres dans ce thread.

• test Mod-256
• test Inexact mod-3465 (évite la division entière au prix de quelques faux positifs)
• racine carrée à virgule flottante, ronde et comparer avec la valeur d'entrée

j'ai également expérimenté ces modifications mais ils ont fait Non help performance:

• Additional mod-255 test
• divisant la valeur d'entrée par des puissances de 4
• racine carrée inversée rapide (pour fonctionner avec des valeurs élevées de N il faut 3 itérations, assez pour la rendre plus lente que la fonction racine carrée matérielle.)

public class SquareTester {

    public static boolean isPerfectSquare(long n) {
        if (n < 0) {
            return false;
        } else {
            switch ((byte) n) {
            case -128: case -127: case -124: case -119: case -112:
            case -111: case -103: case  -95: case  -92: case  -87:
            case  -79: case  -71: case  -64: case  -63: case  -60:
            case  -55: case  -47: case  -39: case  -31: case  -28:
            case  -23: case  -15: case   -7: case    0: case    1:
            case    4: case    9: case   16: case   17: case   25:
            case   33: case   36: case   41: case   49: case   57:
            case   64: case   65: case   68: case   73: case   81:
            case   89: case   97: case  100: case  105: case  113:
            case  121:
                long i = (n * INV3465) >>> 52;
                if (! good3465[(int) i]) {
                    return false;
                } else {
                    long r = round(Math.sqrt(n));
                    return r*r == n; 
                }
            default:
                return false;
            }
        }
    }

    private static int round(double x) {
        return (int) Double.doubleToRawLongBits(x + (double) (1L << 52));
    }

    /** 3465<sup>-1</sup> modulo 2<sup>64</sup> */
    private static final long INV3465 = 0x8ffed161732e78b9L;

    private static final boolean[] good3465 =
        new boolean[0x1000];

    static {
        for (int r = 0; r < 3465; ++ r) {
            int i = (int) ((r * r * INV3465) >>> 52);
            good3465[i] = good3465[i+1] = true;
        }
    }

}

la simplification suivante de la solution de maaartinus semble réduire de quelques points de pourcentage le temps d'exécution, mais je ne suis pas assez bon à l'étalonnage pour produire un benchmark je peux faire confiance:

long goodMask; // 0xC840C04048404040 computed below
{
    for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i);
}

public boolean isSquare(long x) {
    // This tests if the 6 least significant bits are right.
    // Moving the to be tested bit to the highest position saves us masking.
    if (goodMask << x >= 0) return false;
    // Remove an even number of trailing zeros, leaving at most one.
    x >>= (Long.numberOfTrailingZeros(x) & (-2);
    // Repeat the test on the 6 least significant remaining bits.
    if (goodMask << x >= 0 | x <= 0) return x == 0;
    // Do it in the classical way.
    // The correctness is not trivial as the conversion from long to double is lossy!
    final long tst = (long) Math.sqrt(x);
    return tst * tst == x;
}

Il serait intéressant de vérifier comment en omettant le premier test,

if (goodMask << x >= 0) return false;

affecterait la performance.

vous devez vous débarrasser de la partie 2-puissance de N dès le début.

2e Édition L'expression magique pour M ci-dessous devrait être

m = N - (N & (N-1));

et non pas comme il est écrit

fin de la 2e édition

m = N & (N-1); // the lawest bit of N
N /= m;
byte = N & 0x0F;
if ((m % 2) || (byte !=1 && byte !=9))
  return false;

1ère Édition:

amélioration mineure:

m = N & (N-1); // the lawest bit of N
N /= m;
if ((m % 2) || (N & 0x07 != 1))
  return false;

Fin de la 1ère édition

continue comme d'habitude. De cette façon, au moment où vous arrivez à la partie flottante, vous vous êtes déjà débarrassé de tous les numéros dont la partie 2-puissance est étrange (environ la moitié), et puis vous ne considérez que 1/8 de ce qui reste. I. e. vous exécutez la virgule flottante partie sur 6% des effectifs.

c'est une reprise de Décimal en binaire de L'ancien algorithme de calcul de Marchant (désolé, je n'ai pas de référence), en Ruby, adapté spécifiquement pour cette question:

def isexactsqrt(v)
    value = v.abs
    residue = value
    root = 0
    onebit = 1
    onebit <<= 8 while (onebit < residue)
    onebit >>= 2 while (onebit > residue)
    while (onebit > 0)
        x = root + onebit
        if (residue >= x) then
            residue -= x
            root = x + onebit
        end
        root >>= 1
        onebit >>= 2
    end
    return (residue == 0)
end

voici un calcul de quelque chose de similaire (s'il vous plaît ne me votez pas vers le bas pour le style de codage/odeurs ou clunky O/O - c'est l'algorithme qui compte, et C++ n'est pas ma langue maternelle). Dans ce cas, nous cherchons residue = = 0:

#include <iostream>  

using namespace std;  
typedef unsigned long long int llint;

class ISqrt {           // Integer Square Root
    llint value;        // Integer whose square root is required
    llint root;         // Result: floor(sqrt(value))
    llint residue;      // Result: value-root*root
    llint onebit, x;    // Working bit, working value

public:

    ISqrt(llint v = 2) {    // Constructor
        Root(v);            // Take the root 
    };

    llint Root(llint r) {   // Resets and calculates new square root
        value = r;          // Store input
        residue = value;    // Initialise for subtracting down
        root = 0;           // Clear root accumulator

        onebit = 1;                 // Calculate start value of counter
        onebit <<= (8*sizeof(llint)-2);         // Set up counter bit as greatest odd power of 2 
        while (onebit > residue) {onebit >>= 2; };  // Shift down until just < value

        while (onebit > 0) {
            x = root ^ onebit;          // Will check root+1bit (root bit corresponding to onebit is always zero)
            if (residue >= x) {         // Room to subtract?
                residue -= x;           // Yes - deduct from residue
                root = x + onebit;      // and step root
            };
            root >>= 1;
            onebit >>= 2;
        };
        return root;                    
    };
    llint Residue() {           // Returns residue from last calculation
        return residue;                 
    };
};

int main() {
    llint big, i, q, r, v, delta;
    big = 0; big = (big-1);         // Kludge for "big number"
    ISqrt b;                            // Make q sqrt generator
    for ( i = big; i > 0 ; i /= 7 ) {   // for several numbers
        q = b.Root(i);                  // Get the square root
        r = b.Residue();                // Get the residue
        v = q*q+r;                      // Recalc original value
        delta = v-i;                    // And diff, hopefully 0
        cout << i << ": " << q << " ++ " << r << " V: " << v << " Delta: " << delta << "\n";
    };
    return 0;
};

l'appel de la sqrt n'est pas parfaitement exact, comme cela a été mentionné, mais il est intéressant et instructif qu'il ne souffle pas les autres réponses en termes de vitesse. Après tout, la séquence des instructions de langage de montage pour un sqrt est minuscule. Intel a une instruction matérielle, qui N'est pas utilisée par Java je crois parce qu'elle n'est pas conforme à IEEE.

alors pourquoi est-ce lent? Parce que Java appelle en fait une routine C via JNI, et c'est en fait plus lent à le faire que d'appeler un sous-programme Java, qui lui-même est plus lent que de le faire en ligne. C'est très gênant, et Java aurait dû trouver une meilleure solution, c'est-à-dire construire des appels de bibliothèque en virgule flottante si nécessaire. Oh bien.

en C++, je soupçonne que toutes les alternatives complexes perdraient en vitesse, mais je ne les ai pas toutes vérifiées. Ce que J'ai fait, et ce que les gens de Java trouveront utile, est un simple hack, une extension du cas spécial de test suggéré par A. Rex. Utilisez un seul long valeur comme un tableau de bits, qui n'est pas limité vérifié. De cette façon, vous avez 64 bits de recherche booléenne.

typedef unsigned long long UVLONG
UVLONG pp1,pp2;

void init2() {
  for (int i = 0; i < 64; i++) {
    for (int j = 0; j < 64; j++)
      if (isPerfectSquare(i * 64 + j)) {
    pp1 |= (1 << j);
    pp2 |= (1 << i);
    break;
      }
   }
   cout << "pp1=" << pp1 << "," << pp2 << "\n";  
}


inline bool isPerfectSquare5(UVLONG x) {
  return pp1 & (1 << (x & 0x3F)) ? isPerfectSquare(x) : false;
}

la routine isPerfectSquare5 fonctionne dans environ 1/3 du temps sur ma machine Core2 duo. Je soupçonne que d'autres modifications dans le même sens pourraient réduire le temps encore plus en moyenne, mais à chaque fois que vous vérifiez, vous échangez plus de tests pour plus d'élimination, de sorte que vous ne pouvez pas aller trop loin sur cette route.

Certainement, plutôt que d'avoir un test séparé pour négatif, vous pouvez vérifier la haute 6 bits de la même façon.

notez que tout ce que je fais est d'éliminer les carrés possibles, mais quand j'ai un cas potentiel je dois appeler l'original, inlined isPerfectSquare.

la routine init2 est appelée une fois pour initialiser les valeurs statiques de pp1 et pp2. Notez que dans mon application en C++, je suis en utilisant unsigned long long, donc, puisque vous êtes connecté, vous devez utiliser la >>> opérateur.

il n'y a pas besoin intrinsèque de vérifier les limites du tableau, mais L'optimiseur de Java doit trouver ce truc assez rapidement, donc je ne les blâme pas pour cela.

le projet Euler est mentionné dans les étiquettes et bon nombre des problèmes qu'il pose nécessitent des numéros de contrôle >> 2^64. La plupart des optimisations mentionnées ci-dessus ne fonctionnent pas facilement lorsque vous travaillez avec un tampon de 80 octets.

j'ai utilisé java BigInteger et une version légèrement modifiée de la méthode de Newton, qui fonctionne mieux avec les entiers. Le problème était que les carrés exacts N^2 convergeaient vers (n-1) au lieu de n parce que n^2-1 = (n-1)(n+1) et que l'erreur finale n'était qu'une pas en dessous du diviseur final et l'algorithme terminé. Il était facile de corriger en ajoutant un à l'argument original Avant de calculer l'erreur. (Ajouter deux pour les racines cubiques, etc.)

un attribut agréable de cet algorithme est que vous pouvez dire immédiatement si le nombre est un carré parfait - l'erreur finale (Pas de correction) dans la méthode de Newton sera zéro. Une modification simple vous permet également de calculer rapidement le plancher(sqrt(x)) au lieu de l'entier le plus proche. Ce qui est pratique avec plusieurs problèmes Euler.

j'aime l'idée d'utiliser un près de méthode correcte sur certains de l'entrée. Voici une version avec un "offset"plus élevé. Le code semble fonctionner et passe mon test simple.

il suffit de remplacer votre:

if(n < 410881L){...}

code avec celui-ci:

if (n < 11043908100L) {
    //John Carmack hack, converted to Java.
    // See: http://www.codemaestro.com/reviews/9
    int i;
    float x2, y;

    x2 = n * 0.5F;
    y = n;
    i = Float.floatToRawIntBits(y);
    //using the magic number from 
    //http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
    //since it more accurate
    i = 0x5f375a86 - (i >> 1);
    y = Float.intBitsToFloat(i);
    y = y * (1.5F - (x2 * y * y));
    y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate

    sqrt = Math.round(1.0F / y);
} else {
    //Carmack hack gives incorrect answer for n >= 11043908100.
    sqrt = (long) Math.sqrt(n);
}

j'ai vérifié tous les résultats possibles lorsque les n derniers bits d'un carré est observée. En examinant successivement plus de bits, jusqu'à 5/6 entrées peuvent être éliminés. J'ai conçu ceci pour implémenter L'algorithme de factorisation de Fermat, et c'est très rapide là-bas.

public static boolean isSquare(final long val) {
   if ((val & 2) == 2 || (val & 7) == 5) {
     return false;
   }
   if ((val & 11) == 8 || (val & 31) == 20) {
     return false;
   }

   if ((val & 47) == 32 || (val & 127) == 80) {
     return false;
   }

   if ((val & 191) == 128 || (val & 511) == 320) {
     return false;
   }

   // if((val & a == b) || (val & c == d){
   //   return false;
   // }

   if (!modSq[(int) (val % modSq.length)]) {
        return false;
   }

   final long root = (long) Math.sqrt(val);
   return root * root == val;
}

le dernier bit de pseudocode peut être utilisé pour étendre les tests pour éliminer plus de valeurs. Les essais ci-dessus sont pour k = 0, 1, 2, 3

compte tenu de la longueur de bits générale (bien que j'ai utilisé le type spécifique ici), j'ai essayé de concevoir algo simpliste comme ci-dessous. Une vérification simple et évidente de 0,1,2 ou <0 est requise au départ. Ce qui suit est simple en ce sens qu'il n'essaie pas d'utiliser les fonctions mathématiques existantes. La plupart des opérateurs peuvent être remplacés par des opérateurs bit-wise. Je n'ai testé aucune donnée de référence. Je ne suis ni expert en mathématiques ou en conception d'algorithmes informatiques en particulier, j'aimerais vous voir soulignant problème. Je sais qu'il y a beaucoup de chances d'amélioration là-bas.

int main()
{
    unsigned int c1=0 ,c2 = 0;  
    unsigned int x = 0;  
    unsigned int p = 0;  
    int k1 = 0;  
    scanf("%d",&p);  
    if(p % 2 == 0) {  
        x = p/2; 
    }  
    else {  
        x = (p/2) +1;  
    }  
    while(x) 
    {
        if((x*x) > p) {  
            c1 = x;  
            x = x/2; 
        }else {  
            c2 = x;  
            break;  
        }  
    }  
    if((p%2) != 0)  
        c2++;

    while(c2 < c1) 
    {  
        if((c2 * c2 ) == p) {  
            k1 = 1;  
            break;  
        }  
        c2++; 
    }  
    if(k1)  
        printf("\n Perfect square for %d", c2);  
    else  
        printf("\n Not perfect but nearest to :%d :", c2);  
    return 0;  
}  

si la vitesse est un problème, pourquoi ne pas séparer l'ensemble le plus couramment utilisé d'entrées et leurs valeurs à une table de recherche et puis faire tout algorithme magique optimisé que vous avez mis au point pour les cas exceptionnels?

il devrait être possible d'emballer le 'ne peut pas être un carré parfait si les derniers x chiffres sont N' beaucoup plus efficace que cela! Je vais utiliser des ints java 32 bits, et produire assez de données pour vérifier les 16 derniers bits du nombre - c'est 2048 valeurs int hexadécimales.

...

Ok. Soit j'ai rencontré une théorie des nombres qui me dépasse un peu, soit il y a un bug dans mon code. En tout cas, voici le code:

public static void main(String[] args) {
    final int BITS = 16;

    BitSet foo = new BitSet();

    for(int i = 0; i< (1<<BITS); i++) {
        int sq = (i*i);
        sq = sq & ((1<<BITS)-1);
        foo.set(sq);
    }

    System.out.println("int[] mayBeASquare = {");

    for(int i = 0; i< 1<<(BITS-5); i++) {
        int kk = 0;
        for(int j = 0; j<32; j++) {
            if(foo.get((i << 5) | j)) {
                kk |= 1<<j;
            }
        }
        System.out.print("0x" + Integer.toHexString(kk) + ", ");
        if(i%8 == 7) System.out.println();
    }
    System.out.println("};");
}

et voici les résultats:

(ndlr: gommés pour de faibles performances dans l'embellir.js; voir l'historique des révisions pour voir.)

voici le moyen le plus simple et le plus concis, bien que je ne sais pas comment il se compare en termes de cycles CPU. Cela fonctionne très bien si vous ne souhaitez savoir si la racine est un nombre entier. Si vous vous souciez vraiment si c'est un entier, vous pouvez également trouver. Voici une fonction simple (et pure):

public static boolean isRootWhole(double number) {
    return Math.sqrt(number) % 1 == 0;
}

si vous n'avez pas besoin de micro-optimisation, cette réponse est meilleure en termes de simplicité et de maintenabilité. Si vous aurez des nombres négatifs, peut-être vous voulez utiliser les Mathématiques.abs() sur le nombre d'argument que les Mathématiques.argument sqrt ().

sur mon processeur Intel i7-4790 de 3,6 Ghz, une exécution de cet algorithme sur 0 - 10,000,000 a pris en moyenne 35 - 37 nanosecondes par calcul. J'ai fait 10 tirages séquentiels, imprimant le temps moyen passé sur chacun des 10 millions de calculs de la sqrt. Chaque course a pris un peu plus de 600 ms à compléter.

si vous effectuez un nombre moindre de calculs, les calculs antérieurs prennent un peu plus de temps.

si vous voulez la vitesse, étant donné que vos entiers sont de taille finie, je soupçonne que la manière la plus rapide impliquerait (a) partitionner les paramètres par taille (par exemple en catégories par le plus grand ensemble de bits), puis vérifier la valeur par rapport à un tableau de carrés parfaits dans cette gamme.

en ce qui concerne la méthode Carmac, il semble qu'il soit assez facile d'itérer une fois de plus, ce qui devrait doubler le nombre de chiffres de précision. C'est, après tout, une méthode itérative extrêmement tronquée -- celle de Newton, avec une très bonne première supposition.

en ce qui concerne votre meilleur, je vois deux micro-optimisations:

• déplacer le contrôle vs. 0 après le contrôle en utilisant mod255
• réorganiser les pouvoirs de division de quatre pour sauter tous les contrôles pour le cas habituel (75%).

i. e:

// Divide out powers of 4 using binary search

if((n & 0x3L) == 0) {
  n >>=2;

  if((n & 0xffffffffL) == 0)
    n >>= 32;
  if((n & 0xffffL) == 0)
      n >>= 16;
  if((n & 0xffL) == 0)
      n >>= 8;
  if((n & 0xfL) == 0)
      n >>= 4;
  if((n & 0x3L) == 0)
      n >>= 2;
}

encore mieux pourrait être un simple

while ((n & 0x03L) == 0) n >>= 2;

évidemment, il serait intéressant de savoir combien de numéros sont éliminés à chaque point de contrôle -- je doute que les contrôles soient vraiment indépendants, ce qui rend les choses difficiles.

" je suis à la recherche du moyen le plus rapide pour déterminer si une valeur longue est un carré parfait (i.e. sa racine carrée est un autre entier)."

les réponses sont impressionnantes, mais je n'ai pas vu un simple chèque:

vérifier si le premier nombre sur la droite du long il un membre de l'ensemble (0,1,4,5,6,9) . Si ce n'est pas le cas, alors il ne peut pas être un "carré parfait".

par exemple.

4567-ne peut pas être un carré parfait.

Je ne suis pas sûr que ce soit le moyen le plus rapide, mais c'est quelque chose que j'ai découvert (il y a longtemps au lycée) quand je m'ennuyais et que je jouais avec ma calculatrice pendant les cours de mathématiques. À l'époque, j'étais vraiment étonné de voir ce qui fonctionnait...

public static boolean isIntRoot(int number) {
    return isIntRootHelper(number, 1);
}

private static boolean isIntRootHelper(int number, int index) {
    if (number == index) {
        return true;
    }
    if (number < index) {
        return false;
    }
    else {
        return isIntRootHelper(number - 2 * index, index + 1);
    }
}

ne sait pas plus rapide, mais le plus simple est de prendre la racine carrée de la façon normale, multiplier le résultat par lui-même, et voir si elle correspond à votre valeur originale.

puisque nous parlons d'entiers ici, le jeûne impliquerait probablement une collection où vous pouvez juste faire une recherche.