Detección de cuadrados perfectos más rápida que la extracción de la raíz cuadrada

Question

Dado el radix- $r$ representación de un número entero $n$ y una constante entera pequeña $k$ Hay un $O(\log n)$ algoritmo para detectar si $n$ es un múltiplo de $k$ , es decir, la división, que produce como subproducto el cociente $\lfloor n/k\rfloor$ . En general, esto es lo mejor que se puede hacer. Pero para ciertas opciones de $r$ y $k$ por ejemplo $r=10$ y $k=2$ existe un algoritmo que responde a la pregunta mucho más rápido (tiempo constante) sin produciendo el cociente.

Dado el radix- $r$ representación de un número entero $n$ podemos extraer la raíz cuadrada entera $\lfloor\sqrt n\rfloor$ en algo así como $O(\log^3 n)$ tiempo haciendo una búsqueda binaria, que según Joriki se puede mejorar para $O(\log^2 n)$ con una implementación suficientemente inteligente. Esto da una $O(\log^2 n)$ algoritmo para determinar si $n$ es un cuadrado perfecto.

¿Existe un algoritmo significativamente más rápido que decida correctamente si $n$ es cuadrado perfecto, sin producir también la raíz cuadrada? Sospecho que no, pero me interesaría ver una prueba.

Answer 1

Véase el artículo de Bernstein, Lenstra y Pila: Detecting Perfect Powers by Factoring into Coprimes, Mathematics of Computation, Volume 76, #257, January 2007, pp. 385-388. O aquí.

Del resumen: Este trabajo presenta un algoritmo que, dado un número entero n>1, encuentra el mayor k tal que n es una potencia k.

El algoritmo se ejecuta en el tiempo $\log(n)(\log\log(n))^{O(1)}$ .

Answer 2

Aquí se presenta una prueba probabilística de cuadratura que puede lograr un error arbitrariamente pequeño con una complejidad de tiempo muy cercana a $\mathcal{O}$ (log $n$ ) base $r$ . Es una especie de generalización de la enfoque utilizado en la biblioteca GMP .

Premisa 1 : Si un número entero $n$ es un cuadrado perfecto y $P$ es un primo impar < N, entonces $n$ (mod $P$ ) es un residuo cuadrático módulo $P$ .

Contrapositivo : Si $n$ (mod $P$ ) es un no-residuo cuadrático módulo $P$ entonces $n$ no es un cuadrado perfecto.

Premisa 2 : Dado un módulo primo impar $P$ Hay $\frac{(P+1)}{2}$ residuos cuadráticos (incluido el 0) y $\frac{(P-1)}{2}$ cuadráticos no residuales. Así que hay un 50% de probabilidad de que un entero aleatorio $n$ es un residuo cuadrático (mod $P$ ).

Podemos deducir lo siguiente. Dado un número entero $n$ :

• Si $n$ es un cuadrado perfecto, entonces pasará El criterio de Euler para el 100% de los primos Impares coprimos a $n$ (véase la nota [1]).
• Si $n$ es no un cuadrado perfecto, entonces fallará el criterio de Euler para aproximadamente el 50% de los primos Impares.

Así que podemos construir una prueba probabilística robusta del mismo estilo que la Prueba de primalidad de Fermat . Elegimos un primo $P_{0}$ y comprobar el criterio de Euler para $n$ (mod $P_{0}$ ).

• Si $n$ es un cuadrático no -residuo (mod $P_{0}$ ), entonces tenemos nuestra respuesta definitiva, es decir $n$ no es un cuadrado perfecto.
• Por otro lado, si $n$ es un residuo cuadrático (mod $P_{0}$ ), entonces $n$ puede ser o no un cuadrado perfecto. Pero elegimos más primos $P_{i}$ y realizar la prueba repetidamente.

Cada vez $n$ pasa como un residuo cuadrático, la probabilidad de intersección de $n$ que no es cuadrado disminuye en un 50%, de modo que sólo se necesitan 10 pruebas para determinar que $n$ es un cuadrado perfecto con una probabilidad >99,9%[2], independientemente de su tamaño. En otras palabras, si $n$ no es un cuadrado perfecto, entonces al menos una de las pruebas habrá fallado antes de ese punto (con una probabilidad >99,9%).

