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

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	UnivariateDivision.InverseModMonomial<Poly extends IUnivariatePolynomial<Poly>>	Holds poly^(-1) mod x^i

Method Summary

Modifier and Type	Method	Description
static <E> UnivariatePolynomial<E>[]	divideAndRemainder(UnivariatePolynomial<E> dividend, UnivariatePolynomial<E> divider, boolean copy)	Returns quotient and remainder.
static UnivariatePolynomialZ64[]	divideAndRemainder(UnivariatePolynomialZ64 dividend, UnivariatePolynomialZ64 divider, boolean copy)	Returns {quotient, remainder} or null if the division is not possible.
static UnivariatePolynomialZp64[]	divideAndRemainder(UnivariatePolynomialZp64 dividend, UnivariatePolynomialZp64 divider, boolean copy)	Returns quotient and remainder.
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.
static <E> UnivariatePolynomial<E>[]	divideAndRemainderClassic(UnivariatePolynomial<E> dividend, UnivariatePolynomial<E> divider, boolean copy)	Classical algorithm for division with remainder.
static UnivariatePolynomialZp64[]	divideAndRemainderClassic(UnivariatePolynomialZp64 dividend, UnivariatePolynomialZp64 divider, boolean copy)	Classical algorithm for division with remainder.
static <E> UnivariatePolynomial<E>[]	divideAndRemainderFast(UnivariatePolynomial<E> dividend, UnivariatePolynomial<E> divider, boolean copy)	Fast algorithm for division with remainder using Newton's iteration.
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.
static UnivariatePolynomialZp64[]	divideAndRemainderFast(UnivariatePolynomialZp64 dividend, UnivariatePolynomialZp64 divider, boolean copy)	Fast algorithm for division with remainder using Newton's iteration.
static UnivariatePolynomialZp64[]	divideAndRemainderFast(UnivariatePolynomialZp64 dividend, UnivariatePolynomialZp64 divider, UnivariateDivision.InverseModMonomial<UnivariatePolynomialZp64> invMod, boolean copy)	Fast algorithm for division with remainder using Newton's iteration.
static <Poly extends IUnivariatePolynomial<Poly>> Poly[]	divideAndRemainderFast(Poly dividend, Poly divider, UnivariateDivision.InverseModMonomial<Poly> invMod, boolean copy)	Returns {quotient, remainder} of dividend and divider
static <Poly extends IUnivariatePolynomial<Poly>> Poly[]	divideAndRemainderFast0(Poly dividend, Poly divider, UnivariateDivision.InverseModMonomial<Poly> invRevMod, boolean copy)	fast division implementation
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
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
static <Poly extends IUnivariatePolynomial<Poly>> UnivariateDivision.InverseModMonomial<Poly>	fastDivisionPreConditioning(Poly divider)	Prepares rev(divider)^(-1) mod x^i for fast division.
static <Poly extends IUnivariatePolynomial<Poly>> UnivariateDivision.InverseModMonomial<Poly>	fastDivisionPreConditioningWithLCCorrection(Poly divider)	Prepares rev(divider)^(-1) mod x^i for fast division.
static <E> UnivariatePolynomial<E>[]	pseudoDivideAndRemainder(UnivariatePolynomial<E> dividend, UnivariatePolynomial<E> divider, boolean copy)	Returns quotient and remainder using pseudo division.
static UnivariatePolynomialZ64[]	pseudoDivideAndRemainder(UnivariatePolynomialZ64 dividend, UnivariatePolynomialZ64 divider, boolean copy)	Returns quotient and remainder using pseudo division.
static <Poly extends IUnivariatePolynomial<Poly>> Poly[]	pseudoDivideAndRemainder(Poly dividend, Poly divider, boolean copy)	Returns quotient and remainder of dividend and divider using pseudo division.
static <E> UnivariatePolynomial<E>	quotient(UnivariatePolynomial<E> dividend, UnivariatePolynomial<E> divider, boolean copy)	Returns quotient of dividend and divider.
static UnivariatePolynomialZ64	quotient(UnivariatePolynomialZ64 dividend, UnivariatePolynomialZ64 divider, boolean copy)	Returns quotient dividend/ divider
static UnivariatePolynomialZp64	quotient(UnivariatePolynomialZp64 dividend, UnivariatePolynomialZp64 divider, boolean copy)	Returns quotient of dividing dividend by divider.
static <Poly extends IUnivariatePolynomial<Poly>> Poly	quotient(Poly dividend, Poly divider, boolean copy)	Returns quotient dividend/ divider or null if exact division o
static <E> UnivariatePolynomial<E>	quotientFast(UnivariatePolynomial<E> dividend, UnivariatePolynomial<E> divider, UnivariateDivision.InverseModMonomial<UnivariatePolynomial<E>> invMod, boolean copy)	Fast quotient using Newton's iteration.
static UnivariatePolynomialZp64	quotientFast(UnivariatePolynomialZp64 dividend, UnivariatePolynomialZp64 divider, UnivariateDivision.InverseModMonomial<UnivariatePolynomialZp64> invMod, boolean copy)	Fast quotient using Newton's iteration.
static <E> UnivariatePolynomial<E>	remainder(UnivariatePolynomial<E> dividend, UnivariatePolynomial<E> divider, boolean copy)	Returns remainder of dividend and divider.
static UnivariatePolynomialZ64	remainder(UnivariatePolynomialZ64 dividend, UnivariatePolynomialZ64 divider, boolean copy)	Returns remainder of dividend and divider or null if division is not possible.
static UnivariatePolynomialZp64	remainder(UnivariatePolynomialZp64 dividend, UnivariatePolynomialZp64 divider, boolean copy)	Returns remainder of dividing dividend by divider.
static <Poly extends IUnivariatePolynomial<Poly>> Poly	remainder(Poly dividend, Poly divider, boolean copy)	Returns remainder of dividend and divider.
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
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.
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.
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.
static <T extends IUnivariatePolynomial<T>> T	remainderMonomial(T dividend, int xDegree, boolean copy)	Returns the remainder of dividend and monomial x^xDegree

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

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