Addition großer Zahlen!

[Kathrinchen_]

Hallöchen! :p

Leider hab ich nicht viel Ahnung vom programmieren. Bin jetzt aber dabei mich da irgendwie durchzuwuseln :mad: .(hoffentlich hilft mir jemand)

Ich soll für eine Übung zwei zahlen von beliebiger Länge addieren und natürlich auf den overflow achten. Kann mir vielleicht jemand einen tip geben wie man so was macht?
Bei der Aufgabe steht das man die zahlen als array von digits verwalten soll.

Ich dank euch schon mal!
Gruß :rolleyes:

[MikeG]

Von welcher Größe reden wir denn? Evtl. reichen 64bit? Dann kannst Du dafür ja double nehmen.

Aber diese Sache mit Arrays of Digits tät mich auch interessieren.

[locus vivendi]

Da du ja selber schreibst das es sich um eine Übung handelt, möchte ich nicht eine komplette Lösung verraten. (ich habe ich auch gar keine fertige im Kopf)

Aber als Stichwort zur Hilfe möchte ich dich daran errinern wie du in der Grundschule das schriftliche Addieren gelernt hast. Die Lösung dürfte nämlich ganz genaus gehen. Wenn du spezifischere Fragen zu C++ (oder einer anderen Sprache) hast, kannst du die natürlich gerne stellen.

[wraith]

In welcher Sprache soll das denn erfolgen?

Die Idee die dahinter steckt, ist dir bereits vom schriftlichen addieren bekannt.Zwei Zahlen untereinander schreiben, und von rechts nach links durchlaufen, immer die beiden untereinanderstehend Zahlen addieren, falls Übertrag entsteht den in die nächste Stufe übernehmen.
Und genau so kannst du das auch programmieren.