La clave aquí es que los no-cuadrados siempre fallan el criterio en una tasa de ~50% (probado contra varios primos). Así que si después de una docena de pruebas de este tipo $n$ no ha fallado el criterio ni una sola vez, hay una probabilidad muy alta de que sea un cuadrado perfecto. Me doy cuenta de que me falta mucho la terminología bayesiana adecuada aquí, pero esto funciona y puedes probarlo. La probabilidad de error puede hacerse arbitrariamente pequeña probando con más números primos.

Complejidad del tiempo : Dado que la elección de los primos $P_{i}$ no necesita depender de $n$ La determinación de los exponentes para las pruebas requiere $\mathcal{O}(1)$ Yo creo que sí. Y como el nivel de confianza deseado también es independiente de $n$ la complejidad temporal global parece equivalente a la de la exponenciación modular. Utilizando el método de exponenciación al cuadrado con un algoritmo de multiplicación eficiente como k-way Toom-Cook o Schonhage-Strassen da una complejidad temporal global muy cercana a $\mathcal{O}$ (log $n$ ) base $r$ dependiendo de los parámetros elegidos. Consulte los artículos de Wikipedia enlazados para obtener más detalles.

[1]: El criterio de Euler requiere que $n$ y $P$ son coprimos; si no lo son, entonces $n^{\frac{P-1}{2}}\equiv 0$ (mod $P$ ), y el resultado de la prueba se descarta.

[2]: Una tasa de error del 0,1% en mil millones de enteros (de cualquier magnitud) representa alrededor de 1 millón de falsos positivos, lo que es realmente malo. En teoría, deberían utilizarse 30 números primos para obtener menos de un falso positivo por cada mil millones de enteros probados, pero en la práctica he comprobado que basta con los primeros 18-20 números primos para no obtener ninguno.

---

Actualización: Aquí hay una implementación que funciona en C con libgmp:

https://gist.github.com/jrodatus/e66d6f6b2f014f6b69543019edd23982

Ejemplo de ejecución 1 - Estadísticas de residuos:

Test Mode

  0. Statistics for N > P being a quadratic residue mod P
  1. Probable perfect square algorithm

Enter test [0|1] 0
Number of primes: 30  
Number of tests (T): 1000000
Upper bound for N: 100000000000000000

Generating 30 primes...
Done: P_max=127

================================================================================
We will test T=1000000 random integers N, where:

    P_max = 127 < N <= 100000000000000000

Each row P shows the number of these N's that were quadratic residues (mod P),
written as a fraction of T.

If ~50% of randomly-chosen N's were residues (mod P),
that suggests a probability of 50% that a given N > P will be a residue.

Consistent with the Law of Large Numbers,
a large T (e.g. >1000) is needed to converge to this result.
================================================================================
  P   fraction of N's that were residues
----------------------------------------
  3   0.332975000 (332975/1000000)
  5   0.400004000 (400004/1000000)
  7   0.429508000 (429508/1000000)
 11   0.455161000 (455161/1000000)
 13   0.461268000 (461268/1000000)
 17   0.469941000 (469941/1000000)
 19   0.473873000 (473873/1000000)
 23   0.478612000 (478612/1000000)
 29   0.482535000 (482535/1000000)
 31   0.483060000 (483060/1000000)
 37   0.487377000 (487377/1000000)
 41   0.487871000 (487871/1000000)
 43   0.489587000 (489587/1000000)
 47   0.489378000 (489378/1000000)
 53   0.490486000 (490486/1000000)
 59   0.491197000 (491197/1000000)
 61   0.491372000 (491372/1000000)
 67   0.492079000 (492079/1000000)
 71   0.493632000 (493632/1000000)
 73   0.494255000 (494255/1000000)
 79   0.493439000 (493439/1000000)
 83   0.494264000 (494264/1000000)
 89   0.495205000 (495205/1000000)
 97   0.494529000 (494529/1000000)
