Entwickler-Ecke
C# - Die Sprache - Fakultät von 10000 berechnen, Algorithmus optimieren
Keeper - Do 14.05.09 15:09
Titel: Fakultät von 10000 berechnen, Algorithmus optimieren
Hallo alle zusammen, ich habe eine hübsche Aufgabe von meinem Prof bekommen:
Ich soll die Fakultät von 10000 berechnen und zwar unter einer Minute. Soweit so einfach, einen Algorithmus hab ich auch dafür nur ist dieser viel zu langsam. Er funktioniert soweit ich des beurteilen kann.
Es wäre super wenn mir noch jemand mit Optimierungsmöglichkeiten helfen könnte, Code weiter unten.
LongNumbers.CS:
C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
| using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication2
{
class LongNumber
{
List<byte> _Digits = new List<byte>();
private LongNumber()
{
}
public LongNumber(string Init)
{
for(int i = Init.Length -1; i >= 0 ; --i)
{
if (char.IsDigit(Init[i]))
{
_Digits.Add((byte)(Init[i] - '0'));
}
else
{
throw new ArgumentException("Number is not a digit.");
}
}
}
public LongNumber(int size)
{
_Digits = new List<byte>(size);
for (int i = 0; i < size; ++i)
{
_Digits.Add(0);
}
}
public int Length
{
get { return _Digits.Count; }
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
for (int i = _Digits.Count - 1; i >= 0; --i)
{
sb.Append(_Digits[i]);
}
return sb.ToString();
}
static public LongNumber operator+(LongNumber X1, LongNumber X2)
{
LongNumber result = new LongNumber();
int max = (X1.Length > X2.Length) ? X1.Length : X2.Length;
bool carry = false;
byte digit = 0;
byte carryValue = 0;
for (int i = 0; i < max; ++i)
{
if (i < X1.Length && i < X2.Length)
{
digit = (byte)(X1._Digits[i] + X2._Digits[i]);
}
else if (i < X1.Length)
{
digit = (byte)(X1._Digits[i]);
}
else if (i < X2.Length)
{
digit = (byte)(X2._Digits[i]);
}
if (carry)
{
digit++;
carryValue--;
}
carry = (digit >= 10);
if (carry)
{
digit -= 10;
carryValue++;
}
result._Digits.Add(digit);
}
if (carryValue > 0)
{
result._Digits.Add(carryValue);
}
return result;
}
static public LongNumber operator *(LongNumber X1, LongNumber X2)
{
LongNumber num1 = new LongNumber();
LongNumber num2 = new LongNumber();
int max = (X1.Length > X2.Length) ? X1.Length : X2.Length;
byte[,] result = new byte[max,max+max];
byte carryValue = 0;
int j = 0;
for (int i = 0, k = X1.Length - 1 ; k >= 0; i++ , k--)
{
for (j = 0; j < X2.Length; j++)
{
if (j < X1.Length && j < X2.Length)
{
byte multiply = (byte)((X1._Digits[k] * X2._Digits[j]) + carryValue);
if ((multiply + carryValue) < 10)
{
result[i, (max - 1 - i) + j] = multiply;
carryValue = 0;
}
else
{
result[i, (max - 1 - i) + j] = (byte)(multiply % 10);
carryValue = (byte)(multiply / 10);
}
}
else if (j < X1.Length)
{
result[i, (max - 1 - i) + j] = (byte)(X1._Digits[k] + carryValue);
}
else if (j < X2.Length)
{
result[i, (max - 1 - i) + j] = (byte)(X2._Digits[j] + carryValue);
}
}
if (carryValue > 0)
{
result[i, (max - 1 - i) + j] = carryValue;
carryValue = 0;
}
}
bool l = false;
for (j = 0; j < max + max; j++)
{
num1._Digits.Add(result[0, j]);
}
string compare = "";
for (int c = 0; c < (max + max); c++)
{
compare += "0";
}
for (int i = 1; i < max; i++)
{
num2._Digits.Clear();
l = false;
for (j = 0; j < (max + max) ; j++)
{
num2._Digits.Add(result[i, j]);
}
if (num2.ToString() != compare)
{
num1 += num2;
}
}
return num1;
}
}
} |
Berechnung der Fakultät:
C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
| using System;
using ConsoleApplication2;
public class Controller
{
public Controller()
{
}
public string startCrunsher(int start,int end,int step)
{
if (start < 1)
{
return "Start muss größer 1 sein";
}
if (end < 1)
{
return "Ende muss größer 1 sein";
}
if (step < 1)
{
return "Schritt muss größer 1 sein";
}
if (start > end)
{
return "Start muss kleiner als Ende sein!";
}
if (end < step)
{
return "Schrittgröße muss kleiner als Ende sein!";
}
int ForStep = step;
LongNumber result = new LongNumber("1");
for (int i = 1; i <= end; i+=ForStep)
{
result = result * new LongNumber(i.ToString());
}
return result.ToString(); }
} |
und in der Main steht halt der Funktionsaufruf: string res = cl.startCrunsher(1,1000,1);
Bin für jede Hilfe dankbar, da ich ehrlichgesagt keine Ahnung habe warum das solang braucht und auch noch totaler Neuling in der Sprache bin.
danielf - Do 14.05.09 15:42
Hallo und :welcome:,
es geht soooo lang weil du jedes mal ein neues Objekt von Typ LongNumber erstellst. Du verwandelst deinen Counter i in einen String und dann zurück in eine Zahl. Das verbrauch sehr viel Performance.
Diese Stelle: new LongNumber(i.ToString());
Besser du erweiterst dein Klasse LongNumber, dass sie ein int nimmt. Somit sparst du schon ein bisschen an Leistung. Dann fällt auch die Überprüfung von isDigit weg,.. was auch nochmal Zeit frisst.
Das ist das was ich so auf anhieb sehe... aber vermutlich ist da noch viel mehr vergraben ;) Ansonsten hilft wohl nur noch ein Großrechner ;)
Gruß Daniel
Thorsten83 - Do 14.05.09 15:47
Hey,
interessante Aufgabe ;)
C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
| static public LongNumber operator *(LongNumber X1, LongNumber X2)
{
LongNumber result = X1;
for (int i = 1; i < int.Parse(X2.ToString()); i++)
{
result += X1;
}
return result;
} |
Zum einen bin ich mir nicht sicher, ob das überhaupt funktioniert, zum anderen dürfte der wiederholte Aufruf von parse ordentlich Rechenzeit fressen...
Keeper - Do 14.05.09 16:02
Hi, danke schonmal für alle Antworten. Ich hab jetzt mal den Multiplikationsalgorithmus hinzugefügt so wie ich ihn bisher habe. Leider ist der noch brutal langsam.
Ich bastel grade noch dran rum.
Ich versuch mal die Vorschläge soweit umzusetzen :)
Kha - Do 14.05.09 17:24
 Keeper hat folgendes geschrieben  : |
