Klassendesign einer policy-basierten Bignum-Bibliothek

Fytch

Heyho,

ich habe vor zum Spass eine Bignum-Bibliothek zu programmieren. Diese soll ein policy-basiertes Design vorweisen. Ich denke mir gerade aus, was alles in eine eigene Policy gehört. Zur Zeit schwebt mir vor:

Statischer / dynamischer Speicher
Format (binär, BCD, DPD, ...)
Algorithmus für verschiedene Operationen
unsigned / (Algorithmus für) signed

Meine aktuelle Sorge ist, dass diese Policies nicht miteinander vereinbar sind. Beispiele hierfür:

Zweierkomplement ist z.B. nicht mit BCD vereinbar
Wie soll 5 + (-2) effizient mit demselben Additionsalgorithmus berechnet werden wenn (-2) einmal im Zweierkomplement und einmal mit Vorzeichenflag abgelegt ist?
Funktionieren die gängigen arithmetischen Algorithmen (effizient), wenn sie stets nur einzelne Ziffern in einer vorgegebenen Basis von den Operanden beziehen können und das Resultat wieder ziffernweise in dieser Basis angeben müssen?

Ich möchte nicht einfach drauflos programmieren, da das dazu führen kann, dass ich alles neu machen muss, was mir die Motivation raubt. Allgemeine Anregungen erwünscht (abgesehen von "es gibt schon hunderte Bignum-Bibliotheken", denn ich mache das ja zum Spass).

Wenn du dir da mal nicht zu viel vorgenommen hast. Ich habe vor einiger Zeit auch mal eine Bignum Klasse programmiert bei der man den zugrundeliegenden Datentyp als Templateparameter wählen konnte. Das war schon genug Arbeit, vor allem der Divisionsalgorithmus hat es in sich und ich musste den nachschlagen, um das überhaupt lösen zu können.

BCD und DPD macht meiner Meinung nach eher wenig Sinn weil man damit überhaupt nicht vernünftig rechnen kann. Zur Darstellung ist es natürlich praktisch aber sonst eher weniger.

Wie du das mit den verschiedenen Algorithmen meinst ist mir auch nicht ganz klar. Für die Grundrechenarten macht man das ja im Grunde so wie schriftliches Rechnen in der Schule nur nicht zur Basis 10 sondern 2^32 oder sowas. Darüber hinaus gibt es dann z.B. für die Multiplikation bessere Algorithmen wie der Karazuba-Algorithmus, aber für kleine Zahlen ist die Schulmethode doch wieder schnell. Also nutzt man in der Praxis eine Kombination aus beiden Algorithmen.

Torsten Robitzki

Hallo Sebi,
das klingt spannend. Kann man das Ergebnis später auf github sehen?

Ich würde mich mal in die Rolle eines Nutzers versetzen und gucken, welche Aspekte den interessieren und wo es Kollisionen in den Anforderungen verschiedener Nutzergruppen geben könnte.

Die Größe des abbildbaren Werte-Bereichs kollidiert bestimmt mit der nötigen Rechenzeit und wäre damit bestimmt ein guter Kandidat. Ich würde diesen Werte-Bereich übrigens gerne angeben, und nicht auf welchen Datentypen das intern aufbaut.

Ob Du das intern als BCD oder als byte array Speichers, ist mir eigentlich egal. Ich gehe davon aus, dass Du das so effektiv wie möglich machst. Wobei das wahrscheinlich ein Unterschied macht, wenn man den Integer sehr häufig in Text konvertieren muss.

Ich arbeite gerade viel mit Mikrocontrollern. Es wäre doch schon, wenn ich einen Typen definieren könnte, der von 0 - 2^32-1 geht und der auf einem 4 Bit µController alle üblichen Operationen zur Verfügung stellt und auf einem 32 Bit µController die Effektivität eines ints hat.

Vielleicht wäre ein zweistufiger Ansatz hilfreich. Ein äußerer Typ nimmt die Anforderungen (relativ wenige würde ich schätzen) des Anwenders an und kombiniert die mit den Möglichkeiten der Platform und instanziiert damit einen Implementationstypen.

mfg Torsten

Torsten Robitzki schrieb:

Hallo Sebi,
das klingt spannend. Kann man das Ergebnis später auf github sehen?

Du meinst wohl asfdlol. Mein Projekt ist schon fertig, gibts aber nirgendwo zu sehen.

Torsten Robitzki schrieb:

Ich arbeite gerade viel mit Mikrocontrollern. Es wäre doch schon, wenn ich einen Typen definieren könnte, der von 0 - 2^32-1 geht und der auf einem 4 Bit µController alle üblichen Operationen zur Verfügung stellt und auf einem 32 Bit µController die Effektivität eines ints hat.

Wie wärs mit uint32_t? Jeder vernünftige Compiler sollte den auch auf Mikrocontrollern anbieten können. Außerdem wo gibts 4 Bit µCs? 8 Bit kenn ich eher als Minimum.

Torsten Robitzki

Hallo Sebi, (ich nenne einfach alle Sebi, ab und zu passt es dann

sebi707 schrieb:

Wie wärs mit uint32_t? Jeder vernünftige Compiler sollte den auch auf Mikrocontrollern anbieten können. Außerdem wo gibts 4 Bit µCs? 8 Bit kenn ich eher als Minimum.

Ach meno! Warum muss es in diesem Forum immer so eine negative Grundstimmung geben?

Nur, weil Du noch keine 4 Bit Mikrocontroller gesehen hast, bedeutet doch noch lange nicht, dass es keine gibt. Und wenn Du Dir mein Ansinnen mit 32 Bit auf 4 Bit Controller nicht vorstellen kannst, dann versuche es doch einfach mal mit 64 bit auf 8 bit Controllern.

Das Problem wird eher sein, einen C++ Compiler für einen 8-Bit controller zu finden, mit dem es Spaß macht, zu arbeiten.

Schöne Grüße,

Torsten

Wieso jetzt negative Grundstimmung? Für 32 Bit Rechnungen braucht man einfach noch keine Bignum Library. Selbst 64 Bit dürften noch von vielen Compilern, selbst auf 8 Bit Architekturen, unterstützt werden. Interessant wird es dann ab 128 Bit bis beliebig groß. Meistens gibt man den Wertebereich dann auch gar nicht mehr vor sondern es wird dynamisch soviel Speicher reserviert wie gebraucht wird (bis dann der RAM voll ist).