Desafio
Encontre a menor cobertura de bases (por exemplo, módulos) cujos conjuntos de resíduos quadráticos podem ser testados por meio de pesquisa de tabela para determinar definitivamente se um número inteiro não negativo n é ou não um quadrado perfeito. As bases devem ser todas iguais ou iguais à raiz quadrada do valor máximo de n .
A resposta com o menor conjunto de bases para uma determinada categoria de n vence o desafio. (Isso significa que pode haver mais de um vencedor.) As categorias de n são:
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
No caso de um empate com dois sets com cardinalidade igual, o empate irá para o set com maior capacidade de detectar não quadrados no início da sequência.
Caso nenhuma cobertura completa seja encontrada (o que é inteiramente provável para as categorias de 32 e 64 bits), o vencedor será o conjunto de bases que estatisticamente ou comprovadamente exclui a maior porcentagem de não quadrados (sem incorretamente). quadrados de relatório como não quadrados). Veja abaixo uma discussão sobre capas incompletas.
fundo
Em muitas aplicações da teoria dos números, surge a questão de saber se algum número n é um quadrado perfeito (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, etc.). Uma maneira de testar se n é quadrado é testar se floor (√n) ² = n, ou seja, se a raiz quadrada e arredondada de n , quando quadrado, retorna n . Por exemplo, floor (√123) ² = 11² = 121, que não é 123, portanto 123 não é quadrado; mas floor (√121) ² = 11² = 121, então 121 é quadrado. Esse método funciona bem para números pequenos, especialmente quando uma operação de raiz quadrada de hardware está disponível. Mas para números grandes (centenas ou milhares de bits), pode ser muito lento.
Outra maneira de testar a quadratura é descartar não quadrados usando tabelas de resíduos quadráticas. Por exemplo, todos os quadrados na base 10 devem ter um dígito final (um local) que seja 0, 1, 4, 5, 6 ou 9. Esses valores formam o conjunto de resíduo quadrático da base 10. Portanto, se uma base O número -10 termina em 0, 1, 4, 5, 6 ou 9, você sabe que pode ser quadrado e será necessário um exame mais aprofundado. Mas se uma base-10 termina número em 2, 3, 7 ou 8, então você pode ter certeza que é não quadrado.
Então, vamos olhar para outra base. Todos os quadrados na base 8 devem terminar em 0, 1 ou 4, o que convenientemente é apenas 3 de 8 possibilidades, o que significa 37,5% de chance de um número aleatório ser quadrado ou 62,5% de chance de um número aleatório definitivamente não ser quadrado. Essas são probabilidades muito melhores do que a base 10 oferece. (E observe que uma operação do módulo base 8 é simplesmente uma operação lógica e, em oposição ao módulo base 10, que é uma divisão por 10 com o restante.)
Existem bases ainda melhores? Bem, sim, na verdade. A base 120 possui 18 possibilidades (0, 1, 4, 9, 16, 24, 25, 36, 40, 49, 60, 64, 76, 81, 84, 96, 100 e 105), o que representa apenas 15% chance de possivelmente ser quadrado. E a base 240 é melhor ainda, com apenas 24 possibilidades, representando apenas 10% de chance de possivelmente ser quadrada.
Mas nenhuma base sozinha pode determinar definitivamente a quadratura (a menos que seja maior que o número máximo sendo testado, o que é eminentemente impraticável). Uma única base por si só pode excluir a quadratura; não pode verificar conclusivamente a quadratura. Somente um conjunto de bases cuidadosamente selecionado, trabalhando juntos, pode verificar conclusivamente a quadratura em um intervalo de números inteiros.
Então, a pergunta passa a ser: que conjunto de bases forma uma cobertura mínima que, em conjunto, permite a dedução definitiva de quadratura ou não quadratura?
Exemplo de uma cobertura correta, mas não mínima
A cobertura de 16 bases da capa {3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 29, 31, 37} é suficiente para determinar definitivamente a quadratura ou não quadratura de todos os valores de 16 bits são de 0 a 65535. Mas não é uma cobertura mínima , porque existe pelo menos uma cobertura de 15 bases que também é facilmente detectável. De fato, é provável que existam coberturas muito menores - talvez com apenas 6 ou 7 bases.
Mas, para ilustração, vamos dar uma olhada no teste de um valor de amostra de n usando este conjunto de capas de 16 bases. Aqui estão os conjuntos de resíduos quadráticos para o conjunto de bases acima:
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}
Agora vamos testar o número n = 50401 usando esse conjunto de bases, convertendo-o em cada base. (Esta não é a maneira mais eficiente de examinar resíduos, mas é suficiente para fins explicativos.) É o lugar do 1 em que estamos interessados aqui (marcados abaixo entre parênteses):
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 ) ✓
Portanto, podemos ver que em 13 dessas bases, o resíduo corresponde a um resíduo quadrático conhecido (chame isso de "acerto" na tabela) e em 3 dessas bases, o resíduo não corresponde a um resíduo quadrático conhecido (chame a isso de "senhorita"). Basta uma falta para saber que um número não é quadrado, então podemos parar às 11, mas, para fins ilustrativos, examinamos todas as 16 bases aqui.
Exemplo de uma capa incompleta
Tecnicamente, uma capa incompleta não é uma capa, mas isso não vem ao caso. O conjunto de bases {7, 8, 11, 15} cobre quase todos os valores de n de 8 bits de 0 a 255 corretamente, mas não completamente. Em particular, identifica incorretamente 60 e 240 como sendo quadrados (esses são falsos positivos) - mas identifica corretamente todos os quadrados reais (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196 e 225) e não faz outros falsos positivos. Portanto, este é um conjunto de 4 que quase consegue como solução, mas acaba falhando, porque uma cobertura incompleta não é uma solução válida.
Para n de 8 bits , o conjunto de bases {7, 8, 11, 15} é um dos dois conjuntos de 4 bases que produzem dois erros e existem sete conjuntos de 4 bases que produzem apenas um erro. Atualmente, não existem conjuntos de 4 bases que formam uma cobertura completa e precisa dos valores de 8 bits. Você consegue encontrar um conjunto de 5 bases que não produzam erros, cobrindo todos os valores de 8 bits corretamente? Ou você precisa de 6 ou mais? (Conheço a resposta para n de 8 bits , mas não vou denunciá-la. Não conheço a resposta para 16, 32 ou 64 bits, e acredito que até os 16 é impossível resolver casos de bits por meio de pesquisa de força bruta. A resolução de casos de 32 e 64 bits certamente exigirá técnicas genéticas, heurísticas ou outras técnicas de pesquisa.)
Um comentário sobre números criptograficamente grandes
Além dos números de 64 bits - entre centenas ou milhares de dígitos binários - é aqui que uma verificação rápida de esquadrinha é realmente mais útil, mesmo que a capa esteja incompleta (o que certamente será para números realmente grandes). Como um teste como esse ainda pode ser útil, mesmo que seja insuficientemente decisivo? Bem, imagine que você fez um teste extremamente rápido de esqueleto, que funcionou corretamente 99,9% das vezes e deu negativos falsos nos 0,1% restantes e nunca deu falsos positivos. Com esse teste, você seria capaz de determinar a não quadratura de um número quase instantaneamente e, em casos excepcionais de indecisão, poderia recorrer a um método mais lento para resolver o desconhecido de uma maneira diferente. Isso economizaria um pouco de tempo.
Por exemplo, o conjunto {8, 11, 13, 15} está correto 99,61% do tempo para valores de 8 bits de n de 0 a 255, está correto 95,98% do tempo para valores de 16 bits de n de 0 a 65535 e está correto 95,62% do tempo para valores de 24 bits de n de 0 a 16777215. À medida que n vai para o infinito, a porcentagem de correção para esse conjunto de bases diminui, mas se aproxima assintoticamente e nunca cai abaixo de 95,5944% correção.
Portanto, mesmo esse conjunto minúsculo de 4 bases pequenas é útil para identificar quase imediatamente cerca de 22 dos 23 números arbitrariamente grandes como não-quadrados - evitando a necessidade de uma inspeção adicional desses números por métodos mais lentos. Os métodos mais lentos precisam ser aplicados apenas na pequena porcentagem de casos que não poderiam ser descartados por esse teste rápido.
É interessante notar que algumas bases de 16 bits alcançam melhor que 95% por conta própria. De fato, cada uma das bases abaixo é capaz de eliminar melhor que 97% de todos os números até o infinito, como não sendo quadrados. O resíduo quadrático definido para cada uma dessas bases pode ser representado como uma matriz de bits compactados usando apenas 8192 bytes.
Aqui estão as 10 bases únicas mais poderosas com 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%
Vê algo interessante que todas essas bases têm em comum? Não há razão para pensar que eles possam ser úteis em combinação (talvez sejam, talvez não sejam), mas há algumas boas dicas aqui sobre quais bases provavelmente serão mais influentes para as categorias maiores de números.
Desafio lateral: uma das bases mais influentes (se não a mais) até 2 ^ 28 é 245044800, que sozinha pode eliminar corretamente 99,67% dos não quadrados, ou cerca de 306 dos 307 números aleatórios lançados nela. Você consegue encontrar a base única mais influente com menos de 2 ^ 32?
Relacionado
Existem algumas idéias muito boas nas perguntas a seguir que estão intimamente relacionadas, bem como vários truques de micro-otimização para tornar determinadas operações mais rápidas. Embora as perguntas vinculadas não se proponham especificamente a encontrar o conjunto mais forte de bases, a idéia de bases fortes é implicitamente central em algumas das técnicas de otimização usadas lá.
fonte
Respostas:
Mathematica
Eu realmente não sei muito sobre teoria dos números (infelizmente), então essa é uma abordagem bastante ingênua. Eu estou usando um algoritmo ganancioso que sempre adiciona a base que tem mais erros para os números restantes.
Resolve 8 bits rapidamente com as 6 bases a seguir:
16 bits leva 6s e resulta na seguinte tampa de 6 bases:
Para os casos maiores, essa abordagem obviamente fica sem memória.
Para ir além de 16 bits, precisarei descobrir uma maneira de verificar se uma capa está completa sem realmente manter uma lista de todos os números até N max (ou vá e aprenda sobre teoria dos números).
Editar: tempo de execução reduzido para 16 bits, de 66 para 8 segundos, preenchendo previamente a lista de números apenas com aqueles que não são descartados pela base mais eficaz. Isso também deve melhorar significativamente o espaço ocupado pela memória.
Editar: eu adicionei duas otimizações menores para reduzir o espaço de pesquisa. Não é uma das categorias oficiais, mas com isso eu encontrei uma capa de 8 bases para 24 bits em 9,3 horas:
Quanto às otimizações, agora estou pulando todas as bases que dividem o LCM das bases que já estão na capa e, quando testo a eficiência de uma base, testo somente contra números até o LCM dessa nova base e todas as bases que já ter.
fonte