| Hi, danke schonmal für alle Antworten. Ich hab jetzt mal den Multiplikationsalgorithmus hinzugefügt so wie ich ihn bisher habe. Leider ist der noch brutal langsam. |
Ich verstehe ihn auch ehrlich gesagt nicht :mrgreen: . Wofür brauchst du denn das zweidimensionale Array, normalerweise sollte das direkt alleine mit den drei BigInts funktionieren?
Ein paar Sachen, die mir sonst noch einfallen:
- Statt Dezimalsystem einen ganzen Int32 ausnutzen
- Wie gesagt Strings einfach ganz außen vor lassen, für die Schleifenvariable kannst du doch ebenfalls einen BigInt benutzen
- Für große Zahlen dann evtl. sogar Karatsuba
F# schafft es jedenfalls in 125 ms, da ist also noch Luft :zwinker: .
Greenberet - Do 14.05.09 22:11
Wenn du mehrere CPUs/Kerne auf deinem Rechner zur Verfügung hast könntest du die Hälfte der Operationen in einen 2ten Thread z.B.: auslagern.
z.B: Hauptthread rechnet von 1-5000 und der 2te Thread von 5001 bis 10000. Sobald dann beide Ergebnisse da sind Multiplizierst du sie noch miteinander.
_Joe_ - Sa 16.05.09 12:26
ist aber arg "schwer" was du da machst:
in python
C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
| #/usr/bin/env python3
zahl = 1
zahl = int(input("Geben Sie eine Zahl ein: "))
if zahl < 0:
print("Negative Zahlen sind nicht erlaubt")
ergebniss = 1
for i in range(2, zahl+1):
ergebniss = ergebniss * i
print("Ergebnis: ", ergebniss) |
braucht für deine 10000 ~2sec.
Kha - Sa 16.05.09 12:29
| _Joe_ hat folgendes geschrieben : |
| ist aber arg "schwer" was du da machst: |
Wenn er eine fertige BigInt-Implementierung benutzen dürfte, gäbe es wohl dieses Topic nicht...
Und dass es noch deutlich schneller als 2s geht, habe ich ja auch schon geschrieben ;) .
_Joe_ - Sa 16.05.09 12:31
vielleicht ist es auch schnell ist nur geschätzt :dunce:
Thorsten83 - Sa 16.05.09 16:57
Keeper - Di 19.05.09 00:34
Hi Leute,
vielen Dank für eure Hinweise und Tipps. Ich hab das Programm fertig bekommen und die Multiplikationsmethode in die Tonne getreten und neu gemacht. Am Mittwoch bekomm ich das Ergebniss (vom Prof). Ich poste dann den Quelltext hier im Anschluss, dann kann ich auch gleich sagen ob er noch Macken hatte.
Freitag 24 Uhr war Abgabe, wurde knapp fertig sonst hät ich ihn noch vorher hier reingestellt.
Also danke nochmal an alle :)
EDIT: 10000 Hat übrigends rund 1, ungrad Minuten gedauert, also kann man da sicher noch was Optimieren, aber Source gibts Am Mittwoch, nur für alle die mal das gleiche Problem haben sollten :)
Keeper - Fr 29.05.09 16:21
Hi, Sry hat etwas länger gedauert, hier der Sourcecode der Berechnungsklasse:
C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
| using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication2
{
public class LongNumber
{
byte[] _Digits;
private LongNumber()
{
_Digits = new byte[0];
}
public LongNumber(string Num)
{
_Digits = new byte[Num.Length];
for (int i = 0; i < Num.Length; i++)
{
if (char.IsDigit(Num[i]))
{
_Digits[i] = (byte)(Num[i] - '0');
}
else
{
throw new ArgumentException("Number is not a digit.");
}
}
}
public LongNumber(int numbers)
{
string strNumbers = numbers.ToString();
_Digits = new byte[strNumbers.Length];
for (int i = 0; i < strNumbers.Length; i++)
{
_Digits[i] = (byte)(strNumbers[strNumbers.Length - i - 1] - '0');
}
}
private int GetIntegerDigits(int number)
{
int digits;
if (number == 0)
{
return 1;
}
for (digits = 0; number != 0; digits++)
{
number /= 10;
}
return digits;
}
public LongNumber(byte[] number)
{
_Digits = number;
}
public int Length
{
get { return _Digits.Length; }
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
for (int i = _Digits.Length - 1; i >= 0; --i)
{
sb.Append(_Digits[i]);
}
return sb.ToString();
}
static public LongNumber operator +(LongNumber X1, LongNumber X2)
{
int max = (X1.Length > X2.Length) ? X1.Length + 1 : X2.Length + 1;
LongNumber result = new LongNumber(new byte[max]);
byte digit = 0;
byte carryValue = 0;
int i;
for (i = 0; i < max; ++i)
{
digit = 0;
if (i < X1.Length && i < X2.Length)
{
digit = (byte)(X1._Digits[i] + X2._Digits[i] + carryValue);
}
else if (i < X1.Length)
{
digit = (byte)(X1._Digits[i] + carryValue);
}
else if (i < X2.Length)
{
digit = (byte)(X2._Digits[i] + carryValue);
}
carryValue = (byte)(digit / 10);
digit = (byte)(digit % 10);
result._Digits[i] = digit;
}
if (carryValue > 0)
{
result._Digits[i + 1] = carryValue;
}
result = removeZeroes(result);
return result;
}
static private LongNumber removeZeroes(LongNumber number)
{
if (number.Length <= 0)
return number;
int index = number.Length - 1;
while (number._Digits[index] == 0 && index > 0)
{
index--;
}
if (index == number.Length)
{
return number;
}
byte[] tmp = new byte[index + 1];
for (uint i = 0; i <= index; i++)
{
tmp[i] = number._Digits[i];
}
return new LongNumber(tmp);
}
static public LongNumber operator *(LongNumber X1, LongNumber X2)
{
LongNumber result = new LongNumber();
for (int i = 0; i < X1.Length; i++)
{
byte a = X1._Digits[i];
byte carryValue = 0;
byte[] tmpresult = new byte[X1.Length + X2.Length];
for (int j = 0; j < tmpresult.Length - i; j++)
{
byte b = 0;
if (j < X2.Length)
{
b = X2._Digits[j];
}
byte res = (byte)(a * b + carryValue);
carryValue = (byte)(res / 10);
tmpresult[i + j] = (byte)(res % 10);
}
result = result + new LongNumber(tmpresult);
}
return result;
}
}
} |
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!