Minimale Abdeckung der Basen für die quadratische Rückstandsprüfung der Rechtwinkligkeit

11

Herausforderung

Finden Sie die kleinste Abdeckung von Basen (z. B. Modulen), deren quadratische Restmengen über eine Tabellensuche getestet werden können, um definitiv zu bestimmen, ob eine gegebene nicht negative ganze Zahl n ein perfektes Quadrat ist oder nicht . Die Basen müssen alle kleiner oder gleich der Quadratwurzel des Maximalwerts von n sein .

Die Antwort mit dem kleinsten Satz von Basen für eine gegebene Kategorie von n gewinnt die Herausforderung. (Dies bedeutet, dass es möglicherweise mehr als einen Gewinner gibt.) Die Kategorien von n sind:

         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

Im Falle eines Gleichstands mit zwei Sätzen mit gleicher Kardinalität geht der Gleichstand zu dem Satz mit der größeren Fähigkeit, Nichtquadrate früher in der Sequenz zu erkennen.

Für den Fall, dass keine vollständigen Abdeckungen gefunden werden (was für die 32-Bit- und 64-Bit-Kategorien durchaus wahrscheinlich ist), ist der Gewinner der Satz von Basen, der statistisch oder nachweislich den höchsten Prozentsatz an Nicht-Quadraten ausschließt (ohne falsch Quadrate als Nichtquadrate melden). Im Folgenden finden Sie eine Erläuterung unvollständiger Abdeckungen.

Hintergrund

In vielen Anwendungen der Zahlentheorie stellt sich die Frage, ob eine Zahl n ein perfektes Quadrat ist oder nicht (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 usw.). Eine Möglichkeit , zu prüfen , ob n quadratisch ist zu prüfen , ob Boden (√n) ² = n, das heißt, ob die abgerundeten-down Quadratwurzel n , wenn quadriert, gibt zurück n . Zum Beispiel ist Boden (√123) ² = 11² = 121, was nicht 123 ist, also ist 123 nicht quadratisch; aber Boden (√121) ² = 11² = 121, also ist 121 quadratisch. Diese Methode funktioniert gut für kleine Zahlen, insbesondere wenn eine Hardware-Quadratwurzeloperation verfügbar ist. Bei großen Zahlen (Hunderte oder Tausende von Bits) kann dies jedoch sehr langsam sein.

Eine andere Möglichkeit, die Rechtwinkligkeit zu testen, besteht darin, Nichtquadrate mithilfe quadratischer Resttabellen auszuschließen. Zum Beispiel müssen alle Quadrate in Basis 10 eine letzte Ziffer (Einstellen) haben, die entweder 0, 1, 4, 5, 6 oder 9 ist. Diese Werte bilden die Menge der quadratischen Reste für Basis 10. Wenn also eine Basis -10 Anzahl Ende in 0, 1, 4, 5, 6 oder 9, wissen Sie , dass es vielleicht quadratisch sein und eine weitere Prüfung erforderlich. Wenn eine Basis-10-Zahl jedoch mit 2, 3, 7 oder 8 endet, können Sie sicher sein, dass sie nicht quadratisch ist.

Schauen wir uns also eine andere Basis an. Alle Quadrate in Basis 8 müssen mit 0, 1 oder 4 enden, was zweckmäßigerweise nur 3 von 8 Möglichkeiten ist, was eine 37,5% ige Chance bedeutet, dass eine Zufallszahl möglicherweise quadratisch ist, oder eine 62,5% ige Chance, dass eine Zufallszahl definitiv nicht quadratisch ist. Das sind viel bessere Chancen als die Basis 10. (Und beachten Sie, dass eine Operation mit dem Basis-8-Modul einfach eine logische Operation ist, im Gegensatz zum Basis-10-Modul, der mit dem Rest durch 10 geteilt wird.)

Gibt es noch bessere Basen? Na ja, eigentlich. Die Basis 120 bietet 18 Möglichkeiten (0, 1, 4, 9, 16, 24, 25, 36, 40, 49, 60, 64, 76, 81, 84, 96, 100 und 105), was nur 15% entspricht. Chance, möglicherweise quadratisch zu sein. Und Basis 240 ist noch besser, mit nur 24 Möglichkeiten, was nur eine 10% ige Chance darstellt, möglicherweise quadratisch zu sein.

