Langzahlarithmetik

Hallo!

Ich hoffe mal, dass ich hier mit meinem Problem einigermassen richtig bin -- konkret handelt es sich zwar um C++-Programmierung, es ist aber eigentlich eher doch ein mathematisches Problem

Also folgendes:

Es soll (in C++) eine Klasse fuer "Langzahlen" (auch gebrochene Zahlen!) erstellt werden, da bekanntermassen z.B. der Datentyp double fuer das Rechnen mit hoher Genauigkeit nicht ausreicht.
Das prinzipielle Vorgehen ist dabei bekannt/gegeben: Der Vorkomma- sowie der Nachkommateil werden getrennt gespeichert:

- hier bei uns reicht fuer den Vorkomma-Teil int bzw. long int
- die Nachkommastellen werden in einem int-Feld gespeichert.

Somit koennen halt gebrochene Zahlen mit "beliebig vielen" Nachkommastellen repraesentiert werden. Nun zum eigentlichen Problem

Wie sieht der Algorithmus zum Multiplizieren bzw. Addieren zweier solcher Langzahlen aus?

Wenn es sich ledigliche um ganze Zahlen handeln wuerde, waere das Ganze ja wesentlich einfacher, man koennte ja z.B. einfach den Algorithmus der "Schulmethode" nachstellen.
Angenommen, die zwei Langzahlen 1.2345 und 5.6789 sollen multipliziert werden. Nun koennte (bzw. muss ich, da ja getrennt gespeichert) man ja zunaechst einfach die Vorkomma-Teile multiplizieren (Ueberlauf abfangen!?) und die Nachkomma-Teile getrennt betrachten. Und genau da liegt das Problem, wie bringe ich dann beides am Ende wieder korrekt zusammen!?

Offensichtlich ist das schon ein eher "triviales" Problem (wie die Mathematiker so schoen sagen *g*), allerdings stehe ich gerade extrem auf dem Schlauch ...

Danke fuer Hinweise!
Gruss.

Taurin

Wie speicherst du ein drittel in deinem Datenformat? Welche Operationen ausser Addition und Multiplikation willst du noch durchführen? Dividieren geht schnell schief. Was spricht gegen die schriftliche Addidtion/Multiplikation?

Edit: Und zum Multiplizieren würde ich erstmal Addieren und Bitshifts bauen.

Taurin schrieb:

Wie speicherst du ein drittel in deinem Datenformat?

Naja, gute Frage Vermutlich koennte man festlegen, dass z.B. max. 500 Nachkommastellen benutzt werden => 0,333...33. Macht das Sinn?

Taurin schrieb:

Welche Operationen ausser Addition und Multiplikation willst du noch durchführen?

Subtraktion auch noch. Division muss man sich halt was ueberlegen, z.B. naeherungsweise Division.

Taurin schrieb:

Was spricht gegen die schriftliche Addidtion/Multiplikation?

Was meinst Du mit schriftlich? Die "Schulmethode"? Also quasi folgender Algorithmus fuer das Multiplizieren:

Multiplikation von 1234 und 5678:
-> 1234 * 5 * 10^3
-> 1234 * 6 * 10^2
-> 1234 * 7 * 10^1
-> 1234 * 8 * 10^0

-> Addition der Teilergebnisse

Also fuer ganzzahlige Werte wuerde ich das wie oben beschrieben hinbekommen, wie mache ich das aber mit gebrochenen Zahlen? Auf dem Papier bekomme ich es wohl hin, aber in Algorithmus-Form...

Danke und Gruss.

frobnicate.foo schrieb:

Es soll (in C++) eine Klasse fuer "Langzahlen" (auch gebrochene Zahlen!) erstellt werden, da bekanntermassen z.B. der Datentyp double fuer das Rechnen mit hoher Genauigkeit nicht ausreicht.

Wie genau brauchst du es denn? Erst ist dir double nicht genau genug, dann willst u die Division annähern

Ich denke, dass double locker reicht für deine Zwecke!

Für rationale Zahlen kannst du zunächst mal ganze Zahlen implementieren und dann a/b, a \in Z, b \in N\{0}, ggT(a,b)=1 damit implementieren.

Taurin

frobnicate.foo schrieb:

Multiplikation von 1234 und 5678:
-> 1234 * 5 * 10^3
-> 1234 * 6 * 10^2
-> 1234 * 7 * 10^1
-> 1234 * 8 * 10^0

-> Addition der Teilergebnisse

Und jetzt denk mal drüber nach, dass im Speicher alle Zahlen binär vorliegen. Und darüber, wie du ein left-shift implementierst. Und was du alles an logischen Operatoren im Arsenal hast.

Wie bist du überhaupt auf dieses seltsame Speicherverfahren gekommen? Ist das ne Übungsaufgabe oder hat das irgendeine konkrete Anwendung? Normalerweise kommt man nämlich mit doppelter Genauigkeit schon ziemlich weit, wenn man sie nur richtig einsetzt. Vielleicht könnte dir damit auch jemand helfen.

Taurin schrieb:

Wie bist du überhaupt auf dieses seltsame Speicherverfahren gekommen? Ist das ne Übungsaufgabe oder hat das irgendeine konkrete Anwendung? Normalerweise kommt man nämlich mit doppelter Genauigkeit schon ziemlich weit, wenn man sie nur richtig einsetzt. Vielleicht könnte dir damit auch jemand helfen.

Ja, es ist eine Uebungsaufgabe, wenn man so will. Besonders sinnvoll finde ich sie allerdings nicht. Alleine wuerde ich mir soetwas wohl kaum ausdenken, sondern bei Bedarf auf z.B. gmp, hfloat etc. zurueckgreifen

Danke trotzdem fuer die bisherigen Antworten, ich werde mir das Ganze nochmal in Ruhe durch den Kopf gehen lassen ... weitere Hinweise sind natuerlich willkommen

Gruss.

Henno

A = Vorkommaanteil
B = Nachkommaanteil

(A1 + B1) * (A2 + B2) = A1*A2 + A1*B2 + A2*B1 + B1*B2