# exakte Fakultät großer Zahlen



## mad87ger (27. Januar 2011)

Also das gleiche problem gabs schon mal, allerdings wurde es objektorientiert gelöst. Ich habe einen Ansatz der nicht objekt orientiert ist. Ich glaube er funktioniert fast, aber in der ausgabe schreibt er mist. Das Programm soll bis 100! rechnen. Addieren muss es nicht können. Nur von beliebigen zahlen die fakultät berechnen und ausgeben. Ich habe ziemlich viel kommentiert und auch testausgaben eingebaut. Das Programm wird euch in sachen Speicher- und Rechenzeit bedarf bestimmt belustigen, da viel unnötiges gamacht wird, aber darauf kam es in der aufgabe nicht an. Ich danke für eure geduld. Hier mein Quellcode:


```
#include <iostream>
using namespace std;
int main()
{
	int zahl[1000][2],v,w,x,n;
	cout <<"Exakte berechnung grosser Fakultaet"<<endl;
	cout <<"----------------------------------"<<endl;
	cout <<"Bitte geben Sie das n zu berechnende Fakultaet(n) ein:" << endl;
	cin >> n;
	
	//Das int Feld zur berechnung der Fakultät ist 1000 zeichen lang, die zweite zeile ist ein hilfsfeld
	//zum Zwischenspeichern, n ist die Zahl, deren Fakultät berechnet werden soll
	//v,w und x sind die 1. 2. und 3. Ziffer des ergebnisses für die aktuelle Fakultät * Eintrag des Zeichens
	//in der aktuellen Spalte
	
	zahl[0][0]=1;
	zahl[0][1]=1;
	//Die erste Spalte wird auf Null initialiesiert, als neutrales Element der späteren Multiplikation
	for (int i=1; i<1000; i++)
	{
		zahl[i][1]=-1;
		zahl[i][0]=-1;
	}
	//Alle anderen Spalten werden auf -1 initialisiert, um Abfragen zu können wo die Zahl endet
            //Damit nicht erst mal z.B 950 nullen ausgegeben werden

	for (int i=1; i<=n; i++)
	//Es müssen alle Zahlen im bereich von 1 bis n einmal mit dem vorherigen Wert multipliziert
	//werden. Beispiel 5! (!=Fakultät) = 1*2*3*4*5 = 120
	{
		for (int j=0; j<1000; j++)
	//Hier wird jeder Eintrag des Feldes auf gültigkeit überprüft und anschließend mit dem aktuellen 
	//i multipliziert. BSP Im Feld Steht 120, i=6    
            //__0*6 =    0
	//_20*6 = 120
	//100*6 = 600
		{
			if ((zahl[j][0])>0)
			{
			v=(zahl[j][0])*i;
			w=v-(v%10);
			x=w-(w%100);
			}
	//Hier werden die Ergebnisse in ihre einzelnen Ziffern aufgeteit. Bsp.:120 v=0, w=20, x=100

			if ((zahl[j][1])>0)
				zahl[j][1]= (zahl[j][1]) + v%10;
			else
				zahl[j][1]= v%10;
//Es wird geprüft ob an der stelle 10^0 schon etwas steht größer als 0, wenn ja wird das neue ergebnis
//zum alten dazuaddiert, wenn nicht wird der alte wert (also -1) durch den neuen ersetzt 

			if ((zahl[(j+1)][1])>0)
				zahl[(j+1)][1]=(zahl[j+1][1])+((w%100)/10);
			else
				zahl[(j+1)][1]=(w%100)/10;
//Es wird geprüft ob an der stelle 10^1 schon etwas steht (z.B übertrag von der vorherigen abfrage) 
//größer als 0, wenn ja wird das neue ergebnis zum alten dazuaddiert, 
//wenn nicht wird der alte wert durch den neuen ersetzt 

			if ((zahl[(j+2)][1])>0)
				zahl[(j+2)][1]= (zahl[j+2][1]) + ((x%1000)/100);
			else
				zahl[(j+2)][1]=(x%1000)/100;
//Es wird geprüft ob an der stelle 10^2 schon etwas steht größer als 0, wenn ja wird das neue ergebnis 
//zum alten dazuaddiert, wenn nicht wird der alte wert durch den neuen ersetzt. Da das Programm bis 
//100! funktionieren soll ist dieser Schritt nötig, da 9*100 schon 900 ist also 3 stellen 

		}
		
		for (int k=1; k<=1000; k++)
		zahl[k][0]=zahl[k][1];
//Wenn alle berechnungen durchgeführt wurden, wird die Hilfzeile in die hauptzeile kopiert
	}
	
	

	cout << "Die exakte Fakultaet n! fuer n=" << n << " betraegt:" << endl;
	

//Sind alle multiplikationen durchgeführt wird der Inhalt der einzelnen Elemente darauf überprüft 
//ob sie nicht mehr negativ sind, und werden dann in umgekehrter reihenfolge ausgegeben
	for (int i=1000; i>=0; --i)
	{
		if ((zahl[i][0])>=0)
			cout << zahl[i][0];
		else 
			cout << "";
	}

	cout << endl;
	cout << zahl[0][0] << endl;
	cout << zahl[1][0] << endl;
	cout << zahl[2][0] << endl;
	cout << zahl[3][0] << endl;
	cout << zahl[4][0] << endl;
	cout << zahl[5][0] << endl;
	cout << zahl[6][0] << endl;
	cout << zahl[7][0] << endl;
	cout << zahl[8][0] << endl;
	cout << zahl[9][0] << endl;
	cout << zahl[10][0] << endl;
	cout << endl;
	cout << zahl[100][0] << endl;
//Eine test ausgabe, damit ich sehe was einzelne felder machen
//Wie kommen in einzelne elemente des feldes zahlen mit mehr als einer ziffer?
//Und woher kommem die höheren einträge	z.b 227 im 100 element bei 20!


	cin >> n;
	//Eingabe nur zum Ansehen des Ergebnisses
}
```