Aber keine einzelne Basis allein kann die Rechtwinkligkeit definitiv bestimmen (es sei denn, sie ist größer als die maximal getestete Anzahl, was äußerst unpraktisch ist). Eine einzige Basis allein kann nur ausschließen Rechtwinkligkeit; es kann die Rechtwinkligkeit nicht endgültig überprüfen . Nur ein sorgfältig ausgewählter Satz von Basen, die zusammenarbeiten, kann die Rechtwinkligkeit über einen Bereich von ganzen Zahlen endgültig überprüfen.

Die Frage lautet also: Welche Basen bilden eine minimale Abdeckung, die zusammen den endgültigen Abzug von Rechtwinkligkeit oder Nicht-Rechtwinkligkeit ermöglichen?

Beispiel für eine korrekte, aber nicht minimale Abdeckung

Die Abdeckung mit 16 Basen {3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 29, 31, 37} reicht aus, um die Rechtwinkligkeit oder Nicht-Rechtwinkligkeit von definitiv zu bestimmen alle 16-Bit-Werte 0 bis 65535. Es handelt sich jedoch nicht um eine minimale Abdeckung, da mindestens eine 15-Basis-Abdeckung vorhanden ist, die ebenfalls leicht erkennbar ist. In der Tat ist es wahrscheinlich, dass weitaus kleinere Abdeckungen existieren - vielleicht mit nur 6 oder 7 Basen.

Zur Veranschaulichung werfen wir einen Blick auf das Testen eines Beispielwerts von n mit diesem 16-Basis-Abdeckungssatz. Hier sind die Sätze quadratischer Reste für den obigen Satz von Basen:

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}

Testen wir nun die Zahl n = 50401 mit diesem Satz von Basen, indem wir sie in jede Basis umwandeln. (Dies ist nicht die effizienteste Methode, um Rückstände zu untersuchen, aber es reicht zu Erklärungszwecken aus.) Es ist die Stelle der 1, an der wir hier interessiert sind (unten in Klammern angegeben):

 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 ) ✓

Wir können also sehen, dass in 13 dieser Basen der Rest mit einem bekannten quadratischen Rest übereinstimmt (in der Tabelle als "Treffer" bezeichnet), und in 3 dieser Basen stimmt der Rest nicht mit einem bekannten quadratischen Rest überein (nennen Sie dies a "Fräulein"). Alles was es braucht ist 1 Fehler, um zu wissen, dass eine Zahl nicht quadratisch ist, also könnten wir bei 11 anhalten, aber zur Veranschaulichung haben wir alle 16 Basen hier untersucht.

Beispiel einer unvollständigen Deckung

Technisch gesehen ist ein unvollständiges Cover kein Cover, aber das ist nebensächlich. Die Menge der Basen {7, 8, 11, 15} deckt fast alle 8-Bit-Werte von n von 0 bis 255 korrekt ab, aber nicht ganz. Insbesondere werden 60 und 240 fälschlicherweise als quadratisch identifiziert (dies sind falsch positive Ergebnisse) - es werden jedoch alle tatsächlichen Quadrate (0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 8) korrekt identifiziert. 100, 121, 144, 169, 196 und 225) und macht keine anderen falsch positiven Ergebnisse. Dies ist also ein 4er-Set, das als Lösung fast erfolgreich ist, aber letztendlich fehlschlägt, weil eine unvollständige Abdeckung keine gültige Lösung ist.

Für 8-Bit n ist der Satz von Basen {7, 8, 11, 15} einer von zwei Sätzen von 4 Basen, die zwei Fehler erzeugen, und es gibt sieben Sätze von 4 Basen, die nur einen Fehler erzeugen. Es gibt tatsächlich keine Sätze von 4 Basen, die eine vollständige und genaue Abdeckung von 8-Bit-Werten bilden. Können Sie einen Satz von 5 Basen finden, die keine Fehler erzeugen und alle 8-Bit-Werte korrekt abdecken? Oder brauchst du 6 oder mehr? (Ich kenne die Antwort für 8-Bit n , aber ich werde sie nicht verraten. Ich kenne die Antwort für 16-Bit, 32-Bit oder 64-Bit nicht und ich glaube sogar die 16- Bit-Fälle können nicht mit Brute-Force-Suche gelöst werden. Das Lösen der 32-Bit- und 64-Bit-Fälle erfordert sicherlich genetische, heuristische oder andere Suchtechniken.)

