Hallo zusammen,
ich möchte mit ganzzahlen Werten arbeiten, die zu groß sind als dass sie in einen Standard-Datentypen „passen“.
Dazu müsste ich mir jetzt selbst einen Datentyp erstellen und auch die Rechenoperationen für den neuen Datentypen müsste ich selbst erstellen.
Kann mir jemand sagen, wo ich nachlesen kann, wie ich das am besten implementiere. Die Programmiersprache ist mir egal, möchte erst mal nur das Konzept verstehen.
Grüße
powerblue
Hi,
in Objektorientierten Programmiersprachen einfach ein neues Objekt anlegen. Dann Ein und Ausgabefunktionen implementieren und die gewünschten Operationen. Einfache Datentypen wie zB integer oder character kann man nicht neu anlegen.
Bist Du Dir sicher, dass der Longdatentyp(64 bit) mit einem Wertebereich von −9.223.372.036.854.775.808 bis 9.223.372.036.854.775.807 nicht reicht?
Hallo,
danke für die schnelle Antwort.
Das mit dem neuen Objekt ist schon klar, nur wie implementiere ich das Code-Technisch. Da hätte ich gern ein Beispiel zum nachlesen zu. Wie kann ich z. B. sinnvoll die Zahl verwalten. Wie kann ich damit umgehen, dass z. B. die Summe zweier solcher Zahlen den Zahlenbereich der Summanden verlassen. Das sind im Moment die Fragen, die mich beschäftigen.
Und ja, bin sicher dass es keinen Datentyp gibt, der ausreicht. Ist eine Aufgabe aus Projekt Euler und die Zahlen sind extra so gewählt, dass sie für Standard-Datentypen zu groß sind.
Grüße
Michael
Hi,
Du könntest innerhalb des Datentypes zB ein Array anlegen, jedes Arrayelement nimmt dann ein Bit auf. Hierbei wäre die länge fest, man könnte aber den Rest einfacher implementieren.
Oder man legt eine linkedlist an wobei das erste element das most significant bit ist.
Noch ein boolean fürs Vorzeichen?
Nun muss man sich entscheiden wie die Daten kodiert werden. zB mit Matisse und Exponent oder klassisch binär(so dass 1101 13 bedeutet).
In jedem Fall muss man sich angucken wie die Rechenoperationen auf bit ebene funktionieren. Und diese dann implementieren.
Organisatorisch könnte man das mit 2 Datentypen machen, einer wo nur die Daten drin sind und im anderen statisch die Rechenoperationen(„multiplikation(faktor, faktor)“).
Wenn in einem Objekt/Klasse muss man sich halt überlegen wie man zB bei Minus festlegt welcher der Rechte und welcher der linke Operand ist.
MFG
PS: Das habe ich mir gerade zusammen gesponnen, es gibt sicherlich elegantere Lösungen.
Hi,
danke, als erste Ideen, über die ich weiter nachdenken kann, reicht mir das. Werde es für’s erste binär und mit Listen versuchen.
Grüße
powerblue
Hi,
im nachhinein wäre es besser das nicht auf bit ebene runter zu brechen sondern immer eine einstellige Dezimalzahl zu verwenden, das macht vor allem die spätere Ausgabe einfacher!!
Dezimal: 3578
Wert[0]=3
Wert[1]=5
Wert[2]=7
Wert[3]=8
MFG
Hallo Michael,
Das mit dem neuen Objekt ist schon klar, nur wie implementiere
ich das Code-Technisch. Da hätte ich gern ein Beispiel zum
nachlesen zu. Wie kann ich z. B. sinnvoll die Zahl verwalten.
Wie kann ich damit umgehen, dass z. B. die Summe zweier
solcher Zahlen den Zahlenbereich der Summanden verlassen. Das
sind im Moment die Fragen, die mich beschäftigen.
Du baust das auf, wie du z.B. auch ganz normal dezimal rechnest.
Die Zahl 12310 entspricht eigentlich
1x100 + 2x10 + 3
In deinem Fall würde ich an Stelle von Zehnerpotenzen die Potenz des zewitgrössten Interger-Typs verwenden.
Wenn also deine Programmiersprache mit 64-Bit rechnen kann, nimmst du 32-Bit Werte.
Dann ergibt sich die Zahl zu
a3x264 + a2x232 + a1
Eine addition ergibt dann folgenden Pseudocode:
a3,a2,a1 Datentyp32Bit;
b3,b2,b1 Datentyp32Bit;
c3,c2,c1 Datentyp32Bit;
temp Datentyp64Bit;
temp = a1 + b1;
c1 = temp modulo 2<sup>32</sup>;
temp = temp / 2<sup>32</sup>;
temp = temp + a2 + b2;
c2 = temp modulo 2<sup>32</sup>;
temp = temp / 2<sup>32</sup>;
temp = temp + a3 + b3;
c3 = temp modulo 2<sup>32</sup>;
temp = temp / 2<sup>32</sup>;
Wenn temp am Ende 0 ist hast du einen Überlauf.
MfG Peter(TOO)
Naja,
ein bisschen mehr geht schon. In einen 32Bit Integer passen mehr als 4*10^9 rein, also kann man 10^4 als Basis wählen. Dann ist auch die Ausgabe einfacher, als wenn man eine 2-er Potenz als Basis wählt.
Java hat einen Typ BigInteger, unter C und C++ gibt es das gmp-Projekt.
Karatsuba-Multiplikation, Toom-Cook-Multiplikation, Lehmer’s Euklid-Algorithmus und weitere sind optimalere als die naiven Verfahren in diesem Kontext.
Gruß, Lutz
Hallo zusammen,
ich möchte mit ganzzahlen Werten arbeiten, die zu groß sind
als dass sie in einen Standard-Datentypen „passen“.Dazu müsste ich mir jetzt selbst einen Datentyp erstellen und
auch die Rechenoperationen für den neuen Datentypen müsste ich
selbst erstellen.
eigentlich gibt es dafuer bibliotheken.
im engl. ist es dieses: http://en.wikipedia.org/wiki/Arbitrary-precision_ari…
–
je@m1s07:~$ bc
bc 1.06.94
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty’.
5^5^5
19110125979454775203564045597039645991980810489900943371395127892465\
20530242615803012059386519739850265586440155794462235359212788673806\
97228841014691598660208796189675719570183928166033804761122597553362\
61010014826511234131477682524114930944471769652827562851967375143953\
57542479093219206641883011787169122552421070050709064674382870851449\
95025658619446154318351137984913369177992812743384043154923685552678\
35963741021053315460313537253257486369091597786903282664591829838152\
30286936572873691422648131291743762136325730321645282979486862576245\
36221801767322494056764281936007872071383707235530544635615394640118\
53484937927195145945055082327492216058489129109451899599486861995431\
47666938013037176163592594479746164220050885079469804487133205133160\
73913423054019887257003832980124605019701346739717590902738949392381\
73157869968458997947810680428224360937839463352654228157043028324423\
85515082316490967285712171708123232790481817268327510112746782317410\
98588868370852200071173349225391332230075614718042900752767779335230\
62006182860124552542430610068948054465847048206509826643193609603887\
36258510747074340636286976576702699258649953557976318173902550891331\
22329474393034395616132833407283166349825814522686200430779908468810\
38041873683248009038735962129196336025831207816736737425333228792969\
07205490595621406888825991244581842379597863476484315673760923625090\
37151179894142426227022006628648686786871018298087280256069310194928\
08308250441984247967920589088171123271923014555829167467951974305480\
26404646854002733993860798594465961501752586965811447568510041568687\
73090371248253534383928539759874945849705003822501248928400182659005\
62512861876299380444073401423470620557853053250349181895897071993056\
62188512963187501743535960282201038211616048545121039313312256332260\
76643623668829685020883949614283048473911399166962264994856368523471\
28732947966808845094058939511046509441379095022765456531330186706335\
21323028460519434381399810561400652595300731790772711065783494174642\
68472095613464732774858423827489966875505250439421823219135722305406\
67153733742485436456637820457016545932181540535483936142506644985854\
03307466468541890148134347714650315037954175778622811776585876941680\
908203125