algorithm - perfectos - que es un cubo perfecto

¿Un rango de enteros contiene al menos un cuadrado perfecto?

Question

Dados dos enteros a y b , ¿hay una manera eficiente de probar si hay otro entero n tal que a ≤ n 2 < b ?

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

Aunque probar si un entero individual es un cuadrado perfecto es más rápido que calcular la raíz cuadrada , el rango puede ser grande y también preferiría evitar realizar 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) => falso (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 están todos dentro de este intervalo)

Answer 1

1. obtener la raíz cuadrada del número inferior y redondearla
2. obtener la raíz cuadrada del número más alto y redondear hacia abajo
3. si 1 es inferior o igual a 2, habrá un cuadrado perfecto

Answer 2

¿Por qué esperas evitar por completo las raíces cuadradas? Incluso antes de llegar a la forma más eficiente de resolver esto, ha visto métodos que solo requieren 2 raíces cuadradas. Esto se hace en O (1) tiempo, por lo que me parece que cualquier mejora que pueda esperar le tomaría más tiempo de lo que NUNCA le ahorraría tiempo de computación. ¿Me equivoco?

Answer 3

Además de la buena solución de JDunkerley (+1), podría haber una posible mejora que necesita ser probada y usa raíces cuadradas enteras para calcular raíces cuadradas enteras

Answer 4

Calcular hasta qué punto un número es cuadrado no es realmente más rápido que calcular su raíz cuadrada en casos difíciles, que yo sepa. Lo que es cierto es que puede hacer una precomputación para saber que no es un cuadrado, lo que podría ahorrarle tiempo en promedio.

Del mismo modo, para este problema, puede hacer una precomputación para determinar que sqrt (b) -sqrt (a)> = 1, lo que significa que a y b están lo suficientemente separados como para que haya un cuadrado entre ellos. Con algún álgebra, esta desigualdad es equivalente a la condición de que (ba-1) ^ 2> = 4 * a, o si lo quieres en una forma más simétrica, que (ab) ^ 2 + 1> = 2 * (a + b). Entonces, esta precomputación se puede hacer sin raíces cuadradas, solo con un producto entero y algunas sumas y restas.

Si a y b son casi exactamente iguales, entonces puedes seguir el truco de ver los dígitos binarios de orden bajo como precomputación para saber que no hay un cuadrado entre ellos. Pero tienen que estar tan cerca que esta precomputación no valga la pena.

Si estas precomputaciones no son concluyentes, entonces no puedo pensar en otra cosa que no sea la solución de todos los demás, a <= ceil (sqrt (a)) ^ 2 <b.

Ya que había una cuestión de hacer el derecho de á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: en general, cuando a es un número grande, debería calcular sqrt (a) con el método de Newton, o con una tabla de búsqueda seguida de algunos pasos del método de Newton. En principio, es más rápido calcular ceil (sqrt (a)) que sqrt (a), porque la aritmética de punto flotante se puede simplificar a la aritmética de enteros, y porque no necesita tantos pasos del método de Newton para concretar una precisión alta que Sólo vas a tirar. Pero en la práctica, una función de biblioteca numérica puede ser mucho más rápida si utiliza raíces cuadradas implementadas en microcódigo. Si por alguna razón no tiene ese microcódigo para ayudarlo, entonces valdría la pena codificarlo manualmente (sqrt (a)). Tal vez el caso más interesante sería si a y b son enteros ilimitados (como, mil dígitos). Pero para enteros de tamaño ordinario en una computadora ordinaria no obsoleta, no puede vencer a la FPU.

Answer 5

Encuentre la parte integral de sqrt (a) y sqrt (b), digamos sa y sb.

Si sa ² = a, entonces sale sí.

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

Si sa <sb salida sí.

Otra salida no.

Puede optimizar lo anterior para deshacerse del cálculo de sqrt (b) (similar a la respuesta de JDunkerly).

¿O querías evitar calcular las raíces cuadradas de a y b también?

Puede evitar el cálculo completo de las raíces cuadradas utilizando un método similar a la búsqueda binaria.

Comienzas con una conjetura para n, n = 1 y calcula n ²

Considera si a <= n <b, puedes parar.

Si n <a <b, doblas tu conjetura n. si a <b <n, lo hace cercano al promedio de la estimación actual + anterior.

Este será el tiempo O (logb).

Answer 6

Obtener la raíz cuadrada del número inferior. Si este es un número entero, entonces ya está hecho. De lo contrario redondear y cuadrar el número. Si esto es menor que b entonces es verdad.

Solo necesitas calcular una raíz cuadrada de esta manera.

Para evitar un problema de cuando a es igual a b, primero debe verificarlo. Como este caso siempre es falso.

Answer 7

Si acepta el cálculo de dos raíces cuadradas, debido a su monotonicidad, tiene esta desigualdad que es equivalente a su inicial:

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

por lo tanto, si floor(sqrt(a)) != floor(sqrt(b)) , floor(sqrt(b)) - 1 está garantizado como tal n .

Answer 8

Una forma es usar el método de Newton para encontrar la raíz cuadrada entera para b . Luego puedes verificar si ese número cae dentro del rango. Dudo que sea más rápido que simplemente llamar a la función de raíz cuadrada, pero ciertamente 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;
}