Ein Kommentar zu kryptografisch großen Zahlen

Abgesehen von 64-Bit-Zahlen - bis zu Hunderten oder Tausenden von Binärziffern - ist hier eine schnelle Rechtwinkligkeitsprüfung am nützlichsten, selbst wenn das Cover unvollständig ist (was mit Sicherheit für wirklich große Zahlen der Fall sein wird). Wie könnte ein solcher Test auch dann noch nützlich sein, wenn er nicht ausreichend entscheidend ist? Stellen Sie sich vor, Sie hatten einen extrem schnellen Test auf Rechtwinkligkeit, der in 99,9% der Fälle korrekt funktionierte und in den verbleibenden 0,1% der Fälle falsch negative Ergebnisse lieferte und niemals falsch positive Ergebnisse lieferte. Mit einem solchen Test könnten Sie fast sofort feststellen, dass eine Zahl nicht rechtwinklig ist, und in Ausnahmefällen der Unentschlossenheit könnten Sie dann auf eine langsamere Methode zurückgreifen, um das Unbekannte auf andere Weise aufzulösen. Dies würde Ihnen viel Zeit sparen.

Zum Beispiel ist die Menge {8, 11, 13, 15} 99,61% der Zeit für 8-Bit-Werte von n von 0 bis 255 korrekt, 95,98% der Zeit für 16-Bit-Werte von n von 0 bis korrekt 65535 und ist in 95,62% der Fälle für 24-Bit-Werte von n von 0 bis 16777215 korrekt. Wenn n gegen unendlich geht, sinkt der Prozentsatz der Korrektheit für diesen Satz von Basen, aber er nähert sich asymptotisch und fällt nie unter 95,5944% Richtigkeit.

Selbst dieser sehr kleine Satz von 4 kleinen Basen ist nützlich, um etwa 22 von 23 willkürlich großen Zahlen fast sofort als Nichtquadrate zu identifizieren, sodass keine weitere Überprüfung dieser Zahlen mit langsameren Methoden erforderlich ist. Die langsameren Methoden müssen dann nur in wenigen Fällen angewendet werden, die durch diesen Schnelltest nicht ausgeschlossen werden konnten.

Es ist interessant festzustellen, dass einige 16-Bit-Basen allein mehr als 95% erreichen. Tatsächlich kann jede der folgenden Basen besser als 97% aller Zahlen bis unendlich als nicht quadratisch aussortieren. Der für jede dieser Basen festgelegte quadratische Rest kann als gepacktes Bit-Array mit nur 8192 Bytes dargestellt werden.

Hier sind die 10 mächtigsten Einzelbasen unter 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%

Sehen Sie etwas Interessantes, das diese Basen alle gemeinsam haben? Es gibt keinen Grund zu der Annahme, dass sie in Kombination nützlich sein könnten (vielleicht sind sie es, vielleicht sind sie es nicht), aber es gibt hier einige gute Hinweise darauf, welche Basen für die größeren Kategorien von Zahlen wahrscheinlich am einflussreichsten sind.

Nebenherausforderung: Eine der einflussreichsten Basen (wenn nicht die meisten) bis zu 2 ^ 28 ist 245044800, die allein 99,67% der Nichtquadrate oder etwa 306 von 307 darauf geworfenen Zufallszahlen korrekt aussortieren kann. Können Sie die einflussreichste Einzelbasis unter 2 ^ 32 finden?

verbunden

In den folgenden Fragen finden Sie einige sehr nette Ideen, die eng miteinander verbunden sind, sowie einige Tricks zur Mikrooptimierung, um bestimmte Vorgänge schneller zu machen. Obwohl die verknüpften Fragen nicht speziell darauf abzielen, die stärksten Basen zu finden, ist die Idee starker Basen implizit zentral für einige der dort verwendeten Optimierungstechniken.

