If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

Algorithmische Effizienz

Wie können wir die Geschwindigkeit eines (deterministischen) Primzahltests verbessern? Erstellt von Brit Cruise

Willst du an der Diskussion teilnehmen?

Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.

Video-Transkript

Sprecher: Mir wurde gerade berichtet, dass sie einen neuen Rover zum Mars schicken. Wir sind verantwortlich für eine Aufgabe, und zwar das Programmieren des Algorithmus im Inneren des Rovers, der prüft, ob Zahlen Primzahlen sind. Nehmen wir an, unser Rover kommuniziert mittels RSA. Er benötigt einen internen Algorithmus, der einen Primzahlentest durchführen kann. Wenn man einen Rover oder irgendetwas für den Weltraum entwirft, muss man in jeder Hinsicht sehr effizient sein. Die verwendeten Komponenten müssen sehr leicht sein. Die Menge an Energie, die jedes Teilsystem verbraucht, muss minimal sein. Man muss an jeder Stelle im Designprozess Energie und Masse sparen. Wir haben unsere Arbeit vor uns. Wir müssen in der Lage sein, mit Zahlen dieser Größe umzugehen. Er muss das sehr schnell tun können. Wenn wir ihm eine sehr kleine Eingabe geben, sagen wir einfach 90, sollte er das fast genauso schnell berechnen können wie diese ganze Zahl. Wenn die Zahl grösser wird, wollen wir keine merkliche Verlangsamung sehen. Ich möchte die Fragen oder die Ideen, der Benutzer, die aus mathematischer Sicht wirklich gut waren, analysieren. Wir überprüfen, ob N eine Primzahl oder zusammengesetzt ist. Gegeben irgendeine Zahl N, betrachte diesen Raum aller möglichen Ns. Wenn N 100 ist, ist dieser Raum zwei hoch 100. Was unser Algorithmus tut, ist diesen Raum zu durchsuchen. Denke an einen Algorithmus, der einen Raum durchsucht. An jedem Punkt stellt er eine Frage - Betrachte dies als einen Schritt, einen primitiven Schritt. Er stellt eine Frage und es ist tatsächlich ein Kompositionstest, die Frage. Angenommen, dies ist eine Zahl A, wir würden bei der Probedivisionsmethode fragen "Ist N durch A teilbar?" Wir versuchen dies einfach, wir lassen A hier fallen und versuchen N teilt A und wir sehen, ob der Rest null ist, was bedeutet, A ist ein Teiler von N, wir sagen "Ah, wir wissen 100 Prozent-" Wir hissen die Flagge und wissen 100 Prozent sicher, dass es zusammengesetzt ist. Ansonsten sind wir uns an jedem Schritt nicht ganz sicher. Es könnte eine Primzahl sein, aber wir sind uns nicht sicher. Wir setzen die Suche fort, bis wir das Ende erreichen. Erinnere dich, unsere Wand in diesem Fall war bei der Quadratwurzel von N. Die schlimmste Situation tritt auf, wenn N eine Primzahl ist, wir suchen bis zur Quadratwurzel von N und dann können wir sagen "Ah, es ist eine Primzahl "und wir sind 100 Prozent sicher." Im Falle, dass N das Vielfache von zwei Primzahlen ist, sieben mal sieben gleich 49, wenn wir 49 in unseren Algorithmus eingeben, tritt der schlimmste Fall auf. Wir gehen bis zur Quadratwurzel von N. Die erste Reihe von Fragen, zum Beispiel TheFourthDimension fragt: "Sobald wir zwei Möglichkeiten "als nicht teilbar ausschließen, alle Vielfachen von Zwei" "ausgeschlossen werden könnten, dasselbe gilt für Drei, Vier, Fünf usw." Das ist ein wirklich guter Punkt. Unser alter Algorithmus ging Schritt für Schritt vor. Aber wir könnten Muster verwenden, die wir über zusammengesetzte Zahlen kennen, zum Beispiel wissen wir sicher, dass wenn eine Zahl durch zwei teilbar ist, sie zusammengesetzt ist. Wenn sie größer als zwei ist, so ist zwei eine Primzahl, dann können wir sagen, dass vier zusammengesetzt ist. Die Fünf habe ich hier übersehen, das tut mir leid. Vier, sechs, acht, 10, und stattdessen können wir so vorgehen. Drei, fünf, sieben, neun. Es gibt verschiedene Arten von Fragen, die alle versuchen, diesen Raum zu reduzieren. Wenn wir alle geraden Zahlen eliminieren, dann beträgt der Prüfraum, statt bis zur Quadratwurzel von N zu gehen, nur die Hälfte der Quadratwurzel von N. Wir können weitere Muster in zusammengesetzten Zahlen finden, um diesen noch kleiner zu machen. Eine andere Art von Frage betrifft den Fall, in dem wir einen zusammengesetzten Zeugen finden, das heißt, wir finden ein A, das uns erlaubt zu sagen: "Oh, wir wissen, N ist zusammengesetzt." Lola stellte die Frage: "Würde es nicht Zeit sparen, die Schleife zu verlassen, sobald primeCheck false ergibt?" Ja, das ist völlig korrekt und etwas, was wir tun wollen. Sobald wir eine Suche durchführen, die durch irgendein Muster definiert ist, und wir finden einen zusammengesetzten Zeugen, dann bedeutet das, dass es unseren Test besteht und wir mit 100-prozentiger Sicherheit frühzeitig stoppen sollten. Wir hören auf und sagen: "Oh, wir sind fertig. Wir suchen nicht weiter." Dieses frühe Stoppen ist großartig, hilft uns aber nicht im schlimmsten Fall, nämlich wenn N eine Primzahl ist. Dann hilft das frühe Stoppen uns nicht. Wir können visualisieren, wie diese Verbesserungen es uns ermöglichen, den Raum zu reduzieren und somit weniger Überprüfungen im Computer durchzuführen, die, je nach Computer, die benötigte Zeit reduziert. Nun kann ich dir die Darstellung unten zeigen, welche es uns erlaubt, zwei Algorithmen basierend auf der Anzahl der Schritte ihrer Ausführung zu vergleichen. Auf der linken Seite ist Algorithmus A, der durch Probedivision von zwei bis zur Quadratwurzel von N, überprüft. Auf der rechten Seite ist Algorithmus B, sagen wir, unser verbesserter Algorithmus. In diesem Fall habe ich die Überprüfung, ob durch zwei teilbar ist, angewendet, so dass wir nur halb so viele Schritte durchführen. Ich breche in diesem Algorithmus B auch frühzeitig ab. Es ist nicht perfekt, ich habe nur ein paar Benutzeranpassungen vorgenommen, damit wir sehen können, was passiert. Ich werde jetzt damit spielen, um es dir zu zeigen. Wie wir sehen können, wenn ich scrolle, sehen wir Algorithmus A. Wir haben das Ergebnis, ob es zusammengesetzt oder eine Primzahl ist. Am unteren Rand siehst du die Anzahl der Schritte. Das Erste, was auffällt, ist, dass auf der rechten Seite jede zweite Zahl nur einen Schritt benötigt. Wir wissen warum. Wenn es eine gerade Zahl ist, wie diese hier, dann wird sie aufhören. Unser alter Algorithmus brauchte 314 Schritte. Unser neuer Algorithmus brauchte nur einen Schritt, weil er überprüft, ob es durch zwei teilbar ist. Das scheint eine wirklich schöne Optimierung zu sein. Allerdings wirst du feststellen, dass die Anzahl Schritte zunimmt und die Leiste rot und größer wird, sobald wir uns dem Bereich nähern, in dem wir abstürzen werden. Diese rote Linie hier oben ist die Schrittbegrenzung. Wenn dein Balken dort anstößt, scheitern wir, was bedeutet, dass unser Rover kaputt gehen würde. In diesem Fall wird der Browser tatsächlich abstürzen. Ich versuche, mich dem anzunähern. Ich bin ihm jetzt nahe und es läuft sehr langsam. Ich kann spüren, dass mein Browser kurz davor ist abzustürzen und mich in den Kreislauf des Todes führt. Beachte, dass der verbesserte Algorithmus nur zwei Schritte gebraucht hat aber denke an den schlimmsten Fall. Ich werde... ich habe hier ein paar große Primzahlen gespeichert, zum Beispiel. Wir müssen in der Lage sein, jeden Fall zu bewältigen. Wir wissen nicht, was wir unserem Algorithmus übergeben Wenn ich eine große Primzahl darauf anwende, schau, was passiert. Algorithmus B, wie wir wissen, macht in dem schlimmsten Fall nur halb so viele Schritte, aber er macht hier immer noch viele Schritte, weil es der schlimmste Fall ist, richtig? Wir nähern uns hier dem Absturz, und das ist keine sehr lange Primzahl. Wir sind immer noch weit unter 15 Ziffern. Wenn ich diese 12-stellige Primzahl in unseren Algorithmus eingebe, mal sehen, was passiert. Er verzögert sich, er wird abstürzen. Schau, was passiert ist, beide Algorithmen sind weit über das Ziel hinausgeschossen. Es hat nicht funktioniert. Unser Verbesserungsalgorithmus ist noch nicht gut genug. Aber jetzt haben wir ein Verständnis dafür, was wir verbessern wollen, nämlich die Anzahl der Schritte im schlimmsten Fall. Und wir haben dieses coole Werkzeug, das uns erlaubt zu visualisieren, wie schnell es wächst, wie schnell die Anzahl der Schritte wächst, wenn unsere Eingabe wächst. Weiter unten werde ich erklären, wie ich das eingerichtet habe, damit du deinen Algorithmus einrichten kannst und ihn mit dem Basisfall vergleichen können, und sehen, wie viel besser du sein kannst.