Package cc.redberry.rings.poly.univar

Class UnivariateDivision

java.lang.Object
cc.redberry.rings.poly.univar.UnivariateDivision
public final class UnivariateDivision
extends Object
Division with remainder of univariate polynomials.
Since:
1.0

  • Method Details

    • remainderMonomial

      public static <T extends IUnivariatePolynomial<T>> T remainderMonomial​(T dividend, int xDegree, boolean copy)
      Returns the remainder of dividend and monomial x^xDegree
      Parameters:
      dividend - the dividend
      xDegree - monomial degree
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      the remainder

    • divideAndRemainder

      public static UnivariatePolynomialZ64[] divideAndRemainder​(UnivariatePolynomialZ64 dividend, UnivariatePolynomialZ64 divider, boolean copy)
      Returns {quotient, remainder} or null if the division is not possible.
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      {quotient, remainder} or null if the division is not possible

    • pseudoDivideAndRemainder

      public static UnivariatePolynomialZ64[] pseudoDivideAndRemainder​(UnivariatePolynomialZ64 dividend, UnivariatePolynomialZ64 divider, boolean copy)
      Returns quotient and remainder using pseudo division.
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      {quotient, remainder}

    • remainder

      public static UnivariatePolynomialZ64 remainder​(UnivariatePolynomialZ64 dividend, UnivariatePolynomialZ64 divider, boolean copy)
      Returns remainder of dividend and divider or null if division is not possible.
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      the remainder or null if division is not possible

    • quotient

      public static UnivariatePolynomialZ64 quotient​(UnivariatePolynomialZ64 dividend, UnivariatePolynomialZ64 divider, boolean copy)
      Returns quotient dividend/ divider
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      the quotient

    • divideAndRemainder

      public static UnivariatePolynomialZp64[] divideAndRemainder​(UnivariatePolynomialZp64 dividend, UnivariatePolynomialZp64 divider, boolean copy)
      Returns quotient and remainder.
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      {quotient, remainder}

    • divideAndRemainderClassic

      public static UnivariatePolynomialZp64[] divideAndRemainderClassic​(UnivariatePolynomialZp64 dividend, UnivariatePolynomialZp64 divider, boolean copy)
      Classical algorithm for division with remainder.
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      {quotient, remainder}

    • divideAndRemainder

      public static <E> UnivariatePolynomial<E>[] divideAndRemainder​(UnivariatePolynomial<E> dividend, UnivariatePolynomial<E> divider, boolean copy)
      Returns quotient and remainder.
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      {quotient, remainder}

    • pseudoDivideAndRemainder

      public static <E> UnivariatePolynomial<E>[] pseudoDivideAndRemainder​(UnivariatePolynomial<E> dividend, UnivariatePolynomial<E> divider, boolean copy)
      Returns quotient and remainder using pseudo division.
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      {quotient, remainder}

    • divideAndRemainderClassic

      public static <E> UnivariatePolynomial<E>[] divideAndRemainderClassic​(UnivariatePolynomial<E> dividend, UnivariatePolynomial<E> divider, boolean copy)
      Classical algorithm for division with remainder.
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      {quotient, remainder}

    • fastDivisionPreConditioning

      public static <Poly extends IUnivariatePolynomial<Poly>> UnivariateDivision.InverseModMonomial<Poly> fastDivisionPreConditioning​(Poly divider)
      Prepares rev(divider)^(-1) mod x^i for fast division.
      Parameters:
      divider - the divider

    • fastDivisionPreConditioningWithLCCorrection

      public static <Poly extends IUnivariatePolynomial<Poly>> UnivariateDivision.InverseModMonomial<Poly> fastDivisionPreConditioningWithLCCorrection​(Poly divider)
      Prepares rev(divider)^(-1) mod x^i for fast division.
      Parameters:
      divider - the divider

    • divideAndRemainderFast0

      public static <Poly extends IUnivariatePolynomial<Poly>> Poly[] divideAndRemainderFast0​(Poly dividend, Poly divider, UnivariateDivision.InverseModMonomial<Poly> invRevMod, boolean copy)
      fast division implementation

    • divideAndRemainderFast

      public static UnivariatePolynomialZp64[] divideAndRemainderFast​(UnivariatePolynomialZp64 dividend, UnivariatePolynomialZp64 divider, boolean copy)
      Fast algorithm for division with remainder using Newton's iteration.
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      {quotient, remainder}

    • divideAndRemainderFast

      public static UnivariatePolynomialZp64[] divideAndRemainderFast​(UnivariatePolynomialZp64 dividend, UnivariatePolynomialZp64 divider, UnivariateDivision.InverseModMonomial<UnivariatePolynomialZp64> invMod, boolean copy)
      Fast algorithm for division with remainder using Newton's iteration.
      Parameters:
      dividend - the dividend
      divider - the divider
      invMod - pre-conditioned divider (fastDivisionPreConditioning(divider))
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      {quotient, remainder}

    • divideAndRemainderFast

      public static <E> UnivariatePolynomial<E>[] divideAndRemainderFast​(UnivariatePolynomial<E> dividend, UnivariatePolynomial<E> divider, boolean copy)
      Fast algorithm for division with remainder using Newton's iteration.
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      {quotient, remainder}

    • divideAndRemainderFast

      public static <E> UnivariatePolynomial<E>[] divideAndRemainderFast​(UnivariatePolynomial<E> dividend, UnivariatePolynomial<E> divider, UnivariateDivision.InverseModMonomial<UnivariatePolynomial<E>> invMod, boolean copy)
      Fast algorithm for division with remainder using Newton's iteration.
      Parameters:
      dividend - the dividend
      divider - the divider
      invMod - pre-conditioned divider (fastDivisionPreConditioning(divider))
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      {quotient, remainder}

    • remainder

      public static UnivariatePolynomialZp64 remainder​(UnivariatePolynomialZp64 dividend, UnivariatePolynomialZp64 divider, boolean copy)
      Returns remainder of dividing dividend by divider.
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      the remainder

    • remainderFast

      public static UnivariatePolynomialZp64 remainderFast​(UnivariatePolynomialZp64 dividend, UnivariatePolynomialZp64 divider, UnivariateDivision.InverseModMonomial<UnivariatePolynomialZp64> invMod, boolean copy)
      Fast remainder using Newton's iteration with switch to classical remainder for small polynomials.
      Parameters:
      dividend - the dividend
      divider - the divider
      invMod - pre-conditioned divider (fastDivisionPreConditioning(divider))
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      the remainder

    • quotient

      public static UnivariatePolynomialZp64 quotient​(UnivariatePolynomialZp64 dividend, UnivariatePolynomialZp64 divider, boolean copy)
      Returns quotient of dividing dividend by divider.
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      the quotient

    • quotientFast

      public static UnivariatePolynomialZp64 quotientFast​(UnivariatePolynomialZp64 dividend, UnivariatePolynomialZp64 divider, UnivariateDivision.InverseModMonomial<UnivariatePolynomialZp64> invMod, boolean copy)
      Fast quotient using Newton's iteration.
      Parameters:
      dividend - the dividend
      divider - the divider
      invMod - pre-conditioned divider (fastDivisionPreConditioning(divider))
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      the quotient

    • remainder

      public static <E> UnivariatePolynomial<E> remainder​(UnivariatePolynomial<E> dividend, UnivariatePolynomial<E> divider, boolean copy)
      Returns remainder of dividend and divider.
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      the remainder

    • remainderFast

      public static <E> UnivariatePolynomial<E> remainderFast​(UnivariatePolynomial<E> dividend, UnivariatePolynomial<E> divider, UnivariateDivision.InverseModMonomial<UnivariatePolynomial<E>> invMod, boolean copy)
      Fast remainder using Newton's iteration with switch to classical remainder for small polynomials.
      Parameters:
      dividend - the dividend
      divider - the divider
      invMod - pre-conditioned divider (fastDivisionPreConditioning(divider))
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      the remainder

    • quotient

      public static <E> UnivariatePolynomial<E> quotient​(UnivariatePolynomial<E> dividend, UnivariatePolynomial<E> divider, boolean copy)
      Returns quotient of dividend and divider.
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      the quotient

    • quotientFast

      public static <E> UnivariatePolynomial<E> quotientFast​(UnivariatePolynomial<E> dividend, UnivariatePolynomial<E> divider, UnivariateDivision.InverseModMonomial<UnivariatePolynomial<E>> invMod, boolean copy)
      Fast quotient using Newton's iteration.
      Parameters:
      dividend - the dividend
      divider - the divider
      invMod - pre-conditioned divider (fastDivisionPreConditioning(divider))
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      the quotient

    • pseudoDivideAndRemainder

      public static <Poly extends IUnivariatePolynomial<Poly>> Poly[] pseudoDivideAndRemainder​(Poly dividend, Poly divider, boolean copy)
      Returns quotient and remainder of dividend and divider using pseudo division.
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      {quotient, remainder}

    • divideAndRemainder

      public static <Poly extends IUnivariatePolynomial<Poly>> Poly[] divideAndRemainder​(Poly dividend, Poly divider, boolean copy)
      Returns {quotient, remainder} of dividend and divider or null if the division is not possible.
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      {quotient, remainder} or null if the division is not possible

    • divideAndRemainderFast

      public static <Poly extends IUnivariatePolynomial<Poly>> Poly[] divideAndRemainderFast​(Poly dividend, Poly divider, UnivariateDivision.InverseModMonomial<Poly> invMod, boolean copy)
      Returns {quotient, remainder} of dividend and divider
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      invMod - precomputed Newton inverses
      Returns:
      {quotient, remainder} or null if the division is not possible

    • divideExact

      public static <Poly extends IUnivariatePolynomial<Poly>> Poly divideExact​(Poly dividend, Poly divider, boolean copy)
      Divides dividend by divider or throws ArithmeticException if exact division is not possible
      Parameters:
      dividend - the dividend
      divider - the divider
      Returns:
      dividend / divider
      Throws:
      ArithmeticException - if exact division is not possible

    • divideOrNull

      public static <Poly extends IUnivariatePolynomial<Poly>> Poly divideOrNull​(Poly dividend, Poly divider, boolean copy)
      Divides dividend by divider or returns null if exact division is not possible
      Parameters:
      dividend - the dividend
      divider - the divider
      Returns:
      dividend / divider or null if exact division is not possible

    • remainder

      public static <Poly extends IUnivariatePolynomial<Poly>> Poly remainder​(Poly dividend, Poly divider, boolean copy)
      Returns remainder of dividend and divider.
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      the remainder

    • quotient

      public static <Poly extends IUnivariatePolynomial<Poly>> Poly quotient​(Poly dividend, Poly divider, boolean copy)
      Returns quotient dividend/ divider or null if exact division o
      Parameters:
      dividend - the dividend
      divider - the divider
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      the quotient

    • remainderFast

      public static <Poly extends IUnivariatePolynomial<Poly>> Poly remainderFast​(Poly dividend, Poly divider, UnivariateDivision.InverseModMonomial<Poly> invMod, boolean copy)
      Fast remainder using Newton's iteration with switch to classical remainder for small polynomials.
      Parameters:
      dividend - the dividend
      divider - the divider
      invMod - pre-conditioned divider (fastDivisionPreConditioning(divider))
      copy - whether to clone dividend; if not, the remainder will be placed directly to dividend and dividend data will be lost
      Returns:
      the remainder

    • remainderCoefficientBound

      public static <E> E remainderCoefficientBound​(UnivariatePolynomial<E> dividend, UnivariatePolynomial<E> divider)
      Gives an upper bound on the coefficients of remainder of division of dividend by divider
      Parameters:
      dividend - the dividend
      divider - the divider
      Returns:
      upper bound on the coefficients of remainder