Zeit-Speicher-Kompromiss

Ich habe ein neues Update. Ich habe die Ingenieurabteilung der NASA kontaktiert und herausgefunden, dass der neue Rover dieselbe Speicherplattform verwendet, die auch bei Curiosity zum Einsatz kam. Der Curiosity-Rover war mit zwei Computern ausgestattet, aber nur einer war jeweils aktiv und hatte folgende Spezifikationen: Zwei Gigabyte Flash-Speicher, 256 Megabyte Arbeitsspeicher und 256 Kilobyte Read-Only-Memory, das Kernsystemroutinen beherbergte. Wir möchten in der Lage sein, unser gesamtes Programm im RAM zu speichern. Da wir aber diesen Speicherplatz mit anderen Programmen teilen müssen, wird uns maximal 5% des RAMs zugewiesen, was das Maximum ist, das wir nutzen können. Das sind insgesamt etwa 12,8 Megabyte. Ich bringe das zur Sprache, weil ich die Idee des Zeit-Speicher-Kompromiss oder Zeit-Speicher-Ausgleichs vorstellen möchte, ein in der Informatik häufig verwendeter Begriff. Ich habe mir ein Programm von IV42 angesehen, und sie hatten ein Millionen-Primzahlen-Array, damit ihr Algorithmus soweit wie möglich nur über Primzahlen schreiten konnte, wenn er einen Primzahlentest durch Division ausführte. Es stellt sich die Frage, warum wir nicht einfach alle benötigten Primzahlen bis zu einer bestimmten Grenze in einem Array speichern, anstatt sie ad hoc zu berechnen? Wir erwähnten in einem vorherigen Video, dass dies für einen Algorithmus zur Division optimal wäre. Obwohl man sehen kann, dass sein Algorithmus nicht viele Schritte verwendet, begann er sehr langsam zu laufen und stürzte schließlich ab, bevor er die Schrittbegrenzung erreichte. Also konnte er das Problem für die von mir früher definierten Größen nicht schnell lösen. In diesem Fall tauschten sie Zeit in Form von wiederholten Teilbarkeitstests gegen Speicherplatz ein, was den Speicherplatz zur Aufbewahrung des Arrays bedeutet. Aber warum hat das nicht funktioniert? Nun, lass uns eine grobe Rechnung machen, um herauszufinden, ob diese Methode unter Berücksichtigung unserer Speicherbegrenzung möglich ist. Denke daran, dass wir mit Zahlen umgehen können müssen, die über 9 Billiarden liegen. Unsere Algorithmen zur Teilung müssen nur Faktoren bis zur Quadratwurzel einer Zahl prüfen. Und wenn sie diesen Punkt ohne Fund von Faktoren erreichen, kann sie zu 100% sagen, ob die Zahl eine Primzahl ist oder nicht. Nun, wie viele Primzahlen gibt es bis zur Quadratwurzel dieser Grenze, wobei die Quadratwurzel von 9 Billiarden 94,9 Millionen ist? Wie viele Primzahlen unter 95 Millionen? Glücklicherweise haben wir eine mathematische Lösung gelernt, um uns dieser Antwort zu nähern, nämlich den Primzahlsatz. Also, wie viele Primzahlen gibt es unter x? Nun, es ist x geteilt durch den natürlichen Logarithmus von x. Und wenn x gerade über 94,9 Millionen liegt, finden wir, dass die Anzahl der Primzahlen etwa 5,1 Millionen beträgt. Da wir diese Primzahlen speichern, müssen wir die Größe der größten Primzahl kennen, in diesem Fall die etwa 5,1-millionste Primzahl, von der wir wissen, dass sie eine Zahl kleiner als 94,9 Millionen sein wird. Ich habe die Tabelle noch einmal überprüft, und der tatsächliche Wert dieser Primzahl, die größte Primzahl, die wir unter der Quadratwurzel unserer Grenze speichern müssen, beträgt 89'078'611. Wie viel Speicher benötigt diese einzelne große Primzahl? Nun, um das herauszufinden, konvertieren wir die Zahl in Binärcode, was die Art und Weise ist, wie der Computer die Zahl mithilfe kleiner Schalter im Speicher speichern wird. Wir haben dies im Video über den Computerspeicher gelernt. In Bits sieht die größte Primzahl so aus, was 24 Bits oder 3 Bytes bedeutet, die benötigt werden, um diese einzelne Zahl zu speichern. Nehmen wir an, wir wollen jede Zahl im Speicher speichern. Da wir wissen, dass die größte Zahl 24 Bits benötigt, können wir uns einfach eine lange Liste von 24-Bit-Blöcken vorstellen, die jede Primzahl speichern. Wie viele Bits werden für diese gesamte Liste benötigt? Nun, der benötigte Speicher ist die Anzahl der Werte, also die Anzahl der Primzahlen, multipliziert mit dem Speicherplatz pro Wert. Also haben wir rund 5,1 Millionen Werte mal 24 Bits pro Wert, was gerade über 124 Millionen Bits oder, wenn wir es in Bytes umrechnen, etwa 14,7 Millionen Bytes ergibt. Nennen wir das fast 15 Megabyte. Es ist also nicht möglich, selbst eine Liste dieser Zahlen im Speicher mit unserer Begrenzung zu speichern. Dies ist nur ein Beispiel. Es ist tatsächlich eine Unterschätzung dessen, was man wirklich brauchen würde. Zum Beispiel benötigt ein Array Speicherplatz für einen Zeiger auf jedes Element. Und jeder Zeiger auf einer 32-Bit-Maschine ist 4 Byte groß. Daher ist die tatsächlich benötigte Speichermenge viel größer als 15 Megabyte. Wir wissen also, dass es nicht einmal möglich ist, alle Primzahlen bis zur Quadratwurzel unserer relativ kleinen Grenze mit unserer Speicherbegrenzung zu speichern. Wir können es auf diese Weise nicht tun. Nun, was ist, wenn die Preise um einen Faktor von tausend oder zehntausend fallen? Moderne kryptographische Systeme verwenden 512 Bit oder sogar größere Zahlen, was eine Suche und Aufzählung unmöglich macht. Wenn nun jemand dich bittet, eine Liste aller Primzahlen zu erstellen, die 200 Ziffer lang sind, solltest du das nicht einmal in Betracht ziehen, da die Festplatte, die benötigt wird, um all diese Primzahlen zu speichern, schwerer wäre als die Masse des beobachtbaren Universums. Du kannst es ja mal berechnen, wenn du das nächste Mal in einem Restaurant oder so bist. Aber denke daran, es gibt ungefähr 10 hoch 80 Atome im beobachtbaren Universum. Das ist eine 80-stellige Zahl. Du musst begreifen, dass es eine grundlegende Begrenzung dafür gibt, wie viel Platz oder Speicher wir zur Verfügung haben. Mal abgesehen davon, wie viel Zeit es dauern würde, gibt es immer diesen Druck und Zug zwischen der Verwendung von Platz oder Zeit, um unsere Probleme zu lösen. Um dieses Problem des Primzahltests schnell mit wenig Platz und wenig Zeit zu lösen, werden wir es auf eine völlig neue Weise angehen müssen.