Todd Lehman
quelle
Wie können Sie feststellen, ob der Tie-Breaker nicht jede einzelne Zahl in dem angegebenen Bereich testet und wie viele Überprüfungen insgesamt durchgeführt wurden?
Martin Ender
Ich werde die Kardinalität der Sätze quadratischer Reste für jede Basis untersuchen. Zum Beispiel ist 4 eine bessere Basis als 3, da nur die Hälfte der Werte von Modulo 4 quadratische Reste sind, während zwei Drittel der Werte von Modulo 3 quadratische Reste sind. Somit hat 4 eine größere Fähigkeit, Zahlen früher auszusortieren. Die schlechteste Basis ist 2, weil sie keine Zahl ausschließen kann, und die beste Basis unter 256 ist 240, was 90% der Zahlen ausschließen kann. Möglicherweise müssen Monte-Carlo-Proben für wirklich große Basen entnommen werden.
Todd Lehman
Ja, das macht Sinn. Aber werden Sie das Unentschieden nur anhand der ersten Basis entscheiden, deren Wahrscheinlichkeit unterschiedlich ist, oder wie werden Sie die Effizienz des gesamten Satzes anhand der Wahrscheinlichkeiten ermitteln? Ich denke auch, dass die Wahrscheinlichkeiten nicht mehr unabhängig sind, wenn Sie andere Basen überprüft haben.
Martin Ender
2
Bei großen n Räumen muss ich die Bindung auf der Grundlage der geschätzten Gesamteffizienz entscheiden, die durch Multiplikation der von jedem Restsatz vorhergesagten Wahrscheinlichkeiten berechnet wird. Beispielsweise haben die Basen {8,11,13,15} Wahrscheinlichkeiten von 0,375, 0,545455, 0,538462 bzw. 0,4, die sich mit 0,044056 multiplizieren. Subtrahiert von 1 ergibt dies 0,955944, was sehr gut mit dem erschöpfenden Zählergebnis von 95,62% übereinstimmt, gemessen über alle n in [0,2 ^ 24-1].
Todd Lehman

Antworten:

7

Mathematica

Ich weiß (leider) nicht viel über Zahlentheorie, daher ist dies ein eher naiver Ansatz. Ich verwende einen gierigen Algorithmus, der immer die Basis hinzufügt, die die meisten Fehler für die verbleibenden Zahlen aufweist.

