From ca740ed7caeca4deb09a2fc7912f599555442e15 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Sat, 22 Nov 2014 11:46:50 +0100 Subject: bisschen LGS --- math/lgsFp.cpp | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) create mode 100644 math/lgsFp.cpp (limited to 'math/lgsFp.cpp') diff --git a/math/lgsFp.cpp b/math/lgsFp.cpp new file mode 100644 index 0000000..e42e4ab --- /dev/null +++ b/math/lgsFp.cpp @@ -0,0 +1,27 @@ +void normalLine(ll n, ll line, ll p) { //normalisiert Zeile line + ll factor = multInv(mat[line][line], p); //Implementierung von oben + for (ll 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++) { + if (i == line) continue; + ll diff = mat[i][line]; //abziehen + for (ll j = 0; j <= n; j++) { + mat[i][j] -= (diff * mat[line][j]) % p; + while (mat[i][j] < 0) { + mat[i][j] += p; + } + } + } +} + +void gauss(ll n, ll p) { //n x n+1-Matrix, Koerper F_p + for (ll line = 0; line < n; line++) { + normalLine(n, line, p); + takeAll(n, line, p); + } +} \ No newline at end of file -- cgit v1.2.3