101   0.494480000 (494480/1000000)
103   0.494896000 (494896/1000000)
107   0.494841000 (494841/1000000)
109   0.496449000 (496449/1000000)
113   0.494854000 (494854/1000000)
127   0.495656000 (495656/1000000)

(Desplaza el cuadro de código para ver todas las filas de primos, hasta P=127).

La estadística de ~30% para P=3, es simplemente porque 3 tiene sólo un residuo cuadrático (es decir, 1).

---

Ejemplo de ejecución 2 - Determinación de cuadrados perfectos:

Test Mode

  0. Statistics for N > P being a quadratic residue mod P
  1. Probable perfect square algorithm

Enter test [0|1] 1
Number of primes: 20
Number of tests (T): 10000000
Upper bound for N: 10000000000000000

Generating 20 primes...
Done: P_max=73

Testing 10000000 random values of N, 73 < N <= 10000000000000000...
# primes          : 20
# N's tested      : 10000000
# false positives : 23
success rate      : 0.999997700

Answer 3

Como esto está en el foro de matemáticas y no en uno de los muchos foros de programación, voy a dar una respuesta puramente matemática. Si quieres mi respuesta a una versión de programación de esta pregunta, en Python, ver el sitio de stackoverflow y/o visite los comentarios más abajo.

Una cosa que podrías hacer para ahorrar tiempo y esfuerzo es eliminar el número de la consideración de cuadrado perfecto verificando rápidamente que no lo es. Lo que quiero decir es que no voy a extraer la raíz, ni voy a verificar si un número es un cuadrado perfecto, sino que voy a verificar que un número NO es un cuadrado perfecto. Algunas de estas pistas son casi sin esfuerzo, puede ejecutar estos como un precursor de cualquier algoritmo más complicado. Al fin y al cabo, no tiene sentido perder tiempo y esfuerzo en un algoritmo complicado cuando puedes demostrar que un número no es un cuadrado perfecto con uno más sencillo.

Por lo tanto, debes conocer algunas de las interesantes propiedades de los cuadrados perfectos, si es que aún no las conoces.

En primer lugar, cualquier cuadrado perfecto que termine en 0, o un conjunto de ceros, debe contener un número par de ceros finales. Por lo tanto, si el número de ceros que siguen a las cifras menos significativas de un número entero están en cantidad impar, no es un cuadrado perfecto. 57, 000 no es un cuadrado perfecto. Si hay un número par de ceros, puedes ignorarlos por completo y reducir tu número de prueba a los dígitos que preceden a la cadena de ceros: podemos probar la cuadratura perfecta de 640.000 y 820.000 probando sólo el 64 y el 82.

Algo similar se puede hacer en binario. Si se trata de programación, se puede probar fácilmente los factores de $4=2^2$ y reducir la escala mediante operaciones a nivel de bits. En Python prefiero la prueba condicional n&3 == 0, y la operación n >> 2. Esto es efectivamente lo mismo que la prueba anterior, excepto en la lógica digital/binaria donde la base es 2 en lugar de 10.

En segundo lugar, todos los cuadrados perfectos terminan en los números 0, 1, 4, 5, 6 o 9. Puedes ignorar el 0 si observas primero la regla número 1. Esta es una condición necesaria. Reconozca que esta es una operación mod 10. Por lo tanto, si su número de prueba termina (el dígito de las unidades) en un 2, 3, 7 u 8, esto es suficiente para decir que el número no es un cuadrado perfecto. Por ejemplo, el número 934,52 3 obviamente no es un cuadrado perfecto. ¿Lo ves? Con esta regla ya hemos eliminado dos quintas partes de todos los números posibles.

Los dos últimos dígitos de un número de prueba no pueden ser ambos impar. 34,833,8 79 no es un cuadrado perfecto porque tanto 7 como 9 son Impares.

Si el número de la prueba termina en un 1 o un 9, el número de dos dígitos que lo precede TIENE que ser un múltiplo de 4. Los ejemplos incluyen 81 y el número 57, 121 (porque 5,7 12 es un múltiplo de 4). Números como 24 62 1 no son cuadrados perfectos porque 62 no es un múltiplo de 4.

