Desafío
Encuentre la cubierta de bases más pequeña (p. Ej., Módulos) cuyos conjuntos de residuos cuadráticos se pueden probar mediante la búsqueda en la tabla para determinar definitivamente si un entero no negativo n es un cuadrado perfecto. Todas las bases deben ser menores o iguales a la raíz cuadrada del valor máximo de n .
La respuesta con el conjunto más pequeño de bases para una categoría dada de n gana el desafío. (Esto significa que potencialmente puede haber más de un ganador). Las categorías de n son:
Category Maximum allowed n Maximum allowed modulus/base
------------- -------------------- ----------------------------
8-bit values 255 15
16-bit values 65535 255
32-bit values 4294967295 65535
64-bit values 18446744073709551615 4294967295
En el caso de un empate con dos conjuntos que tengan la misma cardinalidad, el empate irá al conjunto que tenga la mayor capacidad de detectar no cuadrados anteriormente en la secuencia.
En el caso de que no se encuentren cubiertas completas (lo cual es muy probable para las categorías de 32 bits y 64 bits), el ganador será el conjunto de bases que descarta estadísticamente o de forma comprobable el mayor porcentaje de no cuadrados (sin incorrectamente informar cuadrados como no cuadrados). Vea a continuación una discusión sobre portadas incompletas.
Antecedentes
En muchas aplicaciones de teoría de números, surge la pregunta de si algún número n es un cuadrado perfecto (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, etc.). Una forma de probar si n es cuadrado es probar si floor (√n) ² = n, es decir, si la raíz cuadrada redondeada hacia abajo de n , cuando está al cuadrado, devuelve n . Por ejemplo, floor (√123) ² = 11² = 121, que no es 123, entonces 123 no es cuadrado; pero piso (√121) ² = 11² = 121, entonces 121 es cuadrado. Este método funciona bien para números pequeños, especialmente cuando hay disponible una operación de raíz cuadrada de hardware. Pero para grandes números (cientos o miles de bits) puede ser muy lento.
Otra forma de probar la cuadratura es descartar no cuadrados utilizando tablas de residuos cuadráticos. Por ejemplo, todos los cuadrados en la base 10 deben tener un dígito final (un lugar) que sea 0, 1, 4, 5, 6 o 9. Estos valores forman el conjunto de residuos cuadráticos para la base 10. Entonces, si una base -10 número termina en 0, 1, 4, 5, 6 o 9, sabe que puede ser cuadrado, y se requerirá un examen más detallado. Pero si una base-10 termina en números 2, 3, 7, u 8, entonces puede estar seguro de que es no cuadrado.
Así que echemos un vistazo a otra base. Todos los cuadrados en la base 8 deben terminar en 0, 1 o 4, lo que convenientemente es solo 3 de 8 posibilidades, lo que significa un 37.5% de posibilidades de que un número aleatorio sea posiblemente cuadrado, o 62.5% de posibilidades de que un número aleatorio definitivamente no sea cuadrado. Esas son probabilidades mucho mejores que las que da la base 10. (Y tenga en cuenta que una operación de módulo de base 8 es simplemente una operación lógica y, en oposición al módulo de base 10, que es una división por 10 con el resto).
¿Hay incluso mejores bases? Bueno, sí, en realidad. Base 120 tiene 18 posibilidades (0, 1, 4, 9, 16, 24, 25, 36, 40, 49, 60, 64, 76, 81, 84, 96, 100 y 105), lo que representa solo un 15% posibilidad de ser posiblemente cuadrada. Y la base 240 es mejor aún, con solo 24 posibilidades, lo que representa solo un 10% de posibilidades de ser cuadrado.
Pero ninguna base individual por sí sola puede determinar definitivamente la cuadratura (a menos que sea mayor que el número máximo que se está probando, lo cual es eminentemente poco práctico). Una sola base solo puede descartar la cuadratura; no puede verificar de manera concluyente la cuadratura. Solo un conjunto cuidadosamente seleccionado de bases, trabajando juntas, puede verificar de manera concluyente la cuadratura en un rango de enteros.
Entonces, la pregunta es: ¿qué conjunto de bases forma una cobertura mínima que, en conjunto, permite la deducción definitiva de la cuadratura o no cuadratura?
Ejemplo de una cobertura correcta pero no mínima
La cubierta de 16 bases {3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 29, 31, 37} es suficiente para determinar definitivamente la cuadratura o no cuadratura de todos los valores de 16 bits de 0 a 65535. Pero no es una cobertura mínima , porque existe al menos una cubierta de 15 bases que también es fácilmente detectable. De hecho, es probable que existan cubiertas mucho más pequeñas, tal vez con tan solo 6 o 7 bases.
Pero a modo de ilustración, echemos un vistazo a la prueba de un valor de muestra de n con este conjunto de cubiertas de 16 bases. Estos son los conjuntos de residuos cuadráticos para el conjunto de bases anterior:
Base m Quadratic residue table specific to base m
------ ----------------------------------------------------
3 {0,1}
4 {0,1}
5 {0,1,4}
7 {0,1,2,4}
8 {0,1,4}
9 {0,1,4,7}
11 {0,1,3,4,5,9}
13 {0,1,3,4,9,10,12}
16 {0,1,4,9}
17 {0,1,2,4,8,9,13,15,16}
19 {0,1,4,5,6,7,9,11,16,17}
23 {0,1,2,3,4,6,8,9,12,13,16,18}
25 {0,1,4,6,9,11,14,16,19,21,24}
29 {0,1,4,5,6,7,9,13,16,20,22,23,24,25,28}
31 {0,1,2,4,5,7,8,9,10,14,16,18,19,20,25,28}
37 {0,1,3,4,7,9,10,11,12,16,21,25,26,27,28,30,33,34,36}
Ahora probemos el número n = 50401 usando este conjunto de bases, convirtiéndolo en cada base. (Esta no es la forma más eficiente de examinar los residuos, pero es suficiente para fines explicativos). Es el lugar del 1 que nos interesa aquí (marcado entre paréntesis a continuación):
Base "Digits" in base m
m m^9 m^8 m^7 m^6 m^5 m^4 m^3 m^2 m^1 ( m^0 )
---- -----------------------------------------------------------------
3 2 1 2 0 0 1 0 2 0 ( 1 ) ✓
4 3 0 1 0 3 2 0 ( 1 ) ✓
5 3 1 0 3 1 0 ( 1 ) ✓
7 2 6 6 6 4 ( 1 ) ✓
8 1 4 2 3 4 ( 1 ) ✓
9 7 6 1 2 ( 1 ) ✓
11 3 4 9 5 ( 10 )
13 1 9 12 3 ( 0 ) ✓
16 12 4 14 ( 1 ) ✓
17 10 4 6 ( 13 ) ✓
19 7 6 11 ( 13 )
23 4 3 6 ( 8 ) ✓
25 3 5 16 ( 1 ) ✓
29 2 1 26 ( 28 ) ✓
31 1 21 13 ( 26 )
37 36 30 ( 7 ) ✓
Entonces podemos ver que en 13 de estas bases, el residuo coincide con un residuo cuadrático conocido (llame a esto un "hit" en la tabla), y en 3 de estas bases, el residuo no coincide con un residuo cuadrático conocido (llame a esto un "perder"). Todo lo que se necesita es 1 error para saber que un número no es cuadrado, por lo que podríamos detenernos en 11, pero con fines ilustrativos, hemos examinado las 16 bases aquí.
Ejemplo de una portada incompleta
Técnicamente, una cubierta incompleta no es una cubierta, pero eso no viene al caso. El conjunto de bases {7, 8, 11, 15} cubre casi todos los valores de 8 bits de n de 0 a 255 correctamente, pero no del todo. En particular, identifica incorrectamente 60 y 240 como cuadrados (estos son falsos positivos), pero identifica correctamente todos los cuadrados reales (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196 y 225) y no hace otros falsos positivos. Entonces, este es un conjunto de 4 que casi tiene éxito como solución, pero finalmente falla, porque una cubierta incompleta no es una solución válida.
Para 8-bit n , el conjunto de bases {7, 8, 11, 15} es uno de dos conjuntos de 4 bases que producen dos errores, y hay conjuntos siete de 4 bases que sólo producen un error. No existen conjuntos de 4 bases que formen una cobertura completa y precisa de valores de 8 bits. ¿Puedes encontrar un conjunto de 5 bases que no produzcan errores y cubran todos los valores de 8 bits correctamente? ¿O necesitas 6 o más? (Sé la respuesta para n de 8 bits , pero no la voy a revelar. No sé la respuesta para 16, 32 o 64 bits, y creo que incluso el 16- El caso de bits es imposible de resolver mediante la búsqueda de fuerza bruta. Resolver los casos de 32 bits y 64 bits ciertamente requerirá técnicas de búsqueda genéticas, heurísticas u otras.
Un comentario sobre números criptográficamente grandes
Más allá de los números de 64 bits, en los cientos o miles de dígitos binarios, aquí es donde una verificación rápida de la cuadratura es realmente útil, incluso si la cubierta está incompleta (lo que sin duda será para números realmente grandes). ¿Cómo podría ser útil una prueba como esta, incluso si no es lo suficientemente decisiva? Bueno, imagine que tuvo una prueba extremadamente rápida para la cuadratura que funcionó correctamente el 99.9% del tiempo y dio falsos negativos el 0.1% restante del tiempo y nunca dio falsos positivos. Con tal prueba, podría determinar la no cuadratura de un número casi al instante, y luego, en los casos excepcionales de indecisión, podría recurrir a un método más lento para resolver lo desconocido de una manera diferente. Esto te ahorraría bastante tiempo.
Por ejemplo, el conjunto {8, 11, 13, 15} es correcto el 99.61% del tiempo para valores de 8 bits de n de 0 a 255, es correcto el 95.98% del tiempo para valores de 16 bits de n de 0 a 65535, y es correcto el 95.62% del tiempo para valores de n de 24 bits de 0 a 16777215. A medida que n va al infinito, el porcentaje de corrección para este conjunto de bases disminuye, pero se acerca asintóticamente y nunca cae por debajo del 95.5944% exactitud.
Por lo tanto, incluso este conjunto muy pequeño de 4 bases pequeñas es útil para identificar casi de inmediato alrededor de 22 de los 23 números arbitrariamente grandes como no cuadrados, lo que evita la necesidad de una mayor inspección de esos números por métodos más lentos. Entonces, los métodos más lentos solo deben aplicarse en el pequeño porcentaje de casos que esta prueba rápida no puede descartar.
Es interesante observar que algunas bases de 16 bits logran más del 95% por sí solas. De hecho, cada una de las bases a continuación puede eliminar mejor que el 97% de todos los números hasta el infinito como no cuadrados. El conjunto de residuos cuadráticos para cada una de estas bases se puede representar como una matriz de bits empaquetados utilizando solo 8192 bytes.
Aquí están las 10 bases simples más poderosas de menos de 2 ^ 16
Rank Base Prime factorization Weeds out
---- ------------------------------ ---------
1. 65520 = 2^4 x 3^2 x 5 x 7 x 13 97.95%
2. 55440 = 2^4 x 3^2 x 5 x 7 x 11 97.92%
3. 50400 = 2^5 x 3^2 x 5^2 x 7 97.56%
4. 52416 = 2^6 x 3^2 x 7 x 13 97.44%
5. 61200 = 2^4 x 3^2 x 5^2 x 17 97.41%
6. 44352 = 2^6 x 3^2 x 7 x 11 97.40%
7. 63360 = 2^7 x 3^2 x 5 x 11 97.39%
8. 60480 = 2^6 x 3^3 x 5 x 7 97.38%
9. 63840 = 2^5 x 3 x 5 x 7 x 19 97.37%
10. 54720 = 2^6 x 3^2 x 5 x 19 97.37%
¿Ves algo interesante que todas estas bases tengan en común? No hay razón para pensar que podrían ser útiles en combinación (tal vez lo sean, tal vez no lo sean), pero aquí hay algunas buenas pistas sobre qué bases pueden ser más influyentes para las categorías más grandes de números.
Desafío secundario: una de las bases más influyentes (si no la más) hasta 2 ^ 28 es 245044800, que solo puede eliminar correctamente el 99.67% de los no cuadrados, o alrededor de 306 de 307 números aleatorios arrojados. ¿Puedes encontrar la base única más influyente de menos de 2 ^ 32?
Relacionado
Hay algunas ideas muy buenas en las siguientes preguntas que están estrechamente relacionadas, así como varios trucos de microoptimización para acelerar ciertas operaciones. Aunque las preguntas vinculadas no se proponen específicamente para encontrar el conjunto de bases más sólido, la idea de bases sólidas es implícitamente central en algunas de las técnicas de optimización utilizadas allí.
fuente
Respuestas:
Mathematica
Realmente no sé mucho sobre teoría de números (desafortunadamente), así que este es un enfoque bastante ingenuo. Estoy usando un algoritmo codicioso que siempre agrega la base que tiene más errores para los números restantes.
Resuelve 8 bits en poco tiempo con las siguientes 6 bases:
16 bits toma 6s y da como resultado la siguiente cubierta de 6 bases:
Para los casos más grandes, este enfoque obviamente se queda sin memoria.
Para ir más allá de 16 bits, necesitaré encontrar una manera de verificar que una cubierta esté completa sin tener que mantener una lista de todos los números hasta N max (o ir y aprender sobre la teoría de números).
Editar: Tiempo de ejecución reducido para 16 bits de 66 a 8 s al rellenar previamente la lista de números con solo aquellos que no están descartados por la base más efectiva. Esto también debería mejorar significativamente la huella de la memoria.
Editar: agregué dos optimizaciones menores para reducir el espacio de búsqueda. No es una de las categorías oficiales, pero con eso encontré una cubierta de 8 bases para 24 bits en 9.3 horas:
En cuanto a las optimizaciones, ahora estoy omitiendo todas las bases que dividen el LCM de las bases que ya están en la cubierta, y cuando pruebo la eficiencia de una base, solo lo pruebo contra los números hasta el LCM de esa nueva base y todas las bases que ya tener.
fuente