Square Root (Integer)

Q: ¿Cuál es la complejidad temporal de la búsqueda binaria de la raíz cuadrada?

Tiempo O(log x) y espacio O(1) . En cada paso se reduce a la mitad el rango de candidatos, así que x = 2^31 - 1 necesita 31 pasos. Contar hacia arriba desde 0 requiere O(√x) pasos, 46340 para el mismo x , lo cual está bien aquí, pero crece rápidamente con entradas de 64 bits.

Q: ¿Cómo calcula el método de Newton una raíz cuadrada entera?

Empieza con r = x . Mientras r × r > x , reemplaza r por (r + x / r) / 2 usando división entera. Cada paso hace que r se acerque a la raíz desde arriba sin sobrepasarla, y el bucle se detiene en la parte entera de la raíz cuadrada. Para x = 2^31 - 1 necesita 19 pasos, y la cantidad de dígitos correctos aproximadamente se duplica en cada paso una vez que se acerca.

FácilBúsqueda binaria Matemáticas y simulación

+10

Tu función recibe un entero no negativo x y devuelve su raíz cuadrada entera: el mayor entero r tal que r × r ≤ x. Es decir, la raíz cuadrada redondeada hacia abajo, así que un número que no sea un cuadrado perfecto obtiene la raíz del cuadrado perfecto inmediatamente inferior. Calcúlala tú mismo, sin usar una función integrada de raíz cuadrada ni de potencia.

Función

mySqrt(x: integer) → integer

xinteger: el entero no negativo del que se debe calcular la raíz cuadrada
Devuelveinteger: la raíz cuadrada de x redondeada hacia abajo al entero más cercano

Restricciones

0 ≤ x ≤ 2³¹ - 1
No llames a una función integrada de raíz cuadrada, potencia o exponente.

Ejemplos

Entrada: x = 17
Salida: 4
Explicación: 4 × 4 = 16 es como máximo 17, pero 5 × 5 = 25 es mayor, así que la raíz de 17 se redondea hacia abajo a 4.

Entrada: x = 49
Salida: 7
Explicación: 49 es un cuadrado perfecto, 7 × 7 = 49, así que no se redondea nada y la respuesta es exactamente 7.

+17 pruebas ocultas al enviar

Para ir más allá

¿Cómo encontrarías la raíz cúbica entera en su lugar, el mayor r tal que r × r × r ≤ x, si x también pudiera ser negativo?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Contar hacia arriba desde 0 hasta que el siguiente cuadrado supere x da la respuesta correcta, pero requiere un paso por cada unidad de la raíz: unos 46000 pasos cerca del límite superior del rango. Los cuadrados 0, 1, 4, 9, 16 y así sucesivamente están ordenados, así que puedes hacer una búsqueda binaria para encontrar el último candidato cuyo cuadrado sea como máximo x y terminar en unos 31 pasos. El problema en ambos casos es el desbordamiento: el cuadrado de un candidato no siempre cabe en 32 bits.

Cuenta desde cero hacia arriba

Intuición

La raíz es el mayor r que cumple r × r ≤ x. Empieza en r = 0, cuyo cuadrado siempre cabe, y sigue avanzando a r + 1 mientras el cuadrado del siguiente número todavía quepa. El bucle se detiene en el primer r cuyo sucesor es demasiado grande, que es exactamente la raíz. Para x = 17, los cuadrados 1, 4, 9 y 16 caben, pero 25 no, así que el bucle se detiene en 4.

El bucle se ejecuta una vez por cada unidad del resultado. El resultado más grande aquí es 46340, así que son como máximo 46340 pasos, lo cual termina rápido. Sin embargo, el costo es O(√x), y crece con la entrada: un x de 64 bits podría requerir alrededor de 3 × 10^9 pasos.

Presta atención a la última comprobación. Para x = 2^31 - 1, el bucle eleva 46341 al cuadrado para averiguar que es demasiado grande, y 46341 × 46341 = 2147488281 no cabe en un entero de 32 bits. Calcula el cuadrado usando 64 bits.

Algoritmo

Establece root = 0.
Mientras (root + 1) × (root + 1) ≤ x, incrementa root en 1.
Devuelve root.

def mySqrt(x):
    root = 0
    while (root + 1) * (root + 1) <= x:
        root += 1
    return root

Búsqueda binaria sobre la respuesta

Intuición

Ordena los candidatos del 0 al 1, 2, hasta x, y hazle a cada uno la misma pregunta: ¿su cuadrado es como máximo x? Las respuestas son sí, sí, sí y después no para todos los candidatos posteriores a la raíz, porque los cuadrados solo crecen. La raíz es el último sí. La búsqueda binaria está diseñada para una secuencia ordenada de síes seguida de noes.

