Package it.unimi.dsi.sux4j.mph.solve
Class Modulo3System.Modulo3Equation
java.lang.Object
it.unimi.dsi.sux4j.mph.solve.Modulo3System.Modulo3Equation
- Enclosing class:
- Modulo3System
An equation on F3.
-
Field Summary
Modifier and TypeFieldDescriptionprotected final long[]
Thebv.bits()
, cached.protected final LongArrayBitVector
The vector representing the coefficients (two bits for each variable).protected long
The constant term.protected int
The first coefficient.protected int
The first variable.protected final LongBigList
A 2-bit list view ofbitVector
, cached. -
Constructor Summary
ModifierConstructorDescriptionModulo3Equation
(long c, int numVars) Creates a new equation.protected
Modulo3Equation
(Modulo3System.Modulo3Equation equation) -
Method Summary
Modifier and TypeMethodDescriptionadd
(int variable) Adds a new variable with coefficient equal to one.add
(int variable, int coefficient) Adds a new variable with given coefficient.protected static final long
addMod3
(long x, long y) Adds two 64-bit words made of 2-bit fields containing 00, 01 or 10, interpreted as values mod 3.int[]
Returns an array containing the coefficients in variable increasing order.copy()
eliminate
(int var, Modulo3System.Modulo3Equation equation) Eliminates the given variable from this equation, using the provided equation, by subtracting it multiplied by a suitable constant.boolean
int
hashCode()
boolean
boolean
void
normalized
(long[] result) Writes in the provided array a normalized (all coefficients turned into ones) version of the bit vector representing the equation.static int
scalarProduct
(long[] x, long[] y) Returns the modulo-3 scalar product of the two provided bit vectors.void
sub
(Modulo3System.Modulo3Equation equation, int mul) Subtract from this equation another equation multiplied by a provided constant.protected static final long
subMod3
(long x, long y) Subtracts two 64-bit words made of 2-bit fields containing 00, 01 or 10, interpreted as values mod 3.toString()
void
Updates the information contained infirstVar
andfirstCoeff
.int[]
Returns an array containing the variables in increasing order.
-
Field Details
-
bitVector
The vector representing the coefficients (two bits for each variable). -
bits
protected final long[] bitsThebv.bits()
, cached. -
list
A 2-bit list view ofbitVector
, cached. -
c
protected long cThe constant term. -
firstVar
protected int firstVarThe first variable. It isInteger.MAX_VALUE
if the first variable is not known. This field must be updated byupdateFirstVar()
to be meaningful. -
firstCoeff
protected int firstCoeffThe first coefficient. This field must be updated byupdateFirstVar()
to be meaningful.
-
-
Constructor Details
-
Modulo3Equation
public Modulo3Equation(long c, int numVars) Creates a new equation.- Parameters:
c
- the constant term.numVars
- the number of variables.
-
Modulo3Equation
-
-
Method Details
-
add
Adds a new variable with given coefficient.- Parameters:
variable
- a variable.coefficient
- its coefficient.- Returns:
- this equation.
- Throws:
IllegalStateException
- if you try to add twice the same variable.
-
add
Adds a new variable with coefficient equal to one.- Parameters:
variable
- a variable.- Returns:
- this equation.
-
variables
public int[] variables()Returns an array containing the variables in increasing order.Mainly for debugging purposes.
- Returns:
- an array containing the variables in increasing order.
- See Also:
-
coefficients
public int[] coefficients()Returns an array containing the coefficients in variable increasing order.Mainly for debugging purposes.
- Returns:
- an array, parallel to that returned by
variables()
, containing the coefficients in variable increasing order. - See Also:
-
eliminate
Eliminates the given variable from this equation, using the provided equation, by subtracting it multiplied by a suitable constant.- Parameters:
var
- a variable.equation
- an equation in whichvar
appears.- Returns:
- this equation.
-
sub
Subtract from this equation another equation multiplied by a provided constant.- Parameters:
equation
- the subtrahend.mul
- a multiplier that will be applied to the subtrahend.
-
addMod3
protected static final long addMod3(long x, long y) Adds two 64-bit words made of 2-bit fields containing 00, 01 or 10, interpreted as values mod 3.- Parameters:
x
- a 64-bit word made of modulo-3 2-bit fields.y
- a 64-bit word made of modulo-3 2-bit fields.- Returns:
- the field-by-field mod 3 sum of
x
andy
.
-
subMod3
protected static final long subMod3(long x, long y) Subtracts two 64-bit words made of 2-bit fields containing 00, 01 or 10, interpreted as values mod 3.- Parameters:
x
- a 64-bit word made of modulo-3 2-bit fields.y
- a 64-bit word made of modulo-3 2-bit fields.- Returns:
- the field-by-field mod 3 difference of
x
andy
.
-
updateFirstVar
public void updateFirstVar()Updates the information contained infirstVar
andfirstCoeff
. -
isUnsolvable
public boolean isUnsolvable() -
isIdentity
public boolean isIdentity() -
hashCode
public int hashCode() -
equals
-
normalized
public void normalized(long[] result) Writes in the provided array a normalized (all coefficients turned into ones) version of the bit vector representing the equation.- Parameters:
result
- an array where the result will be stored; must be long at least asbits
.
-
scalarProduct
public static int scalarProduct(long[] x, long[] y) Returns the modulo-3 scalar product of the two provided bit vectors.This implementation was suggested by Djamal Belazzougui.
- Parameters:
x
- a bit vector represented as an array of longs.y
- a bit vector represented as an array of longs.- Returns:
- the modulo-3 scalar product of
x
and {code y}, unnormalized (might be larger than 2).
-
toString
-
copy
-