3. Klasse entwerfen für beliebig große ganze Zahlen

Klasse entwerfen für beliebig große ganze Zahlen

  • S

    Ich dachte mir ich versuche mich mal an solch einer Klasse, allerdings bin ich
    am überlegen was alles nötig ist.
    Zum speichern der Zahl dachte ich an ein Array aus Zeichen, nun stellt sich mir
    die Frage ob ich einen Vector oder einen String verwenden soll. Was denkt ihr?

    Wie sieht es mit dem rechnen intern aus, wenn ich so rechne als würde ich es auf
    dem papier tun (im Dezimalsystem), z.B. 14+18:
    4+8 = 12, 2 übertrag 1
    1+1+1 = 3 übertrag 0
    => 32

    Das würde ja bei jeder Zahl, egal wie groß funktionieren, setzt das jetzt vorraus
    dass ich nur Dezimalzahlen speichern kann? Ich würde sagen, nein bin mir
    allerdings nicht ganz sicher.

    Wie sieht es mit den Operatoren aus, welche sollte Sie unterstützen könnem?
    Ich dachte an:
    ++

    -/+ (Unär)
    *
    /
    %

    Als Kostruktoren:
    ctor (long signed int i);
    ctor (long unsigned int i);
    ctor (andere große Zahl);

    Fehlt da noch was, oder würde das reichen?
    Trigonometrie,Potenzen,Wurzeln,Logarithmen,... werde ich wohl nicht implementieren
    bzw. nicht gleich.

    Achja ob die Zahl positiv oder negativ ist, speicher ich einfach in einem unsigned
    Integer, wobei 0x00000000 negativ ist und 0xFFFFFFFF positiv ist.
    Oder wäre da was anderes besser?

    0
  • ?

    Naja ich würde vector<bool> zum speichern verwenden. Das sign bit in einem seperaten bool speichern. Und als operatoren würde ich +, - vergleiche und eventuel * und /.

    0
  • ?

    Entweder mein Post wurde gelöscht, oder das Board ist abgekackt. Beides werde ich mir nicht bieten lassen. 😉

    Ok, also nochmal in Kürze:
    Falls du die einzelnen Bits repräsentieren willst, würde ich die 2er-Komplement Darstellung verwenden.

    Amsonsten empfehle ich dir auch einfach mal, von Profis abzugucken. In der entsprechenden Java-Klasse werden int-Arrays verwendet, ich hab jetzt aber mir nicht angeschaut, wie die Funktionsweise da ist. Schau dir einfach mal den Sourcecode dazu an, die haben das bestimmt nicht auf die schlechtest mögliche Weise gelöst.
    http://java.sun.com/j2se/1.4/docs/api/java/math/BigInteger.html

    0
  • S

    Konnte Gestern leider nicht mehr antworten, da das bord nicht mehr zu erreichen war.
    Wie soll ich die Daten denn mit vector <bool> speichern? Da kann ich ja nur 0 und 1
    wählen, ich brauche aber für die zahlen 0-9 4Bits.

    Ich werde mir mal diese Klasse anschauen und hoffen dass ich verstehe was die da machen *g*

    0
  • B

    speicher deine zahl einfach binär in einem vector<bool>, rechnen kannst du damit dann wie du es schon angesprochen hast.

    zB:
    10010101
    +01000001
    =11010110

    evtl. ist auch std::bitset das was du suchst.

    0
  • S

    Ich dachte eigentlich an Integer, weil 32Bit CPUs mit 32Bit doch am schnellsten
    rechnen können, oder?

    Ok nehmen wir an ich speicher die Zahl als Bitfolge, dann habe ich 4Bits pro Ziffer,
    ist soweit ja kein Problem, allerdings müsst ich für jede zahl eine Konvertierungsroutine
    aufrufen.
    Wenn der Benutzer das Objekt mit 149 als Konstruktorargument aufruft, dann muss
    ich die 149 ja erstmal in das interne Format konvertieren, ebenso jede andere
    Ziffer die eingegeben wird. Bei den Integern müsst ich die nur in ein Array aus
    Ziffern aufspalten.

    0
  • ?

    Ne, wenn du das schon als Bitfolge abspeicherst, dann auch richtig und nicht einzelne Dezimalziffern als Bitfolge.
    Komplizierter geht es ja gar nicht mehr. 🤡

    0
  • S

    Wie das anderst gehen soll weiß ich aber nicht, wie mache ich das denn?

    0
  • ?

    Na Zahlen halt im Binärsystem darstellen. Wenn du negative Zahlen haben willst, am besten im 2er Komplement. Bloß nicht versuchen, einzelne Dezimalziffern auf diese Weise nachzubilden.
    Aber wie gesagt, ich würde mir erstmal anschauen, wie die Java-Typen das bei BigInteger gemacht haben. Ich glaube irgendwie nicht, dass die die Zahlen im Binärsystem verwalten.

    0
  • S

    Ich seh da leider nur die Dokumentation der Schnittstelle, vllt. übersehe ich
    ja aber auch nur die Implementation.

    0
  • ?

    Die Quellcodes des Java-API findest du in der Datei Src.zip.
    Falls du kein Java SDK installiert hast, musst du dir jetzt die Frage stellen ob sich das jetzt deswegen lohnt, wenn du sonst kein Java coden willst. Vielleicht findest du den Source auch so im Internet.
    Vielleicht findest du im Internet auch eine andere geeignete Klasse als Anhaltspunkt.

    EDIT: Ich kann dir den Source von BigInteger auch per eMail schicken.

    0
  • S

    Ich hab das Java SDK installiert, habe die Datei auch schon gefunden, dann werd
    ich mir die mal durchschauen (wird bei 3000 Zeilen aber etwas dauern), ich melde
    mich danach dann wieder 🙂

    0
  • V

    SirLant schrieb:

    Wie sieht es mit den Operatoren aus, welche sollte Sie unterstützen könnem?
    Ich dachte an:
    ++

    -/+ (Unär)
    *
    /
    %

    jo. ++ und -- nur als prefixversion.

    SirLant schrieb:

    Als Kostruktoren:
    ctor (long signed int i);
    ctor (long unsigned int i);
    ctor (andere große Zahl);

    evtl noch nen

    template<class ITERATOR>