bits = 8
Timing[
 maxN = 2^bits - 1;
 maxBase = 2^(bits/2) - 1;
 bases = {
     #,
     Union[Mod[Range[0, Floor[#/2]]^2, #]]
     } & /@ Range[3, maxBase];
 bases = SortBy[bases, Length@#[[2]]/#[[1]] &];
 numbers = {};
 For[i = 0, i <= Quotient[maxN, bases[[1, 1]]], ++i,
  AppendTo[numbers, # + i*bases[[1, 1]]] & /@ bases[[1, 2]]
  ];
 While[numbers[[-1]] > maxN, numbers = Most@numbers];
 numbers = Rest@numbers;
 i = 0;
 cover = {bases[[1, 1]]};
 lcm = cover[[-1]];
 Print@cover[[1]];
 While[Length@numbers > maxBase,
  ++i;
  bases = DeleteCases[bases, {b_, r_} /; b\[Divides]lcm];
  (*bases=SortBy[bases,(Print[{#,c=Count[numbers,n_/;MemberQ[#[[2]],
  Mod[n,#[[1]]]]]}];c)&];*)
  bases = SortBy[
    bases,
    (
      n = Cases[numbers, n_ /; n < LCM[#[[1]], lcm]];
      Count[n, n_ /; MemberQ[#[[2]], Mod[n, #[[1]]]]]/Length@n
      ) &
    ];
  {base, residues} = bases[[1]];
  numbers = Cases[numbers, n_ /; MemberQ[residues, Mod[n, base]]];
  AppendTo[cover, base];
  lcm = LCM[lcm, base];
  Print@base
  ];
 cover
 ]

Es löst 8 Bits in kürzester Zeit mit den folgenden 6 Basen:

{12, 13, 7, 11, 5, 8}

16 Bit dauert 6 Sekunden und führt zu der folgenden 6-Basis-Abdeckung:

{240, 247, 253, 119, 225, 37}

In den größeren Fällen geht diesem Ansatz offensichtlich der Speicher aus.

Um über 16 Bit hinauszugehen, muss ich einen Weg finden, um zu überprüfen, ob ein Cover vollständig ist, ohne eine Liste aller Zahlen bis zu N max zu führen (oder etwas über die Zahlentheorie zu lernen).

Bearbeiten: Reduzierte Laufzeit für 16 Bit von 66s auf 8s, indem die Liste der Zahlen nur mit denen vorab ausgefüllt wird, die von der effektivsten Basis nicht ausgeschlossen werden. Dies sollte auch den Speicherbedarf erheblich verbessern.

Bearbeiten: Ich habe zwei kleinere Optimierungen hinzugefügt, um den Suchraum zu reduzieren. Es ist keine der offiziellen Kategorien, aber damit habe ich in 9,3 Stunden eine 8-Basis-Abdeckung für 24 Bit gefunden:

{4032, 3575, 4087, 3977, 437, 899, 1961, 799}

Was die Optimierungen betrifft, überspringe ich jetzt alle Basen, die das LCM der Basen teilen, die sich bereits in der Abdeckung befinden, und wenn ich die Effizienz einer Basis teste, teste ich sie nur gegen Zahlen bis zum LCM dieser neuen Basis und aller Basen, die ich bereits habe haben.

Martin Ender
quelle
1
@ToddLehman Ich weiß nicht, ob Sie meine erste Lösung gesehen haben, bevor ich sie mit der gierigen bearbeitet habe. (Sehen Sie sich den Bearbeitungsverlauf an, wenn Sie dies nicht getan haben.) Dort habe ich nur Basen nach ihrem allgemeinen Treffer- / Fehlerverhältnis ausgewählt, bis ich ein vollständiges Cover hatte. Das ergab 8 Basen für 8 Bit und 29 Basen für 16 Bit. : D
Martin Ender
1
@ToddLehman Danke für die Tests! :) Ich frage mich, was sich Leute mit tatsächlichem Wissen über die Zahlentheorie einfallen lassen könnten. Ich habe ein paar Ideen, um es zu beschleunigen, damit ich auf 24 Bit gehen kann, aber ich denke, ich muss mich darauf konzentrieren, meine nächste Herausforderung auf den richtigen Weg zu bringen.
Martin Ender
1
@ToddLehman Es gibt ein 24-Bit-Cover für Sie. Ich habe mich bereits gefragt, ob ich die Hauptfaktoren nutzen könnte, aber ich habe mir noch keine anständige Heuristik ausgedacht. Ich könnte nur die Reihenfolge verbessern, in der die Basen getestet werden, aber ich bin mir noch nicht sicher, wann ich das abbrechen könnte.
Martin Ender
1
@ToddLehman Du musst mich nicht in meinen eigenen Posts markieren, da ich sowieso benachrichtigt werde. Aus diesem Grund deaktiviert SE die automatische Vervollständigung, bis Kommentare von mehreren Benutzern vorliegen, wobei es möglicherweise sinnvoll ist, das OP speziell anzusprechen.
Martin Ender
1
Ich habe gerade eine 9-Basis-Abdeckung für 28 Bit gefunden: {15840, 15827, 16211, 12549, 14911, 15111, 9869, 14647, 16043}. Die Laufzeit betrug 36,5 Minuten, wobei ein C-Programm verwendet wurde, das für die Bewertung der Fitness unter Verwendung gepackter bitweiser Operationen unter Verwendung eines Greedy-Algorithmus optimiert wurde. Dieses 9-Basen-Set ist eine perfekte Abdeckung für Zahlen unter 2²⁸ und eine Genauigkeit von 99,999983% für Zahlen im 2⁶⁴-Bereich.
Todd Lehman