php - GF2 代码的高斯消除
问题描述
我有这个 gauss_eliminate 函数,但不是处理实数,而是希望它处理二进制值。我需要 GF2 gauss_eliminate 函数,其中输入为二进制,输出为二进制。这会产生实际值,而不是二进制值,例如 0.57142857142857 0.71428571428571 -0.42857142857143 -0.28571428571429 0.14285714285714
高斯消元法有以下 3 个允许的步骤:1)交换两行(以实现某种外观) 2)将一行乘以一个非零数,3)将一行的倍数添加到另一行。-- 在 GF2: 加法运算是 XOR : 0+0=0, 0+1=1, 1+0=1, 1+1=0 --and-- 乘法是 AND 运算: 0*0=0,0 *1=0,1*0=0,1*1=1
function gauss_eliminate($A, $b, $N)
{
for ($col = 0; $col < $N; $col++) {
$j = $col;
$max = $A[$j][$j];
for ($i = $col + 1; $i < $N; $i++) {
$tmp = abs($A[$i][$col]);
if ($tmp > $max) {
$j = $i;
$max = $tmp;
}
}
swap_rows($A, $b, $col, $j);
for ($i = $col + 1; $i < $N; $i++) {
$tmp = $A[$i][$col] / $A[$col][$col];
for ($j = $col + 1; $j < $N; $j++) $A[$i][$j] -= $tmp * $A[$col][$j];
$A[$i][$col] = 0;
$b[$i] -= $tmp * $b[$col];
}
}
$x = array();
for ($col = $N - 1; $col >= 0; $col--) {
$tmp = $b[$col];
for ($j = $N - 1; $j > $col; $j--) $tmp -= $x[$j] * $A[$col][$j];
$x[$col] = $tmp / $A[$col][$col];
}
return $x;
}
新代码#1,仍然不起作用:
function gauss_eliminate($A, $b, $N)
{
for ($col = 0; $col < $N; $col++) {
$j = $col;
$max = $A[$j][$j];
for ($i = $col + 1; $i < $N; $i++) {
$tmp = abs($A[$i][$col]);
if ($tmp > $max) {
$j = $i;
$max = $tmp;
}
}
swap_rows($A, $b, $col, $j);
for ($i = $col + 1; $i < $N; $i++) {
for ($j = $col + 1; $j < $N; $j++)
$A[$i][$j]=( $A[$i][$j] != $A[$col][$j] ) ? 1 : 0;
$A[$i][$col] = 0;
$b[$i]=( $b[$i] != $b[$col] ) ? 1 : 0;
}
}
$x = array();
for ($col = $N - 1; $col >= 0; $col--) {
# $tmp = $b[$col];
# for ($j = $N - 1; $j > $col; $j--) $tmp -= $x[$j] * $A[$col][$j];
$x[$col] = ( $x[$col] != $A[$col][$j] ) ? 1 : 0;
}
return $x;
}
新代码 #2 - 仍然无法正常工作 - tmp setup to alter
function gauss_eliminate($A, $b, $N)
{
for ($col = 0; $col < $N; $col++) {
$j = $col;
$max = $A[$j][$j];
for ($i = $col + 1; $i < $N; $i++) {
$tmp = abs($A[$i][$col]);
if ($tmp > $max) { $j = $i; $max = $tmp; }
}
swap_rows($A, $b, $col, $j);
for ($i = $col + 1; $i < $N; $i++) {
# $tmp = $A[$i][$col] / $A[$col][$col];
for ($j = $col + 1; $j < $N; $j++) $A[$i][$j]=($A[$i][$j] != $A[$col][$j] ? 1 : 0);
$A[$i][$col] = 0;
$b[$i] = ( $b[$i] != $b[$col] ? 1 : 0);
}
}
$x = array();
for ($col = $N - 1; $col >= 0; $col--) {
$tmp = $b[$col];
for ($j = $N - 1; $j > $col; $j--) $tmp = 1 - $tmp;
$x[$col] = ($tmp != $A[$col][$j] ? 1 : 0);
}
return $x;
}
解决方案
看来我找到了正确的语法。在以一种有意义的方式修改代码之后,我得到了一个示例的正确结果......将 - 转换为 +,并将 + 转换为 XOR,而 / 被忽略,* 是 AND。仍然很高兴确认此代码是正确的。
function gauss_eliminate($A, $b, $N) {
for ($col = 0; $col < $N; $col++) {
$j = $col;
$max = $A[$j][$j];
for ($i = $col + 1; $i < $N; $i++) {
$tmp = abs($A[$i][$col]);
if ($tmp > $max) {
$j = $i;
$max = $tmp;
}
}
swap_rows($A, $b, $col, $j);
for ($i = $col + 1; $i < $N; $i++) {
# $tmp = $A[$i][$col] / $A[$col][$col];
# for ($j = $col + 1; $j < $N; $j++) {
# $A[$i][$j] -= $tmp * $A[$col][$j];
# }
# $A[$i][$col] = 0;
# $b[$i] -= $tmp * $b[$col];
$tmp = $A[$i][$col];
for ($j = $col + 1; $j < $N; $j++) {
# $A[$i][$j] = $A[$i][$j] + ( $tmp * $A[$col][$j] );
$A[$i][$j] = ( $A[$i][$j] != ( $tmp && $A[$col][$j] ) ) ? 1 : 0;
}
$A[$i][$col] = 0;
# $b[$i] = $b[$i] + ($tmp * $b[$col]);
$b[$i] = ( $b[$i] != ($tmp && $b[$col]) ) ? 1 : 0;
}
}
$x = array();
for ($col = $N - 1; $col >= 0; $col--) {
$tmp = $b[$col];
for ($j = $N - 1; $j > $col; $j--) {
# $tmp -= $x[$j] * $A[$col][$j];
# $tmp = $tmp + ($x[$j] * $A[$col][$j]);
$tmp = ( $tmp != ($x[$j] && $A[$col][$j]) ) ? 1 : 0;
}
# $x[$col] = $tmp / $A[$col][$col];
$x[$col] = $tmp;
}
return $x;
}
注释文本是旧的(非 GF2 代码)以及显示我将 + 转换为 XOR、* 转换为 AND 等的“中间步骤”
推荐阅读
- c# - 如何在 xamarin MVVM 中将数据从 content-page.cs 发送到 tabbed-page.cs?
- ios - 每 5 分钟附近的 messageLostHandler 事件
- hbase - Hbase:如何使用来自源 Hbase 表的数据将列族添加到 Target-Hbase 表
- r - 如何在数据框之间获取一列相同且另一列相似的行?
- php - 使用 glob 和 array_slice 时排除文件名
- python - 如何使用 Python 下载股票价格数据?
- mysql - 选择耗时 8 秒。改进想法
- c# - 由数据库填充时,组合框将值加倍
- haskell - 未将类型识别为变压器堆栈内的单子的关联类型
- php - nusoap 未定义索引在 nusoap.php 上线