----------



## deepthroat (27. Januar 2011)

Hi.





mad87ger hat gesagt.:


> Hier mein Quellcode:


Bitte verwende Code-Tags für deine Quelltexte! Also, fasse den Quelltext in [code=cpp]...[/code] ein.


mad87ger hat gesagt.:


> ```
> int zahl[1000][2],v,w,x,n;
> ...
> for (int i=1; i<=1000; i++)
> ...


Du greifst hier außerhalb der Grenzen des Arrays zahl zu, woraus undefiniertes Verhalten resultiert. Der valide Index wäre 0 bis 999, also i < 1000.

Dann solltest du mal erläutern was du dir dabei gedacht hast und wie das Ganze funktionieren soll.

Und evtl. solltest du erstmal versuchen den Algorithmus für kleine Werte zum Laufen zu bringen.

Gruß


----------



## mad87ger (27. Januar 2011)

ok danke das mit dem Feld habe ich geändert und auch die code tags benutzt. Also die aufgabe is ne übungsaufgabe für die informatik klausur. Es geht darum extrem lange Zahlen auszugeben und dafür einen eigen datentyp zu verwenden der bis zu 1000 Stellen ausgibt. Das Programm soll eine ganze Zahl einlesen und anschließend deren Fakultät ausgeben. Als beispiel sollen wie 100! ausgeben. 
Ich habe versucht dies mit einem 1000-Stelligen Feld des Typs Integer zu realisieren. Die anderen haben statt eines Feldes eine Struktur verwendet, aber meiner (vielleicht nicht sehr Fachkundigen) Meinung nach spielt das in dem Fall keine Rolle. 

Ich habe zwei Schleifen ineinander verschachtelt. Die äußere zählt jeweils die Fakultät (Multiplikant)
um eins hoch. Die innere läuft dann jeden eintrag des feldes durch, führt die Rechnung durch und "Zerlegt" das Ergebnis dann in ihre Zehnerpotenzen durch modulorechnung und speichert das Ergebnis dann eintragsweise im Hilfsfeld, in meinem fall habe ich dem Feld einach eine zweite Zeile hinzugefügt.
Dieses Hilfsfeld benötige ich für die überträge. 
Hier ein bsp. Im Hauptfeld (also feld[x][0] steht in den ersten drei feldern [0][0]=0, [1][0]=8, [2][0]=1 also 180 und n (also Fakultät) = 9 
1. 0*9 = 0  -->Im Hilffeld schreibe ich feld[0][1]=0
2. 8*9 = 72 --> In jedem Feld soll nur eine Ziffer stehen also 72 modulo 10 = 2     (72/10=7 rest2)
Im Hilfsfeld schreibe ich [1][1] =2, dann kommt 72 - modulo72 (also2) / 10 = 7 ich schreibe ins 
feld [2][1]=7
3. 1*9=9 ich muss ins feld [2][1] also 9 schreiben, da steht aber schon eine 7 drin, deshalb muss ich die beiden werte addieren und wieder auf überträge achten 7+9 =16 ...

OK jetzt bin ich selber auf ein problem gekommen, diese abfrage auf übertrag mache ich noch nicht
das werd ich gleich einbauen und das ergebnis dann posten 

Wenn die innere schleife komplett einmal durchgelaufen ist, wird das hilfsfeld elementeweise ins originalfeld Kopiert, dann wird die Fakultät eins hochgezählt usw.
Das auffälligste Problem das mir bei der ausgabe auffällt ist, dass in jedem Feld mehrere Ziffern stehen. Wenn man beispielsweise n=60! wählt stehen in den meisten Feldern 709, 
Warum? Da soll nur eine Ziffer drinstehen, deshalb mach ich ja die ganze sache mit den Modulorechnungen.

Am Ende des Programmes gebe ich das Feld "falschrum" aus, damit die Zahlen hinterher in der richtigen Reihenfolge auf dem Bildschirm stehen, da der eintrag in Feld[0][0] ja 10^0 ist. Deshalb initialisiere ich das gesamte Feld am anfang mit -1 und überschreibe diesen Wert dann in der Schleife. Bei der ausgabe gebe ich dann nur werte >=0 aus, damit ich nicht immer alle 1000 stellen angezeigt bekomme, sondern nur die in denen auch das Ergebnis steht.


----------



## sheel (27. Januar 2011)

Hi

ich finde, du würdest dir leicher tun, wenn du Operationen wie Addition etc extra in Funktionen verpackst.
So blickt man auf die Schnelle nicht durch, für was welcher Code eigentlich gut ist.

Und das Zahlenformat ändern. Warum überall -1? Mathematisch problemloser wäre, überall 0 reinzuschreiben.

Weiters: Wenn du in jedem int nur eine Ziffer hast, nimm char. Damit sparst du 3/4 des Speichers.

Und dann voneinander getrennt zB folgende Funktionen für die 1000-stelligen Zahlen:
-Übertrag (macht zB aus "1 69" "7 9"), ist hilfreich für die folgenden Funktionen
-Multiplizeren (wie man es in der Schule lernt: Für jede Ziffer der zweiten Zahl extra ausrechnen und dann (verschoben) zusammenaddieren. Übertrag verwenden)
-Dekrement: Eins herunterzählen. Ist nur ein -1 auf die Einerstelle und dann Übertrag.
-Funktion zum Null-Prüfen: Ob eine Zahl Null ist
-Fakultät:
Ergebnis=1
Ergebnis*=Zahl
Zahl dekrementieren
Ergebnis*=Zahl
Zahl dekrementieren...usw bis nur noch 0 übrigbleibt.

Bei Multiplikation etc kann man alle führenden Nuller ignorieren.
Bessere Performance (vor allem beim Auf-Null-Prüfen) bekommt man, wenn man mit jeder 1000.Stellen-Zahl eine 1001. int mitspeichert, wieviel führende Nuller in der Zahl sind bzw. wo die erste aussagekräftige Ziffer ist.
Diese Kennzahl immer aktuell zu halten macht die Funktionen aber ein wenig komplexer...sollte aber kein Problem sein.

Gruß


----------