ctor(ITERATOR begin,ITERATOR end);//typeof(*begin)==char

    um aus langen strings und vor allem aus dateien direkt lesen zu können.

    SirLant schrieb:

    Fehlt da noch was, oder würde das reichen?
    Trigonometrie,Potenzen,Wurzeln,Logarithmen,... werde ich wohl nicht implementieren
    bzw. nicht gleich.

    mit + - * / % kann man fein arbeiten. für performance kanns aber fein sein, nicht nur die offensichtlichen

    Langzahl operator+(Langzahl const&a,Langzahl const&b)

    zu bauen, sondern lieber

    void plus(Langzahl& ergebnis,Langzahl const&a,Langzahl const&b)

    .
    ist halt gefählicher, wegen überraschung bei plus(x,x,y), aber manchmal schneller.
    Potenzen, Wurzeln und so müssen nicht member/friend sein, da sie intern wohl mit + - * / % gebaut werden. evtl müssen dann << und >> oder so noch als members/friend gebaut werden, aber das verschiebe ruhig, bis echt bedarf ist. mach nur das notwendigste gleich.

    0
  • S

    Ok danke 🙂

    Wenn ich den Aufbau von der BigInteger Klasse richtig verstehe, haben die ein
    Array (int[] mag) in welchem die einzelnen Ziffern stehen.
    Die arbeiten da aber recht viel low level, ist im mom noch etwas zu hoch für mich 😞

    0
  • W

    Also ich würde auf keinen Fall, wie hier vorgeschlagen, das ganze durch ein Bitset realisieren, da das die Performance in den Keller reißt, sondern mit ganzen DWORDs arbeiten.

    0
  • E

    Hallo,

    mein Brüderchen hat sowas auch schonmal programmiert, und ich seinen Code schonmal gepostet. Hier ein Link zu dem Thread mit dem Code, fals du da mal reinschauen willst. Ist aber glaub auch etwas Hardware nahes dabei.

    http://www.c-plusplus.net/forum/viewtopic.php?p=415318&highlight=bruder#415318

    Der Quellcode zum Linux bc müsste ja auch zu bekommen sein, die haben sowas bestimmt auch ziehmlich performant gemacht.

    0
Anmelden zum Antworten