Klasse für große Zahlen - Erst mal dynamisches Array
-
Hallo!
Ich möchte eine Klasse für (unendlich) große Zahlen implementieren, und will dabei nicht std::vector oder ähnlich verwenden, sondern das dynamsiche Array selbst basteln.
Mein Problem: Was ist wenn ich nun ein Element vorne dranhängen/wegnehmen möchte (sprich ich multipliziere das ganze mit bsp. 255 und bekomme dann ein neues byte vorne (es soll ein uchar array werden) ).
Eine Idee wäre es zu machen wie realloc() von C: Ich kopiere das komplette Array in ein Temp-Array, alloziere Speicher für ein Array mit einem zusätzlichen Byte und schreib dann das Temp-Array in das größere Array, lösche dann das alte. Nur ist das nicht sehr effizient, und wenn ich häufiger Multiplikationen verwenden will, wirds happig (Beispiel: Exponenten benutzen, sprich pow() von einem Klassenobjekt).
Also dachte ich da an eine verkettete Liste, dann kann ich einfach ein zusätzliches Element vorne hinzufügen, indem ich für den next-pointer des vordersten Elements Speicher alloziere. Problem: Das Array wäre furchtbar groß; in einem 32bit System würde ich für eine Struktur in diesem Array 5byte brauchen: 1B für den uchar, 4B für den pointer. Unpraktisch! Da ist die erste Methode noch besser!Man bedenke: Ich werde Zahlen benötigen, die eventuell mehr als 50MB oder noch mehr benötigen werden.
Gibt es Alternativen? Sonst werde ich die erste Variante benutzen.
-
Wenn du das dynamische Array selbst verwalten willst, hast du dir aber einiges vorgenommen.
Ich würde erst einmal die vorhandenen STL-Klassen verwenden (vector, list, deque) und einzeln austesten.Beim vector kannst du mit resize(x) die Größe vorbestimmen.
Bei der Multiplikation zweier Zahlen kannst du ja im voraus abschätzen, wie groß das Resultat wird.Es kommt natürlich auch noch darauf an, wieviele große Zahlen du gleichzeitig verwalten willst (da dein System evtl. irgendwann nicht mehr 50MB als einen Speicherblock frei hat).
Mit welcher Zahlenbasis möchtest du denn arbeiten?
Weil eine Dezimal-Ziffer pro Byte wären ziemliche Speicherverschwendung.
Dann würde ich dir empfehlen die Zahlen als BCD zu speichern (also 2 Dezimalzahlen pro Byte).
Evtl. könntest du für BCD direkt die Assembler-Opcodes benutzen (falls du Assembler beherrschst).
-
Also ich brauch die Zahlen nicht zur Ausgabe, also werde ich das 256-System verwenden.
Wie ich die Speicherverwaltung anstelle hab ich eigentlich schon im Kopf. Bei operator- ist es eigentlich nicht notwendig, und da ich bei operator+ maximal ein zusätzliches byte brauche, nehm ich einfach generell ein Objekt mit einem byte mehr als als den größeren der beiden Summanden und lösch dann das eventuelle Null-byte. operator* ist dann ein wiederholtes operator+. operator/ dann wie in der Grundschule: Wie oft geht x in y rein ?
So, alle Grundrechenarten drin. Nicht unbedingt perfekt effizient, aber fürs erste solls genügen.Ach ja, die Idee mit realloc ist unnötig
Ich werde niemals ein leeres byte vorne anfügen müssen... (ist mir gerade eingefallen )Danke für die Antwort!
(Und sorry für den unnötigen Thread...)
-
Ach ja: Was ist BCD?
(Nein, ich beherrsche leider keinen Assembler... )Und wenn es dich interessiert, wofür ich das brauch: Ich will ein kleines Programm zur Verschlüsselung benutzen.
Hm.. Dabei hab ich eine ganz gute Formel ausgedacht, nur braucht die einen Schlüssel, der mindestens 1byte größer ist als die Hälfte der zu verschlüsselnden Datei. ._. das kann lustig werden...