Si el número de la prueba termina en 4, la cifra que lo precede tiene que ser par. Si no es par, no es un cuadrado perfecto. 23,0 7 4 no es un cuadrado perfecto.

Si el número de la prueba termina en 6, la cifra que lo precede debe ser impar. Si no es impar entonces no es un cuadrado perfecto. 56,8 4 El 6 no es un cuadrado perfecto.

Si el número de prueba termina en 5, la cifra que lo precede debe ser un 2. Además, la(s) cifra(s) que precede(n) a ese 2 debe(n) ser un 0, otro 2, o las cifras 06 o 56. El número 33 1,62 5 no es un cuadrado perfecto.

Ahora un poco de aritmética de módulos. Se puede hacer en papel o en la cabeza, por lo que no se necesitan ordenadores.

Un cuadrado perfecto debe ser equivalente a 0, 1 o 4 en mod 8. Si no es así, sabes que no tienes un cuadrado perfecto. Pero si tienes un cuadrado perfecto, el 0, 1 o 4 te proporciona información útil sobre la raíz cuadrada. Si obtienes un 1 en mod 8 entonces tu raíz es impar, si 0 en mod 8 la raíz es un múltiplo de 4, si 4 en mod 8 entonces la raíz es justa pero no un múltiplo de 4.

Hablando de pruebas mod 8, en la lógica binaria podemos emplear operaciones bit a bit. Si se expresa en binario, los tres dígitos más pequeños de un cuadrado perfecto siempre terminan en 001, es decir, n&7 == 1. Esto es cierto después de haber restado todas las potencias de 4 (prueba 1 de la variación binaria), de lo contrario n&3 == 0 también podría ser cierto.

Existe la prueba del mod 9. Los resultados tienen que ser 0, 1, 4 o 7 en mod 9. Si no (2,3,5,6,8) entonces no tienes un cuadrado perfecto. El número 56,430,143 no es un cuadrado perfecto; lo sé porque el 56,430,143 % 9 = 8. Alternativamente, busque la "raíz digital" (suma de los dígitos, repetidos, a un valor singular), esencialmente lo mismo que la prueba mod 9. Si su valor es 2, 3, 5, 6 u 8 entonces no es un cuadrado perfecto, pero podría serlo si tiene 1,4,7,9.

En mod 13, todos los cuadrados perfectos son equivalentes a 0,1,3,4,9,10,12; y en mod 7 deben ser equivalentes a 1,2,4. PARA QUE LO SEPAS.

Además, observe que $(n+1)^2 = n^2 + 2n + 1$ . Claramente si su número de prueba $N\in (n^2,n^2+2n+1)$ entonces se encuentra entre dos cuadrados perfectos consecutivos. Si $n,n^2$ se conocen, para algunos más grandes $n^2<N$ sería bastante fácil rechazar cualquier valor en este intervalo.

En este punto, si su número de prueba no ha fallado ninguna de las pruebas, entonces y sólo entonces pondría los recursos en la extracción de raíces u otros algoritmos complicados. Estas pruebas anteriores utilizan poco más que comparaciones, condicionales, conteo y sumas de un solo dígito, algunas incluso pueden hacerse con lógica de bits.

Espero que esta información te ayude a ti y a otras personas que quieran orientarse al respecto.

También me gustaría señalar que cualquier factor primo de su número de prueba que se encuentre en una multiplicidad impar tampoco es un cuadrado perfecto. Sin embargo, este enfoque requiere más tiempo. Sólo tienes que comprobar los primos entre 2 y sqrt(n). Si encuentras un primo que se divide en n, pero lo hace sólo un número impar de veces, no tienes un número cuadrado. Tomemos el cuadrado perfecto 99,225. Su primo se divide en [3,3,3,3,5,5,7,7], con un número par de cada uno. Mientras que el no cuadrado 55,125 es primo factorizado en [3,3,5,5,7,7], con un número impar de 5's.

