如何实现对二元方程的高斯消去 [英] how to implementing gaussian elimination for binary equations
问题描述
我有这个方程组 1 =x⊕y⊕z
1 =x⊕y⊕w
0 =x⊕w⊕z
1 =w⊕y⊕z
我正在尝试实施高斯消去法来解决此系统,如
i have this system of equations
1=x⊕y⊕z
1=x⊕y⊕w
0=x⊕w⊕z
1=w⊕y⊕z
I'm trying to implement gaussian elimination to solve this system as described here , replacing division,subtraction and multiplication by XOR, but it gives my wrong answer..the correct answer is (x,y,z,w)=(0,1,0,0)
what am i doing wrong ?
public static void ComputeCoefficents(byte[,] X, byte[] Y)
{
int I, J, K, K1, N;
N = Y.Length;
for (K = 0; K < N; K++)
{
K1 = K + 1;
for (I = K; I < N; I++)
{
if (X[I, K] != 0)
{
for (J = K1; J < N; J++)
{
X[I, J] /= X[I, K];
}
//Y[I] /= X[I, K];
Y[I] ^= X[I, K];
}
}
for (I = K1; I < N; I++)
{
if (X[I, K] != 0)
{
for (J = K1; J < N; J++)
{
X[I, J] ^= X[K, J];
}
Y[I] ^= Y[K];
}
}
}
for (I = N - 2; I >= 0; I--)
{
for (J = N - 1; J >= I + 1; J--)
{
//Y[I] -= AndOperation(X[I, J], Y[J]);
Y[I] ^= (byte)(X[I, J]* Y[J]);
}
}
}
推荐答案
我认为您正在尝试为此应用高斯消除模2.
I think you're trying to apply Gaussian elimination mod 2 for this.
通常,如果您的方程式为以下形式,则可以进行高斯消除模k
In general you can do Gaussian elimination mod k, if your equations are of the form
a_1 * x + b_1 * y + c_1 * z = d_1
a_2 * x + b_2 * y + c_2 * z = d_2
a_3 * x + b_3 * y + c_3 * z = d_3
a_4 * x + b_4 * y + c_4 * z = d_4
在Z2中,*是and
,而+是xor
,因此您可以使用高斯消去法来求解形式为
And in Z2 * is and
and + is xor
, so you can use Gausian elimination to solve equations of the form
x (xor) y (xor) z = 1
x (xor) y (xor) w = 1
x (xor) z (xor) w = 0
y (xor) z (xor) w = 1
让我们用高斯消去法手工做这个方程.
Lets do this equation using Gausian elimination by hand.
对应的增强矩阵为:
1 1 1 0 | 1
1 1 0 1 | 1
1 0 1 1 | 0
0 1 1 1 | 1
1 1 1 0 | 1
0 0 1 1 | 0 (R2 = R2 + R1)
0 1 0 1 | 1 (R3 = R3 + R1)
0 1 1 1 | 1
1 1 1 0 | 1
0 1 1 1 | 1 (R2 = R4)
0 1 0 1 | 1
0 0 1 1 | 0 (R4 = R2)
1 0 0 1 | 0 (R1 = R1 + R2)
0 1 1 1 | 1
0 0 1 0 | 0 (R3 = R3 + R2)
0 0 1 1 | 0
1 0 0 1 | 0
0 1 0 1 | 1 (R2 = R2 + R3)
0 0 1 0 | 0
0 0 0 1 | 0 (R4 = R4 + R3)
1 0 0 0 | 0 (R1 = R1 + R4)
0 1 0 0 | 1 (R2 = R2 + R4)
0 0 1 0 | 0
0 0 0 1 | 0
给出(x,y,z,w)=(0,1,0,0)的解.
Giving your solution of (x,y,z,w) = (0,1,0,0).
但这需要行透视-我在您的代码中看不到.
But this requires row pivoting - which I can't see in your code.
您的代码中还存在一些可能不需要的乘法和除法运算.我希望代码看起来像这样:(您需要修复TODO).
There's also some multiplications and divisions floating around in your code that probably dont need to be there. I'd expect the code to look like this: (You'll need to fix the TODOs).
public static void ComputeCoefficents(byte[,] X, byte[] Y) {
int I, J, K, K1, N;
N = Y.Length;
for (K = 0; K < N; K++) {
//First ensure that we have a non-zero entry in X[K,K]
if( X[K,K] == 0 ) {
for(int i = 0; i<N ; ++i ) {
if(X[i,K] != 0 ) {
for( ... ) //TODO: A loop to swap the entries
//TODO swap entries in Y too
}
}
if( X[K,K] == 0 ) {
// TODO: Handle the case where we have a zero column
// - for now we just move on to the next column
// - This means we have no solutions or multiple
// solutions
continue
}
// Do full row elimination.
for( int I = 0; I<N; ++I)
{
if( I!=K ){ //Don't self eliminate
if( X[I,K] ) {
for( int J=K; J<N; ++J ) { X[I,J] = X[I,J] ^ X[K,J]; }
Y[J] = Y[J] ^ Y[K];
}
}
}
}
//Now assuming we didnt hit any zero columns Y should be our solution.
}
这篇关于如何实现对二元方程的高斯消去的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!