Solución:
Véase el artículo de Bernstein, Lenstra y Pila: Detecting Perfect Powers by Factoring into Coprimes, Mathematics of Computation, Volumen 76, # 257, enero de 2007, págs. 385-388. O aquí.
Del resumen: Este artículo presenta un algoritmo que, dado un número entero n> 1, encuentra el k más grande tal que n es una k-ésima potencia.
El algoritmo se ejecuta en el tiempo $ log (n) ( log log (n)) ^ O (1) $.
Aquí hay 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 del enfoque utilizado en la biblioteca GMP.
Premisa 1: Si un entero $ n $ es un cuadrado perfecto y $ P $ es un primo impar Contrapositivo: Si $ n $ (mod $ P $) es un módulo cuadrático sin residuos $ 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 0) y $ frac (P-1) 2 $ no cuadráticos residuos. Entonces, existe una probabilidad del 50% de que un entero aleatorio $ n $ sea un residuo cuadrático (mod $ P $). Podemos inferir lo siguiente. Dado un número entero $ n $: Entonces podemos construir una prueba probabilística robusta en el mismo estilo que la prueba de primalidad de Fermat. Elegimos un $ P_ 0 $ principal y verificamos el criterio de Euler para $ n $ (mod $ P_ 0 $). Cada vez que $ n $ pasa como un residuo cuadrático, la probabilidad de intersección de que $ n $ no sea cuadrado disminuye en un 50%, por lo que solo se necesitan 10 pruebas para determinar que $ n $ es un cuadrado perfecto con> 99,9% de probabilidad[2], independientemente de su tamaño. En otras palabras, si $ n $ no es un cuadrado perfecto, al menos una de las pruebas habrá fallado antes de ese punto (con> 99,9% de probabilidad). los key aquí es que los no cuadrados siempre fallan el criterio a una tasa de ~ 50% (probado contra varios primos). Entonces, si después de una docena de pruebas de este tipo, $ n $ no ha fallado el criterio ni una sola vez, existe una probabilidad muy alta de que sea un cuadrado perfecto. Me doy cuenta de que me falta seriamente la terminología bayesiana adecuada aquí, pero esto funciona y puedes probarlo. La probabilidad de error se puede hacer arbitrariamente pequeña probando con más números primos. Complejidad del tiempo: Dado que la elección de los números primos $ P_ i $ no necesita depender de $ n $, la determinación de los exponentes para las pruebas requiere $ mathcal O (1) $, creo. Y dado que el nivel de confianza deseado también es independiente de $ n $, la complejidad de tiempo total parece equivalente a la de la exponenciación modular. Usar el método de exponenciación al elevar al cuadrado con un algoritmo de multiplicación eficiente como k-way Toom-Cook o Schonhage-Strassen da una complejidad de tiempo general muy cercana a $ mathcal O $ (log $ n $) base $ r $, dependiendo de los parámetros elegidos. Consulte los artículos de Wikipedia vinculados para obtener más detalles. [1]: El criterio de Euler requiere que $ n $ y $ P $ sean coprimos; si no es así, 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 false positivos, lo cual es realmente malo. Teóricamente, se deben usar 30 primos para producir menos de 1 false positivo por cada mil millones de enteros probados, pero en la práctica he descubierto que solo los primeros 18-20 primos son suficientes para producir ninguno. Actualizar: Aquí hay una implementación funcional en C con libgmp: https://gist.github.com/jrodatus/e66d6f6b2f014f6b69543019edd23982 Ejemplo de ejecución 1: estadísticas de residuos: (Desplácese por el cuadro de código para ver todas las filas principales, hasta P = 127). La estadística de ~ 30% para P = 3, es simplemente porque 3 tiene solo 1 residuo cuadrático (es decir, 1). Ejemplo de ejecución 2: determinación de cuadrados perfectos: Dado que 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 desea mi respuesta a una versión de programación de esta pregunta, en Python, consulte el sitio de stackoverflow y / o visite los comentarios a continuación. Una cosa que podría hacer para ahorrar tiempo y esfuerzo es eliminar el número de consideración como un 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, pero voy a verificar que un número NO es un cuadrado perfecto. Algunas de estas sugerencias son casi sencillas, puede ejecutarlas como un precursor de cualquier algoritmo más complicado. Después de todo, 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 simple. Por lo tanto, necesita conocer algunas de las propiedades interesantes e interesantes de los cuadrados perfectos, si aún no lo ha hecho. En primer lugar, cualquier cuadrado perfecto que termine en 0, o un conjunto de ceros, debe contener un número par de ceros terminales. Entonces, si el número de ceros detrás de los dígitos menos significativos de un número entero está en una cantidad impar, no es un cuadrado perfecto. 57,000 no es un cuadrado perfecto. Si hay un número par de ceros, puede ignorarlos por completo y reducir su número de prueba a los dígitos que preceden al string de ceros: podemos probar 640,000 y 820,000 para una cuadratura perfecta probando solo 64 y 82. Se puede hacer algo similar en binario. Si se trata de programación, puede probar fácilmente factores de $ 4 = 2 ^ 2 $ y reducir la escala utilizando operaciones bit a bit. 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 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 la regla número 1 primero. Ésta es una condición necesaria. Reconozca que esta es una operación mod 10. Entonces, si su número de prueba termina (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,523 obviamente no es un cuadrado perfecto. ¿Mira eso? 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 impares. 34,833,879 no es un cuadrado perfecto porque tanto el 7 como el 9 son impares. Si el número de 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 numero 57,121 (porque 5,712 es un múltiplo de 4). Números como 24621 no son cuadrados perfectos porque 62 no es múltiplo de 4. Si el número de prueba termina en 4, el dígito que lo precede tiene que ser par. Si ni siquiera entonces no es un cuadrado perfecto. 23,074 no es un cuadrado perfecto. Si el número de prueba termina en 6, el dígito que lo precede debe ser impar. Si no es extraño, no es un cuadrado perfecto. 56,846 no es un cuadrado perfecto. Si el número de prueba termina en 5, el dígito que lo precede tiene un 2. Además, el dígito o dígitos que preceden al 2 deben ser un 0, otro 2 o los dígitos 06 o 56. El número 331,625 no es un cuadrado perfecto. Ahora, un poco de aritmética de módulo. Estos se pueden hacer en papel o en su cabeza, por lo que no requieren computadoras. Un cuadrado perfecto debe ser equivalente a 0, 1 o 4 en el mod 8. Si no es así, sabes que no tienes un cuadrado perfecto. Pero si tiene un cuadrado perfecto, el 0,1 o el 4 le proporcionan información útil sobre la raíz cuadrada. Si obtiene un 1 en el mod 8, entonces su raíz es impar, si 0 en el mod 8, la raíz es un múltiplo de 4, si 4 en el mod 8, entonces la raíz es par pero no un múltiplo de 4. Hablando de pruebas mod 8, en 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 true después de haber factorizado todas las potencias de 4 (prueba 1 variación binaria), de lo contrario n & 3 == 0 podría ser true también. Existe la prueba mod 9. Los resultados tienen que ser 0, 1, 4 o 7 en el 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 "raíz digital" (suma de los dígitos, repetida, 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 el mod 13, todos los cuadrados perfectos equivalen a 0,1,3,4,9,10,12; y en el mod 7 deben ser equivalentes a 1,2,4. FYI. 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 se conocen $ n, n ^ 2 $, para algunos $ n ^ 2 más grandes En este punto, si su número de prueba no ha fallado en ninguna de las pruebas, entonces y solo entonces pondría los recursos en extracción de raíz u otros algoritmos complicados. Estas pruebas anteriores usan poco más que comparación, condicionales, conteo y sumas de un solo dígito, algunas incluso se pueden hacer con lógica de bits. Espero que esta información le ayude a usted y a otras personas que deseen orientación sobre esto. También me gustaría señalar que cualquier factor primo de su número de prueba que viene en una multiplicidad impar tampoco es un cuadrado perfecto. Sin embargo, este es un enfoque que requiere más tiempo. Solo necesita verificar los números primos entre 2 y sqrt (n). Si encuentra un número primo que se divide en n, pero lo hace solo un número impar de veces, no tiene un número cuadrado. Tome el cuadrado perfecto 99,225. Su primo factorizado en [3,3,3,3,5,5,7,7], con un número par de cada uno. Mientras que el no cuadrado 55,125 se factoriza en primos en [3,3,5,5,5,7,7], con un número impar de 5. También, puede ser razonable reducir su número factorizando cualquier factor cuadrado que encuentre. Puede tener una lista precalculada de números 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 reduce con éxito un número, llega a algo más pequeño para probar. Tome los mencionados 99,225 y 55,125. Si sabe que en cada uno hay 3, intente dividir 9. Obtendrá 11,025 y 6,125. Intente reducir en un factor de 9 nuevamente y obtendrá 1,225 y 6,125, respectivamente, y 9 ya no entrará en ninguno de los dos. A continuación, intente 5. Intente reducir en 25 y obtendrá 49 y 245, respectivamente. Pronto. Solo necesitamos probar 49 y 245 para determinar la cuadratura. El primero claramente lo es; el último no lo es, porque se puede dividir entre 5 una vez, pero no dos veces. En una nota al margen, una vez que factorizas un valor, puede que valga la pena 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 números enteros se pueden factorizar en sus factores enteros, incluido 1 y él mismo. Si esta lista consta 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. Desafortunadamente, esta prueba es un poco inútil ya que implica encontrar una lista de factores que incluyen la raíz cuadrada en sí. Tome el cuadrado perfecto 9, por ejemplo. 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]. Si piensas que te ha resultado de utilidad este post, agradeceríamos que lo compartas con más programadores y nos ayudes a dar difusión a nuestra información.
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)
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