Además, puede ser razonable reducir la escala de tu número factorizando cualquier factor cuadrado que encuentres. Puedes tener una lista precalculada de primos y(?) sus cuadrados esperando. Hacer esto podría reducir el tamaño de su número de prueba, mejorar la velocidad, etc. Cada vez que reduzcas con éxito un número, llegarás a algo más pequeño para probar. Tomemos los mencionados 99.225 y 55.125. Si sabes que 3 entra en cada uno, intenta dividir por 9. Obtendrás 11.025 y 6.125. Vuelve a intentar reducir por un factor 9 y obtendrás 1.225 y 6.125, respectivamente, y el 9 ya no entrará en ninguno de los dos. A continuación, prueba con 5. Intenta reducir por 25 y obtienes 49 y 245, respectivamente. Y así sucesivamente. Sólo tenemos que comprobar si 49 y 245 son cuadrados. El primero claramente lo es; el segundo no, porque se puede dividir por 5 una vez pero no dos.

Como nota al margen, una vez que se ha calculado un valor, puede valer la pena volver a revisar algunas de las reglas y trucos anteriores, ya que algunos de los patrones pueden surgir y revelar información.

Otro dato es que todos los enteros pueden ser factorizados en sus factores enteros, incluyendo el 1 y a sí mismo. Si esta lista se compone sólo de factores únicos, entonces se aplica esta regla. Los cuadrados no perfectos tienen un número par de factores porque vienen en pares, uno a cada lado de la raíz cuadrada. Pero los cuadrados perfectos tienen un número impar de factores únicos, ya que su raíz cuadrada se cuenta una vez. Por desgracia, esta prueba es un poco inútil, ya que implica encontrar una lista de factores que incluya la propia raíz cuadrada. Tomemos como ejemplo el cuadrado perfecto 9. Sus factores enteros son [1,3,9]. El 3 es la raíz cuadrada, pero hay un número impar de términos en la lista. El no cuadrado 10, sin embargo, tiene factores enteros [1,2,5,10].

Answer 4

Puede hacer que el algoritmo que enlaza $O(\log^2 n)$ devolviendo no sólo $\left\lfloor\sqrt n\right\rfloor$ pero también $\left\lfloor\sqrt n\right\rfloor^2$ . Entonces sólo se necesitan adiciones en cada uno de los $O(\log n)$ pasos, que sólo llevan $O(\log n)$ tiempo.

Answer 5

Creo que tengo una respuesta parcial. Lo que realmente quería era un algoritmo que decidiera la cuadratura sin examinar todos los dígitos de entrada, como hace el algoritmo de la paridad (en base 10).

Pero creo que no existe tal algoritmo. Supongamos que $s_i$ y $s_i'$ eran números que, representados en base $r$ están de acuerdo en todo menos en su $i$ dígito. Un algoritmo $\mathcal A$ que decidió la cuadratura de la base- $r$ numérico tendría que examinar el $i$ de su entrada. Si $\mathcal A$ examina la $i$ El hecho de examinar el último dígito antes o después no supone ninguna diferencia: examinar el último significa que $\mathcal A$ ha examinado toda su entrada, y examinarla antes no proporciona ninguna información para distinguir $s_i$ y $s_i'$ .

Así que creo que si puedo demostrar que $s_i$ y $s_i'$ existen realmente para todas las opciones de $r$ y $i$ ya he terminado. Necesito $s_i$ cuadrado y $s_i'$ no cuadrados, y $|s_i - s_i'| = kr^i $ para algunos $k$ . Pero (agitando las manos) esto es extremadamente fácil de lograr porque hay muchas opciones posibles de $s_i'$ .

Debería comprobar que el argumento no pasa cuando $\mathcal A$ es comprobar la divisibilidad por $d$ en lugar de la cuadratura. Pero hace no pasar: necesito $m_i$ , un múltiplo de $k$ y $m_i'$ no un múltiplo de $k$ , donde $|m_i - m_i'| = kr^i$ para algunos $k$ . Pero si $d|r$ no hay tal $m_i$ y $m_i'$ a menos que $i=0$ y, de hecho, el $o$ La única cifra que debemos examinar es la de la tercera.

Esto todavía deja abierto si hay un algoritmo significativamente mejor que $O(\log^2 n)$ aunque deba examinar toda la entrada. Pero descarta un algoritmo que sea mejor que $O(\log n)$ .