New extended euclid code without global variables.

1 files changed, 19 insertions, 17 deletions

diff --git a/math/lgsFp.cpp b/math/lgsFp.cpp
index 439e5b7..14549b7 100644
--- a/math/lgsFp.cpp
+++ b/math/lgsFp.cpp
@@ -1,28 +1,30 @@
 // Laufzeit: O(n^3)
-void normalLine(ll n, ll line, ll p) { // Normalisiert Zeile line.
+void swapLines(int n, int l1, int l2) {
+	for (int i = 0; i <= n; i++) swap(mat[l1][i], mat[l2][i]);
+}
+
+void normalLine(int n, int line, ll p) {
 	ll factor = multInv(mat[line][line], p); // Implementierung von oben.
-	for (ll i = 0; i <= n; i++) {
+	for (int i = 0; i <= n; i++) {
 		mat[line][i] *= factor;
 		mat[line][i] %= p;
-	}
-}
+}}
 
-void takeAll(ll n, ll line, ll p) { // Zieht Vielfaches von line von allen anderen Zeilen ab.
-	for (ll i = 0; i < n; i++) {
+void takeAll(int n, int line, ll p) {
+	for (int i = 0; i < n; i++) {
 		if (i == line) continue;
 		ll diff = mat[i][line];
-		for (ll j = 0; j <= n; j++) {
+		for (int j = 0; j <= n; j++) {
 			mat[i][j] -= (diff * mat[line][j]) % p;
-			while (mat[i][j] < 0) {
-				mat[i][j] += p;
-			}
-		}
-	}
-}
+			mat[i][j] %= p;
+			if (mat[i][j] < 0) mat[i][j] += p;
+}}}
 
-void gauss(ll n, ll p) { // nx(n+1)-Matrix, Koerper F_p.
-	for (ll line = 0; line < n; line++) {
+void gauss(int n, ll p) { // nx(n+1)-Matrix, Körper F_p.
+	for (int line = 0; line < n; line++) {
+		int swappee = line;
+		while (mat[swappee][line] == 0) swappee++;
+		swapLines(n, line, swappee);
 		normalLine(n, line, p);
 		takeAll(n, line, p);
-	}
-}
+}}