Also fang bei zwei Digits an (schreib' dir eine Funktion dafür).
Was kann passieren?Es kann ein Übertrag (carry) in die nächste Stufe erfolgen.
Damit wird klar, daß deine Funktion 3 Eingabeparameter hat (die zwei Digits und der CarryIn der vorherigen Stufe) und 2 Ausgabeparameter (das 'Ergebnis' der Addition und der CarryOut in die nächste Stufe).
Das ist ein No-Brainer, 2-3 Zeilen max.

Darauf baust du jetzt eine Funktion auf, die zwei Zeichenketten 'addiert'.
Also die letzten beiden Digits anschauen, und addieren (das CarryIn ist hier '0', weil es keinen Vorgänger gibt), CarryOut und Ergebnis berechnen.
In beiden Zeichenketten zum nächsten Digit wechseln (also nach links gehen), CarryOut der vorherigen Stufe mitaddieren, usw...
Einziger Knackpunkt ist, daß eine Zeichenkette kürzer ist, wie die andere.

[Kathrinchen_]

Ich hab natürlich wirklich vergessen zu sagen das das Programm in C sein soll.
Eine 64- bit Darstellung reicht glaub ich nicht aus, da die das Programm mit bis zu 100-1000 Stellen funktionieren sollte.
Eine komplette Lösung möcht ich auch gar, sonst wäre der Lerneffekt gleich null. Nur einen leichten, einfachen, für jeden, auch für ein ahnungsloses Mädel, verständliche n Tip in einer Sprache die auch Programmieridioten verstehen.

Danke schön
Gruß!

[panzi]

Also es gibt da den header limits.h, da dinn ist mal das Makro INT_MAX definiert, welches die größte mögliche int Zahl angibt. In dem header sind noch andere _MAX Makros definiert, schau dir den header bzw. die Doku dazu an.
Also und dann wirst du wohl ein array von ints anlegen müssen. Um dieses Array wie eine lange int Variable verwenden zu können, musst du alle funktionen wie addition, subtraktion, multiplikation, division usw. dafür neu programmieren.
Bei der Addition musst du z.B. überprüfen, ob lhs[ i ] > INT_MAX - rhs[ i ], dann musst du dem ergebnis folgendes zuweisen: result[ i ] = rhs[ i ] - ( INT_MAX - lhs[ i ] ), wobei es einen übertrag gibt: result[ i + 1 ] += 1 (also um noch 1 größer als es die rechnung lhs[ i + 1 ] + rhs[ i + 1 ] ergibt, wobei da wieder das mit dem INT_MAX geprüft werden muss...).
Ob das jetzt tatsächlich ganz korrekt ist, hab ich net nachgeprüft.
In C++ wär das cooler zu programmieren, da du da tatsächlich den operator +, -, *, /, +=, -=, *=, /=, =, ==, !=, <, >, <=, >= etc. überladen kannst.

[sticky bit]

Wie schon erwähnt, das ganze läuft auf das Stellenweise Additionsverfahren, das wir aus der Grundschule kennen hinaus, welches nicht nur im dezimalen System funktioniert, sondern in allen Systemen zu beliebigen Basen.

Also Addieren wir mal 1594 mit 33 im dezimal System:
Wir nehmen die 3 und die 4 und addieren diese mit unserem Übertragspuffer der natürlich am Anfang 0 ist und erhalten 7.

Unseren Übertragspuffer füllen wir mit der ganzzahligen Divison von unserem Teilergebnis, der 7 und der Basis unseren Notationssystems, 10 und erhalten also 0.
Nun ziehen wir von unserem Teilergebnis, der 7, das Produkt aus unserem Übertragspuffer, der 0 und unserer Basis, der 10 ab und erhalten 7, welche wir von links an unseren noch leeren Ergebnispuffer anfügen so das dieser so aussieht: 7
Wir gehen weiter und addieren die 3 und die 9 und unseren Übertragspuffer, 0 und erhalten 12.
Den Übertragspuffer füllen wir wieder mit der ganzzahligen Division unseres Teilergebisses, 12, und der Basis, also 1.
Und wir fügen wieder von links die Differenz unseres Teilergebnises, 12 und dem Produkt unseres Übertragspuffers, 1 und der Basis 10, also der 2 so dass unser Ergebnispuffer dann so aussieht: 27.

Im nächsten Schritt addieren wir diesmal die 5 mit der 0 (weil unser zweiter Summand bereit zu Ende ist) und unseren Übertragspuffer, 1 und erhalten 6.
Den Übertragspuffer füllen wir wieder mit der ganzzahligen Division des Teilergenises, 6 und der Basis, 10, also 0.
Und wie gehabt hängen wir von links an unseren Ergebnispuffer die Differenz des Teilergebnises 6 und dem Produkt des Übertragspuffers, 0 und der Basis 10, so dass der Ergebispuffer nun 627 enthält.

Jetzt könnten wir wieder das ganze machen oder weil wir wissen, dass wir zwei Stellen hinter dem Ende des kleineren Summanden sind das ganze abkürzen und einfach die 1 von links an das Ergebnis dranhängen, so dass die 1627 rauskommt.

Achtung wenn die Zahlen die gleiche Anzahl an Stellen haben müssten wir noch einmal das ganze Ausführen (mit zwei mal der 0 als aktuelle Stelle in den Zahlen) um einen evtl. im Übertragspuffer verbleibenden Wert noch anzufügen! Entfällt in dem Fall aber...


Jetzt nehmen wir an Du hast nen Rechner der nur ein Byte auf einmal abarbeiten kann (und Überlaufbit sonst gehts nicht allgemein, erklär ich gleich), also Werte von 0 bis 255, dann müsstest du den ersten Summanden aus obigen Bsp. als zweielementigen Array mit 6 und 58 darstellen, weil wir einfach die 256 als Basis für unser Stellenwertsystem nehmenund 6 mal 256 hoch 1 plus 58 mal 256 hoch 0 gleich 1594 ist. Die 33 passt in eine Stelle, also kommt sie in einen ein elementigen Array.

Jetzt können wir wieder das Verfahren von oben anwenden, addieren also die 58 und die 33 mit dem Übertragspuffer, 0 und erhalten 91.
Unseren Übertragspuffer könnten wir nun verfahrensgemäss wieder mit dem Ergenis der ganzzahligen Division useres Teilergebnisses 91 und der Basis, 256 füllen wo wir 0 erhalten würden.
Nun mag aber auffallen, dass man ja als Teiladdition maximal 255 + 255 haben könnte was zu 510 führen würde und auch die 256 nicht in ein Byte passt was unserer imaginärer Rechner aber nicht mehr verarbeiten kann, schliesslich kann er nur 1 Byte. Und jetzt kommt das mit dem Überlaufbit (so was gibts in Prozessoren tatsächlich), unser Rechner hat das nämlich nun auf 1 gestellt und das Ergenis einfach soweit er konnte in das Byte gepackt. Da wir wissen, dass maximal 510 rauskommen kann und die nächste zweier Potenz minus 1 dazu die 511 ist, was genau in 9 Bit passt also unser Byte und unser Überlaufbit wissen wir auch dass dieses eine Bit reicht und wir unseren Übertrag auch berechnen können in dem wir ihn gleich dem Überlaufbit setzen und selbst wenn wir dann noch mal 255 + 255 + unsern Übertrag mit 1 haben passt das noch in die 9 Bits weil das genau 511 ist!
Das aber nur als kleinen Exkurs, ich weiss ja nicht was Du lernst aber wenn du näher an die Hardware kommst kannst du das u. U. gebrauchen, in deinem C Programm wo du analog zum Bsp. unsigned char Arrays benutzt hindert dich natürlich keiner daran dein Teilergebnis einfach in einem grösseren (mindestens 1 Byte breiter, weil wir wie gesagt 1 Bit mehr brauchen wegen der Oktetgrenze aber nur ganze Bytes bekommen) Datentyp aufzufangen, z. B. unsigned short int und ganz normal weiter zu machen (aber Achtung casten nicht vergessen wenn du wieder deinen unsigned char zuweist! Obwohl das teilweise auch implizit geschieht ist das sauberer!).
Also zurück zum Schema F, an unseren Ergenispuffer in dem Fall auch ein Array aus Bytes der im Moment noch kein Element hat fügen wir von links wieder die Differenz unseres Teilergebnisses, 91 mit dem Produkt unser Basis 256 und dem Übertragspuffer, 0 so dass der Array nun aus der 91 besteht.
Um noch mal kurz auf das Überlaufbit zurück zu kommen, weil wir ja hier schon wieder die 256 die zu gross ist verwendet haben, es würde auch genügen das Ergebnis in dem Byte das unser imaginärer Rechner gefüllt hat anzuhängen, denn der Schritt oben mit der Differenz des Teilergenisses und des Produktes macht nichts anders als die rechte Stelle (also im Falle des imaginären Rechners das Byte) zu isolieren, jetzt aber Schluss mit Hardware *g*.

Gemäss Verfahren addieren wir jetzt die 6 weil die als nächstes im ersten Array kommt und die 0 weil der zweite Array ja bereits zu Ende ist und noch mal die Null aus unserem Übertragspuffer und erhalten die 6.
Den Übertragspuffer füllen wir wieder mit dem Ergebnis der ganzzahligen Division des Teilergebnisses 6 und der Basis 256 und erhalten die 0.
Von links können wir nun an unseren Ergebnispuffer die Differenz des Teilergebnisses und dem Produkt des Überlaufpuffers, 0 und der Basis 256, was zu 6 ist anfügen, so dass dieser aus der 6 und der 91 besteht.

Nicht vergessen, dass wir unseren Übertragspuffer noch mal von links an den Ergebnispuffer anfügen müssten wenn die beiden Arrays gleich lang wären, denn dieser könnte dann noch etwas enthalten, in dem Fall ist das aber nciht so, also können wir das auslassen.

Überprüfen wir das Ergebnis:
6 mal 256 hoch 1 plus 91 mal 256 hoch 0 ist gleich 6 mal 256 plus 91 ist gleich 1627!


Natürlich kann man das ganze auch auf binärer Ebene aus führen, ich weiss ja nicht was dir beigebracht werden soll, so könnte man dann halt Hardware relativ genau simulieren wenn man dann anstatt mathmatischer Operatoren (+, -, etc.) durch die Elemente shiftet (<< nach links und >> nach rechts wobei links hier eigentlich alles sein dürfte was man braucht) und bitweise Verknüpfungen (& (and), | (or), ^ (xor), ~ (not)) verwendet und so Schaltelemente und die deren Ansteuerung simuliert...


Hoffe du hast die Zusammenhänge erkennen können und kannst daraus das gesuchte basteln.
Ansonsten, was ich eigentlich sagen wollte, wenn du mal sehen willst wie sowas aussehen kann oder es später mal brauchst aber nicht selber schreiben willst schau dir mal die GMP Bibliothek an, das Rad wurde dahingehend schon erfunden:
http://www.swox.com/gmp/

[Kathrinchen_]

Ich versteh das alles nicht!

[ContainerDriver]

Servus,
das ist doch wirklich nicht soooo schwer. Addition von Zahlen ohne Taschenreechner machst du ja so:


1 3 6 8
+ 3 5
================
1 4 0 3

. wenn eine Spalte > als 10 ist, wird nur die letzte Ziffer der addierten Zahlen in der Spalte gewertet, die anderen Ziffern bilden einen Übertrag für die nächste Spalte.
Jede Ziffer der Zahl stellt dabei ein Element in einem Array (vlt. auch in einer verketten List) dar. Jede Zahl stellt ein Array (Liste) dar.
Weißt du jetzt weiter?

Gruß, FLorian

[sticky bit]

Ich versteh das alles nicht!
Linguistisch, mathematisch oder programmiertechnisch?

Gibts wenigstens Teile die Du verstehst? Wenn ja was verstehst Du dann im Detail nicht?

[Kathrinchen_]

erstmal danke für die Hilfe. Ich habe jetzt folgende Lösung, aber da steckt noch ein Fehler drinn. Könnt ihr mir bitte sagen was falsch ist (bitte konkret, ich stehe etwas unter Zeitdruck
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
int i, n=0, laenge_num1=0, laenge_num2=0, carry=0, laenge_ergeb;
char* num1;
char* num2;
char* ergeb;

printf("\nAddition grosser Zahlen\n");
printf("\nAnzahl an Dezimalstellen angeben: ");
scanf("%d, &n");

num1 = (char*)malloc(n* sizeof(char)); num2 = (char*)malloc(n* sizeof(char)); ergeb = (char*)malloc(n* sizeof(char));

printf("\nErste Zahl eingeben: ");
scanf("%s", num1);

printf("\nZweite Zahl eingeben: ");
scanf("%s", num2);

laenge_num1 = strlen(zahl1); laenge_num2 = strlen(zahl2);

if(laenge_num1 >= laenge_num2)
laenge_ergeb = laenge_num1;
else
laenge_ergeb = laenge_num2;

for(i=laenge_ergeb; i>0; i--)
{
num1[i] = num1[i-laenge_ergeb+laenge_num1-1] - '0'; num2[i] = num2[i-laenge_ergeb+laenge_num2-1] - '0'; } for (i=laenge_ergeb - laenge_num1; i>=0; i--) num1[i] = 0;
for (i=laenge_ergeb - laenge_num2; i>=0; i--) num2[i] = 0;


for(i=laenge_ergeb; i>=0; i--)
{
ergeb[i] = num1[i] + num2[i] + carry; carry = 0;
if(ergeb[i]>9) {
ergeb[i] = ergeb[i] - 10;
carry = 1;
}
}

for(i=1-ergeb[0]; i<=laenge_ergeb; i++)
printf("%d", ergeb[i]);
printf("\n\n");

free (num1);
free (num2);
free (ergeb);

return 0;
}

Als fehler im Compiler erhalte ich:Undeclared identifier 'zahl1,Type error in argument 1 to 'strlen'; found 'int' expected 'const char *,Undeclared identifier 'zahl2,ype error in argument 1 to 'strlen'; found 'int' expected 'const char *

[wraith]

laenge_num1 = strlen (zahl1);
laenge_num2 = strlen (zahl2);

Das soll num1 und num2 heißen, zahl1 und zahl2 gibt es nicht.
Und hier ist die ein kleiner Fehler unterlaufen


scanf ("%d, &n");

[Kathrinchen_]

Ich habe jetzt erfahren das das Programm nicht ganz korrekt ist.

Wenn die Zahlen eine gewisse Grosse erreichen, stuerzt das Programm
ab. Die Ausgabe sieht dan bspw. so aus:

Addition grosser Zahlen

Anzahl der maximalen Dezimalstellen angeben: 23

Erste Zahl eingeben: 123134142.

Kann mir jemand helfen?


Exiting due to signal SIGSEGV
General Protection Fault at eip=0000268f
eax=0195b1bc ebx=0008ff58 ecx=0008ff58 edx=019677ec esi=00090164
edi=00656c6f
ebp=0008f8e8 esp=0008f8dc


cs: sel=01a7 base=02a90000 limit=0009ffff
ds: sel=01af base=02a90000 limit=0009ffff
es: sel=01af base=02a90000 limit=0009ffff
fs: sel=017f base=00013fe0 limit=0000ffff
gs: sel=01bf base=00000000 limit=0010ffff
ss: sel=01af base=02a90000 limit=0009ffff
App stack: [0008f948..0000f948] Exceptn stack: [0000f8a8..0000d968]

Call frame traceback EIPs:
0x0000268f
0x000018dc
0x00001f78

[Der Untergeher]

Könnte helfen:

num1 = (char*)malloc(n* sizeof(char)); num2 = (char*)malloc(n* sizeof(char)); ergeb = (char*)malloc(2*n* sizeof(char));

und das hier ist Quark:


if(laenge_num1 >= laenge_num2)
laenge_ergeb = laenge_num1;
else
laenge_ergeb = laenge_num2;

[sticky bit]

num1 = (char*)malloc((n + 1) * sizeof(char));
// der Stringterminator muss da auch noch rein du liest das ja als String ein!
num2 = (char*)malloc((n + 1) * sizeof(char));
// der Stringterminator muss da auch noch rein du liest das ja als String ein!
ergeb = (char*)malloc((n + 1) * sizeof(char));
// Und hier könnte ein Stellenüberlauf passieren (vgl. 2 dez. Stellen: 99 + 99 = 198 -> 3 dez. Stellen) also eins mehr (mal 2 wie mein Vorredner sagte ist viel zu viel)

Den Rest deines Codes hab ich so gelassen und bei mir ausprobiert, zumindest ich habe keine Probleme mehr entdecken können, der Code ist allerdings etwas unleserlich und teilweise sehr "kreativ" (z. B. dass du um die Zahl zu bekommen mit dem Zeichen '0' subtrahierst, ist zwar ne nette Idee (wär ich gar nicht drauf gekommen) aber der "übliche" Weg wäre wohl atoi() gewesen ;) (kannteste aber wahrschl. nicht) und auch deine Umsortierung damit die Zahlen hinten im Array stehen weil deren Zeichen durch das scanf() erst mal vorne reinkommen will mir nicht so recht in den Kopf aber es scheint ja zu funktionieren...).

[Kathrinchen_]

Und wie würde dann so ein Programm in C für die Multiplikation von großen Zahlen aussehen?

Danke

[sticky bit]

Und wie würde dann so ein Programm in C für die Multiplikation von großen Zahlen aussehen?Nachdem sich die Multiplikation auf die Addition zurückführen lässt würde das Programm das dann auch tun.