Mantén el intervalo lo a hi de candidatos aún no decididos, empezando de 0 a x, y una variable best para el mayor sí hasta el momento. Prueba el punto medio mid. Si mid × mid ≤ x, la raíz es mid o mayor: guárdalo en best y mueve lo a mid + 1. De lo contrario, la raíz es menor: mueve hi a mid - 1. Cuando el intervalo esté vacío, best será la raíz.

Traza x = 17. El intervalo de 0 a 17 prueba 8 (64, demasiado grande), después de 0 a 7 prueba 3 (9, cabe, best = 3), después de 4 a 7 prueba 5 (25, demasiado grande), después de 4 a 4 prueba 4 (16, cabe, best = 4). El intervalo está vacío y la respuesta es 4. Cada paso reduce el intervalo a la mitad, así que x = 2^31 - 1 requiere 31 pasos. Haz los cuadrados en 64 bits: el primer mid allí es 1073741823.

Algoritmo

Establece lo = 0, hi = x y best = 0.
Mientras lo ≤ hi, calcula mid, el punto medio del rango.
Si mid × mid ≤ x (en 64 bits), establece best = mid y lo = mid + 1.
De lo contrario, establece hi = mid - 1.
Devuelve best.

def mySqrt(x):
    lo, hi = 0, x
    best = 0  # largest candidate seen so far whose square fits
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            best = mid  # mid fits, so try a larger root
            lo = mid + 1
        else:
            hi = mid - 1  # mid is too big
    return best

Errores comunes y casos límite

La búsqueda en sí es breve; los errores se esconden en la aritmética y en los casos límite.

Elevar al cuadrado en 32 bits. Para x = 2147483647, el primer candidato intermedio es 1073741823, y su cuadrado es aproximadamente 1.15 × 10^18. En un int de 32 bits, el resultado se desborda y da un valor incorrecto, que incluso puede parecer lo bastante pequeño como para caber. Haz la multiplicación en 64 bits o compara m ≤ x / m.
Elevar al cuadrado el siguiente candidato en 32 bits en el bucle de conteo. La raíz de 2^31 - 1 es 46340, y la última comprobación del bucle eleva 46341 al cuadrado, lo que da 2147488281, por encima del límite de 32 bits.
Superar el límite de 32 bits con el rango. Un límite exclusivo hi = x + 1 es 2147483648 para el valor máximo de x, uno por encima del límite de 32 bits. Con el límite inclusivo hi = x, lo + hi alcanza exactamente 2147483647 en el primer paso, así que cabe justo. Usa índices de 64 bits o lo + (hi - lo) / 2.
Devolver el último mid que examinaste en lugar del último que encajaba. Para x = 17, la búsqueda termina después de probar 5, que es demasiado grande; la respuesta es el 4 que se había guardado.
Romper los casos pequeños. Una búsqueda que empieza en lo = 1 no encuentra x = 0, y la comprobación de división m ≤ x / m divide por cero cuando m = 0. Comprueba 0 y 1 por separado.

Preguntas frecuentes4

¿Cómo se calcula una raíz cuadrada sin una función integrada?

Para calcular la raíz cuadrada entera, busca la respuesta mediante búsqueda binaria. Los candidatos de 0 a x se dividen en una secuencia cuyos cuadrados son menores o iguales que x y otra cuyos cuadrados son mayores, y la búsqueda binaria encuentra el último candidato de la primera secuencia. El método de Newton es la otra respuesta habitual: refina una estimación r con (r + x / r) / 2 hasta que el cuadrado encaje.

¿Cuál es la complejidad temporal de la búsqueda binaria de la raíz cuadrada?

Tiempo O(log x) y espacio O(1). En cada paso se reduce a la mitad el rango de candidatos, así que x = 2^31 - 1 necesita 31 pasos. Contar hacia arriba desde 0 requiere O(√x) pasos, 46340 para el mismo x, lo cual está bien aquí, pero crece rápidamente con entradas de 64 bits.

¿Cómo calcula el método de Newton una raíz cuadrada entera?

Empieza con r = x. Mientras r × r > x, reemplaza r por (r + x / r) / 2 usando división entera. Cada paso hace que r se acerque a la raíz desde arriba sin sobrepasarla, y el bucle se detiene en la parte entera de la raíz cuadrada. Para x = 2^31 - 1 necesita 19 pasos, y la cantidad de dígitos correctos aproximadamente se duplica en cada paso una vez que se acerca.

¿Por qué la solución necesita enteros de 64 bits cuando la respuesta cabe en 32 bits?

La respuesta es como máximo 46340, pero los candidatos que pruebas no lo son. La búsqueda binaria entre 0 y x primero prueba un candidato cercano a 10^9, y su cuadrado es cercano a 10^18, muy por encima del límite de 32 bits, de aproximadamente 2.1 × 10^9. Elevar al cuadrado usando 64 bits mantiene la comparación exacta. Comparar m ≤ x / m evita por completo el producto grande.

Python

def mySqrt(x):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Entrada

x = 17

Esperado