Est-ce une gamme d'entiers contiennent au moins un carré parfait?

Question

Etant donnés deux entiers a et b, est-il un moyen efficace pour vérifier s'il y a un autre n entier tel que a ≤ n2 < b?

Je ne ai pas besoin de savoir n, seulement si au moins un tel n existe ou non, je l'espère éviter calcul des racines carrées de tous les nombres dans l'intervalle.

Bien que si une personne entier est un carré parfait est plus rapide que le calcul du racine carrée, la plage peut être grande et je préférerais aussi éviter d'effectuer ce test pour chaque numéro dans la plage.

Exemples:

• intervalContainsSquare(2, 3) => false
• intervalContainsSquare(5, 9) => false (note: 9 est en dehors de cet intervalle)
• intervalContainsSquare(9, 9) => false (cet intervalle est vide)
• intervalContainsSquare(4, 9) => true (figure 4 est à l'intérieur de cet intervalle)
• intervalContainsSquare(5, 16) => true (9 est à l'intérieur de cet intervalle)
• intervalContainsSquare(1, 10) => true (1, 4 et 9 sont tous à l'intérieur de cet intervalle)

Answer 1

Computing si un nombre est un carré est pas vraiment plus rapide que de calculer sa racine carrée dans les cas difficiles, pour autant que je sache. Ce qui est vrai est que vous pouvez faire un précalcul de savoir que ce n'est pas un carré, ce qui pourrait vous faire gagner du temps en moyenne.

De même pour ce problème, vous pouvez faire un pré-calcul pour déterminer que sqrt (b) -sqrt (a)> = 1, alors des moyens que a et b sont suffisamment éloignés qu'il doit y avoir une place entre eux. Avec un peu de l'algèbre, cette inégalité est équivalente à la condition que (ba-1) ^ 2> = 4 * a, ou si vous le souhaitez sous une forme plus symétrique, que (ab) ^ 2 + 1> = 2 * (a + b). Donc, ce précalcul peut être fait sans racines carrées, avec un seul produit entier et quelques additions et soustractions.

Si a et b sont presque exactement les mêmes, alors vous pouvez toujours utiliser l'astuce de regarder bas chiffres binaires de commande comme un précalcul de savoir qu'il n'y a pas un carré entre eux. Mais ils doivent être si proches que ce précalcul pourrait ne pas valoir la peine.

Si ces précalculs ne sont pas concluants, alors je ne peux pas penser à autre chose que la solution de tout le monde, un <= ceil (sqrt (a)) ^ 2

---

Comme il y avait une question de faire le droit d'algèbre:

sqrt(b)-sqrt(a) >= 1
sqrt(b) >= 1+sqrt(a)
b >= 1+2*sqrt(a)+a
b-a-1 >= 2*sqrt(a)
(b-a-1)^2 >= 4*a

---

Aussi: En général, lorsqu'un est un grand nombre, vous calculerait sqrt (a) avec la méthode de Newton, ou avec une table de consultation suivie par quelques étapes de la méthode de Newton. Il est plus rapide en principe Ceil de calcul (sqrt (a)) que sqrt (a), parce que l'arithmétique en virgule flottante peut être simplifiée à l'arithmétique entière, et parce que vous n'avez pas besoin d'autant les étapes de la méthode de Newton à clouer haute précision vous allez juste jeter. Mais dans la pratique, une fonction de bibliothèque numérique peut être beaucoup plus rapide si elle utilise des racines carrées mises en œuvre dans microcode. Si pour une raison quelconque, vous n'avez pas ce microcode pour vous aider, il pourrait être utile au code à la main Ceil (sqrt (a)). Peut-être le cas le plus intéressant serait si a et b sont des nombres entiers (comme, non bornées mille chiffres). Mais pour les entiers de taille ordinaires sur un ordinateur non obsolète ordinaire, vous ne pouvez pas battre le FPU.

Answer 2

Obtenir la racine carrée du nombre inférieur. Si cela est un entier, vous avez terminé. Dans le cas contraire et carré le nombre rond. Si elle est inférieure à b alors il est vrai.

Il vous suffit de calculer une racine carrée de cette façon.

Afin d'éviter un problème quand un est égal à b, vous devez vérifier que la première. Comme ce cas est toujours faux.

Answer 3

Si vous accepterez calculer deux racines carrées, en raison de son monotonicity vous avez cette inégalité qui équivaut à un démarrage de votre:

sqrt(a) <= n < sqrt(b)

ainsi, si floor(sqrt(a)) != floor(sqrt(b)), floor(sqrt(b)) - 1 est garanti d'être un tel n.

Answer 4

1. obtenir la racine carrée du nombre inférieur et arrondir
2. obtenir la racine carrée du nombre plus élevé et le tour vers le bas
3. si 1 est inférieure ou égale 2, il y aura un carré parfait

Answer 5

Trouver la partie intégrante de sqrt (a) et sqrt (b), par exemple SA et SB.

Si sa ² = a, alors oui sortie.

Si sb ² = b et sa = sb-1, puis la sortie no.

Si sa

Sinon la sortie no.

Vous pouvez optimiser ci-dessus pour se débarrasser du calcul de sqrt (b) (similaire à la réponse de JDunkerly).

Ou avez-vous voulez éviter de calcul des racines carrées a et b aussi?

---

Vous pouvez éviter calculer des racines carrées complètement en utilisant une méthode similaire à la recherche binaire.

Vous commencez avec une estimation pour n, n = 1 et n Compute ²

Considérez si <= n

Si n

Ce sera O (logb) temps.

Answer 6

En plus de la solution agréable de JDunkerley (+1), il pourrait y avoir une amélioration possible que les besoins à tester et utilisations entier racines carrées pour calculer les racines carrées entier

Answer 7

Pourquoi Espérez-vous pour éviter les racines carrées entièrement? Même avant d'arriver à la façon la plus efficace de résoudre, vous avez vu des méthodes qui appel à seulement deux racines carrées. Cela se fait en O (1) le temps, il me semble que toute amélioration que vous pourriez espérer faire prendrait plus de temps pour penser à que cela ne jamais vous faire économiser du temps de calcul. Ai-je tort?

Answer 8

La première consiste à utiliser la méthode de Newton pour trouver le racine carrée pour b. Ensuite, vous pouvez vérifier si ce nombre tombe dans la gamme. Je doute qu'il est plus rapide que d'appeler simplement la fonction de la racine carrée, mais il est certainement plus intéressant:

int main( int argc, char* argv[] )
{
    int a, b;
    double xk=0, xk1;
    int root;
    int iter=0;
    a = atoi( argv[1] );
    b = atoi( argv[2] );

    xk1 = b / 32 + 1;  // +1 to ensure > 0
    xk1 = b;
    while( fabs( xk1 - xk ) >= .5 ) {
        xk = xk1;
        xk1 = ( xk + b / xk ) / 2.;
        printf( "%d) xk = %f\n", ++iter, xk1 );
    }

    root = (int)xk1;

    // If b is a perfect square, then this finds that root, so it also
    // needs to check if (n-1)^2 falls in the range.
    // And this does a lot more multiplications than it needs
    if ( root*root >= a && root*root < b ||
         (root-1)*(root-1) >= a && (root-1)*(root-1) < b )
        printf( "Contains perfect square\n" );
    else
        printf( "Does not contain perfect square\n" );

    return 1;
}