Défi
Trouvez la plus petite couverture de bases (par exemple, des modules) dont les ensembles de résidus quadratiques peuvent être testés via la recherche de table pour déterminer définitivement si un entier non négatif donné n est un carré parfait. Les bases doivent toutes être inférieures ou égales à la racine carrée de la valeur maximale de n .
La réponse avec le plus petit ensemble de bases pour une catégorie donnée de n remporte le défi. (Cela signifie qu'il peut potentiellement y avoir plus d'un gagnant.) Les catégories de n sont:
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 cas d'égalité avec deux ensembles ayant une cardinalité égale, l'égalité ira à l'ensemble ayant la plus grande capacité à détecter les non-carrés plus tôt dans la séquence.
Dans le cas où aucune couverture complète n'est trouvée (ce qui est tout à fait probable pour les catégories 32 bits et 64 bits), le gagnant sera l'ensemble de bases qui exclut statistiquement ou prouvablement le pourcentage le plus élevé de non-carrés (sans incorrectement déclarer les carrés comme des non-carrés). Voir ci-dessous pour une discussion sur les couvertures incomplètes.
Contexte
Dans de nombreuses applications de la théorie des nombres, la question se pose de savoir si un certain nombre n est ou non un carré parfait (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, etc.). Une façon de tester si n est carré est de tester si floor (√n) ² = n, c'est-à-dire si la racine carrée arrondie de n , lorsqu'elle est au carré, donne n . Par exemple, étage (√123) ² = 11² = 121, qui n'est pas 123, donc 123 n'est pas carré; mais plancher (√121) ² = 11² = 121, donc 121 est carré. Cette méthode fonctionne bien pour les petits nombres, en particulier lorsqu'une opération matérielle racine carrée est disponible. Mais pour les grands nombres (centaines ou milliers de bits), cela peut être très lent.
Une autre façon de tester la carré est d'exclure les non-carrés en utilisant des tables de résidus quadratiques. Par exemple, tous les carrés de la base 10 doivent avoir un chiffre final (à une place) qui est soit 0, 1, 4, 5, 6 ou 9. Ces valeurs forment l'ensemble des résidus quadratiques pour la base 10. Donc, si une base -10 nombre se termine par 0, 1, 4, 5, 6 ou 9, vous savez qu'il pourrait être carré, et un examen plus approfondi sera nécessaire. Mais si un nombre de base 10 se termine par 2, 3, 7 ou 8, alors vous pouvez être certain qu'il n'est pas carré.
Regardons donc une autre base. Tous les carrés de la base 8 doivent se terminer par 0, 1 ou 4, ce qui n'est commodément que 3 des 8 possibilités, ce qui signifie une probabilité de 37,5% qu'un nombre aléatoire soit éventuellement carré, ou 62,5% de chance qu'un nombre aléatoire ne soit définitivement pas carré. Ce sont de bien meilleures chances que ce que donne la base 10. (Et notez qu'une opération de module de base 8 est simplement une opération logique et, par opposition au module de base 10, qui est une division par 10 avec le reste.)
Existe-t-il des bases encore meilleures? Eh bien, oui, en fait. Base 120 a 18 possibilités (0, 1, 4, 9, 16, 24, 25, 36, 40, 49, 60, 64, 76, 81, 84, 96, 100 et 105), ce qui représente seulement 15% chance d'être carré. Et la base 240 est encore meilleure, avec seulement 24 possibilités, représentant seulement 10% de chances d'être carré.
Mais aucune base ne peut à elle seule déterminer définitivement l'équerrage (à moins qu'il ne soit plus grand que le nombre maximum testé, ce qui est tout à fait impraticable). Une seule base à elle seule ne peut exclure que l' équerrage; il ne peut pas vérifier de façon concluante l' équerrage. Seul un ensemble de bases soigneusement sélectionnées, travaillant ensemble, peut vérifier de manière concluante l'équerrage sur une gamme d'entiers.
Donc, la question devient: quel ensemble de bases forme une couverture minimale qui ensemble permet la déduction définitive de l'équerrage ou du non équerrage?
Exemple d'une couverture correcte mais non minimale
Le couvercle à 16 bases {3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 29, 31, 37} est suffisant pour déterminer définitivement l'équerrage ou le non équerrage de toutes les valeurs 16 bits 0 à 65535. Mais ce n'est pas une couverture minimale , car il existe au moins une couverture à 15 bases qui est également facilement détectable. En fait, il est probable qu'il existe des couvertures beaucoup plus petites - avec peut-être aussi peu que 6 ou 7 bases.
Mais à titre d'illustration, examinons un exemple de valeur de n à l' aide de cet ensemble de couvercles à 16 bases. Voici les ensembles de résidus quadratiques pour l'ensemble de bases ci-dessus:
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}
Maintenant, testons le nombre n = 50401 en utilisant cet ensemble de bases, en le convertissant en chaque base. (Ce n'est pas la façon la plus efficace d'examiner les résidus, mais c'est suffisant à des fins explicatives.) C'est la place du 1 qui nous intéresse ici (indiquée ci-dessous entre parenthèses):
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 ) ✓
Nous pouvons donc voir que dans 13 de ces bases, le résidu correspond à un résidu quadratique connu (appelez cela un "hit" dans le tableau), et dans 3 de ces bases, le résidu ne correspond pas à un résidu quadratique connu (appelez cela un "manquer"). Tout ce qu'il faut, c'est manquer de savoir qu'un nombre n'est pas carré, donc nous pourrions nous arrêter à 11, mais à des fins d'illustration, nous avons examiné les 16 bases ici.
Exemple de couverture incomplète
Techniquement, une couverture incomplète n'est pas une couverture, mais ce n'est pas la question. L'ensemble des bases {7, 8, 11, 15} couvre presque toutes les valeurs de 8 bits de n de 0 à 255 correctement, mais pas tout à fait. En particulier, il identifie incorrectement 60 et 240 comme étant carrés (ce sont des faux positifs) - mais il identifie correctement tous les carrés réels (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196 et 225) et ne fait aucun autre faux positif. Il s'agit donc d'un ensemble de 4 qui réussit presque comme solution, mais échoue finalement, car une couverture incomplète n'est pas une solution valide.
Pour 8 bits n , l'ensemble des bases {7, 8, 11, 15} est l' un des deux ensembles de 4 bases qui produisent deux erreurs, et il y a sept ensembles de 4 bases qui ne produisent qu'une seule erreur. Il n'existe en réalité aucun ensemble de 4 bases qui forment une couverture complète et précise des valeurs 8 bits. Pouvez-vous trouver un ensemble de 5 bases qui ne produisent aucune erreur, couvrant correctement toutes les valeurs 8 bits? Ou avez-vous besoin de 6 ou plus? (Je connais la réponse pour n 8 bits , mais je ne vais pas la révéler. Je ne connais pas la réponse pour 16 bits, 32 bits ou 64 bits, et je crois que même le 16- le cas de bits est impossible à résoudre via la recherche par force brute. La résolution des cas 32 bits et 64 bits nécessitera certainement des techniques de recherche génétiques, heuristiques ou autres.)
Un commentaire sur les nombres cryptographiquement grands
Au-delà des nombres 64 bits - dans les centaines ou des milliers de chiffres binaires - c'est là qu'un contrôle rapide de l'équerrage est vraiment le plus pratique, même si la couverture est incomplète (ce qui sera très certainement pour les très grands nombres). Comment un test comme celui-ci pourrait-il encore être utile même s'il n'est pas suffisamment décisif? Eh bien, imaginez que vous ayez eu un test extrêmement rapide pour l'équerrage qui a fonctionné correctement 99,9% du temps et a donné de faux négatifs le 0,1% restant du temps et n'a jamais donné de faux positifs. Avec un tel test, vous seriez en mesure de déterminer la non-équerrage d'un nombre presque instantanément, puis dans les cas exceptionnels d'indécision, vous pourriez alors recourir à une méthode plus lente pour résoudre l'inconnu d'une manière différente. Cela vous ferait gagner un peu de temps.
Par exemple, l'ensemble {8, 11, 13, 15} est correct 99,61% du temps pour les valeurs 8 bits de n de 0 à 255, est correct 95,98% du temps pour les valeurs 16 bits de n de 0 à 65535, et est correct 95,62% du temps pour des valeurs de 24 bits de n de 0 à 16777215. Comme n va à l'infini, le pourcentage de correction pour cet ensemble de bases diminue, mais il approche de manière asymptotique et ne descend jamais en dessous de 95,5944% exactitude.
Ainsi, même ce très petit ensemble de 4 petites bases est utile pour identifier presque immédiatement environ 22 des 23 nombres arbitrairement grands comme étant non carrés - évitant ainsi la nécessité d'une inspection plus approfondie de ces nombres par des méthodes plus lentes. Les méthodes plus lentes n'ont alors besoin d'être appliquées que dans le petit pourcentage de cas qui n'ont pas pu être écartés par ce test rapide.
Il est intéressant de noter que certaines bases 16 bits atteignent mieux que 95% toutes seules. En fait, chacune des bases ci-dessous est capable d'éliminer mieux que 97% de tous les nombres jusqu'à l'infini comme n'étant pas carrés. Le résidu quadratique défini pour chacune de ces bases peut être représenté comme un tableau de bits compressés en utilisant seulement 8192 octets.
Voici les 10 bases simples les plus puissantes de moins 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%
Vous voyez quelque chose d'intéressant que ces bases ont toutes en commun? Il n'y a aucune raison de penser qu'ils pourraient être utiles en combinaison ensemble (peut-être qu'ils le sont, peut-être qu'ils ne le sont pas), mais il y a de bons indices ici sur les bases qui seront probablement les plus influentes pour les grandes catégories de nombres.
Défi secondaire: L'une des bases les plus influentes (sinon la plus) jusqu'à 2 ^ 28 est 245044800, qui à elle seule peut éliminer correctement 99,67% des non-carrés, soit environ 306 des 307 nombres aléatoires jetés dessus. Pouvez-vous trouver la base unique la plus influente inférieure à 2 ^ 32?
en relation
Il y a de très bonnes idées dans les questions suivantes qui sont étroitement liées, ainsi que plusieurs astuces de micro-optimisation pour accélérer certaines opérations. Bien que les questions liées ne visent pas spécifiquement à trouver l'ensemble de bases le plus solide, l'idée de bases fortes est implicitement au centre de certaines des techniques d'optimisation utilisées.
la source
Réponses:
Mathematica
Je ne connais pas vraiment la théorie des nombres (malheureusement), c'est donc une approche plutôt naïve. J'utilise un algorithme gourmand qui ajoute toujours la base qui a le plus de ratés pour les nombres restants.
Il résout 8 bits en un rien de temps avec les 6 bases suivantes:
16 bits prend 6 s et donne le cache à 6 bases suivant:
Pour les cas plus importants, cette approche manque évidemment de mémoire.
Pour aller au-delà de 16 bits, je devrai trouver un moyen de vérifier qu'une couverture est complète sans vraiment garder une liste de tous les nombres jusqu'à N max (ou aller en apprendre davantage sur la théorie des nombres).
Edit: durée d'exécution réduite pour 16 bits de 66s à 8s en préremplissant la liste des nombres avec seulement ceux qui ne sont pas exclus par la base la plus efficace. Cela devrait également améliorer considérablement l'empreinte mémoire.
Edit: j'ai ajouté deux optimisations mineures pour réduire l'espace de recherche. Ce n'est pas l'une des catégories officielles, mais avec cela j'ai trouvé une couverture à 8 bases pour 24 bits en 9,3 heures:
En ce qui concerne les optimisations, je saute maintenant toutes les bases qui divisent le LCM des bases déjà dans la couverture, et quand je teste l'efficacité d'une base, je la teste uniquement par rapport aux nombres jusqu'au LCM de cette nouvelle base et toutes les bases que j'ai déjà avoir.
la source