Class Modulo3System.Modulo3Equation

  • Enclosing class:
    Modulo3System

    protected static class Modulo3System.Modulo3Equation
    extends java.lang.Object
    An equation on F3.
    • Field Detail

      • bitVector

        protected final it.unimi.dsi.bits.LongArrayBitVector bitVector
        The vector representing the coefficients (two bits for each variable).
      • bits

        protected final long[] bits
        The bv.bits(), cached.
      • list

        protected final it.unimi.dsi.fastutil.longs.LongBigList list
        A 2-bit list view of bitVector, cached.
      • c

        protected long c
        The constant term.
      • firstVar

        protected int firstVar
        The first variable. It is Integer.MAX_VALUE if the first variable is not known. This field must be updated by updateFirstVar() to be meaningful.
      • firstCoeff

        protected int firstCoeff
        The first coefficient. This field must be updated by updateFirstVar() to be meaningful.
    • Constructor Detail

      • Modulo3Equation

        public Modulo3Equation​(long c,
                               int numVars)
        Creates a new equation.
        Parameters:
        c - the constant term.
        numVars - the number of variables.
    • Method Detail

      • add

        public Modulo3System.Modulo3Equation add​(int variable,
                                                 int coefficient)
        Adds a new variable with given coefficient.
        Parameters:
        variable - a variable.
        coefficient - its coefficient.
        Returns:
        this equation.
        Throws:
        java.lang.IllegalStateException - if you try to add twice the same variable.
      • add

        public Modulo3System.Modulo3Equation add​(int variable)
        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()
      • 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:
        variables()
      • eliminate

        public Modulo3System.Modulo3Equation 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.
        Parameters:
        var - a variable.
        equation - an equation in which var appears.
        Returns:
        this equation.
      • sub

        public void sub​(Modulo3System.Modulo3Equation equation,
                        int mul)
        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 and y.
      • 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 and y.
      • updateFirstVar

        public void updateFirstVar()
        Updates the information contained in firstVar and firstCoeff.
      • isUnsolvable

        public boolean isUnsolvable()
      • isIdentity

        public boolean isIdentity()
      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class java.lang.Object
      • equals

        public boolean equals​(java.lang.Object o)
        Overrides:
        equals in class java.lang.Object
      • 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 as bits.
      • 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

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object