Hace una serie de números enteros contienen al menos un cuadrado perfecto?

https://stackoverflow.com/questions/3140562

01-10-2019
|

Pregunta

Dados dos números enteros a y b, ¿hay una forma eficiente para probar si hay otro n entero tal que a ≤ n² < b?

No necesito saber n, solamente si existe al menos una de esas n o no, así que espero evitar el cálculo de raíces cuadradas de cualquier número en el intervalo.

Aunque si un individuo número entero es un cuadrado perfecto es más rápido que el cálculo de la raíz cuadrada , el rango puede ser grande y yo también preferiría evitar la realización de esta prueba para cada número dentro del rango.

Ejemplos:

intervalContainsSquare(2, 3) => false
intervalContainsSquare(5, 9) => false (nota: 9 está fuera de este intervalo)
intervalContainsSquare(9, 9) => false (este intervalo está vacío)
intervalContainsSquare(4, 9) => true (4 está dentro de este intervalo)
intervalContainsSquare(5, 16) => true (9 está dentro de este intervalo)
intervalContainsSquare(1, 10) => true (1, 4 y 9 son todos dentro de este intervalo)

Solución

Informática si un número es un cuadrado no es realmente más rápido que el cálculo de la raíz cuadrada en casos difíciles, por lo que yo sé. Lo que es cierto es que se puede hacer un precomputation saber que no es un cuadrado, que se podría ahorrar tiempo en promedio.

Asimismo para este problema, se puede hacer un precomputation para determinar que sqrt (b) -sqrt (a)> = 1, lo que significa, entonces, que a y b son lo suficientemente aparte de que debe ser un cuadrado entre ellos. Con un poco de álgebra, esta desigualdad es equivalente a la condición de que (ba-1) ^ 2> = 4 * a, o si lo desea en una forma más simétrica, que (ab) ^ 2 + 1> = 2 * (una + b). Por lo que este precomputation se puede hacer sin raíces cuadradas, sólo que con un producto entero y algunas adiciones y sustracciones.

Si a y b son casi exactamente el mismo, a continuación, puede seguir utilizando el truco de mirar bajo orden dígitos binarios como un precomputation saber que no es un cuadrado entre ellos. Pero tienen que ser tan juntos que este precomputation podría no valer la pena.

Si estas precomputations no son concluyentes, entonces no puedo pensar en otra que todos los demás de solución de nada, un <= ceil (sqrt (a)) ^ 2

Dado que no era una cuestión de hacer la derecha álgebra:

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

También: Generalmente cuando a es un número grande, se calcularía sqrt (a) con el método de Newton, o con una tabla de búsqueda seguido de las etapas del método de Newton unos pocos. Es más rápido, en principio, a ceil de cómputo (sqrt (a)) que sqrt (a), debido a que la aritmética de punto flotante puede simplificarse a la aritmética de enteros, y debido a que no es necesario que las etapas del método de muchos Newton para clavar de alta precisión que se sólo vamos a tirar a la basura. Pero en la práctica, una función de biblioteca numérica puede ser mucho más rápido si se utiliza raíces cuadradas implementadas en microcódigo. Si por cualquier razón usted no tiene que microcódigo para ayudarle, a continuación, podría valer la pena para la mano de código ceil (sqrt (a)). Tal vez el caso más interesante sería si a y b son números enteros sin límites (como, mil dígitos). Pero para los enteros ordinarios de tamaño en un equipo que no sea obsoleta ordinaria, no se puede vencer a la FPU.

Otros consejos

Obtiene la raíz cuadrada del número más bajo. Si esto es un entero, entonces ya está. De lo contrario hasta redonda y cuadrada del número. Si este es menor que b, entonces es cierto.

Sólo es necesario calcular una raíz cuadrada de esta manera.

Con el fin de evitar un problema de cuando a es igual a b, debe comprobar que la primera. Como este caso siempre es falsa.

Si va a aceptar el cálculo de dos raíces cuadradas, debido a su monotonía que tiene esta desigualdad que es equivalente a la de iniciar uno:

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

Así, si floor(sqrt(a)) != floor(sqrt(b)), floor(sqrt(b)) - 1 se garantiza que sea una n tales.

obtener la raíz cuadrada del número más bajo y alrededor de ella hasta
obtener la raíz cuadrada del número más alto y se redondea hacia abajo
si 1 es menor o igual 2, habrá un cuadrado perfecto

Para la parte integral de sqrt (a) y sqrt (b), por ejemplo SA y SB.

Si sa ² = a, entonces sí de salida.

Si sb ² = b y sa = sb-1, entonces la salida no.

Si sa

salida de lo contrario no.

Se puede optimizar la anterior para deshacerse del cálculo de la raíz cuadrada (b) (similar a la respuesta de JDunkerly).

O es que quiere evitar el cálculo de raíces cuadradas de A y B también?

Se puede evitar el cálculo de raíces cuadradas por completo mediante el uso de un método similar a la búsqueda binaria.

Se empieza con una conjetura para n, n = 1 y calcular n ²

Tenga en cuenta si a <= n

Si n

Esto será O (logb) tiempo.

Además de solución agradable de JDunkerley (1), no podría ser una posible mejora que tiene que ser probado y usos número entero raíces cuadradas para calcular raíces cuadradas número entero

¿Por qué la esperanza de evitar por completo las raíces cuadradas? Incluso antes de llegar a la forma más eficiente de resolver esto, se ha visto que los métodos de llamadas por sólo 2 raíces cuadradas. Eso se hace en O (1) tiempo, así que me parece que cualquier mejora que se podría esperar para hacer tomaría más tiempo para pensar acerca de lo que podríamos llegar a ahorrar tiempo de cálculo. ¿Me equivoco?

Una forma es utilizar el método de Newton para encontrar el número entero raíz cuadrada de b. A continuación, se puede comprobar si ese número cae en el rango. Dudo que es más rápido que simplemente llamando a la función de raíz cuadrada, pero sin duda es más interesante:

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;
}

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow