1 #ifndef _UNIPOLYNOMIAL_H_ 2 #define _UNIPOLYNOMIAL_H_ 5 #include "../DyadicRationalNumber/globals.h" 6 #include "../DyadicRationalNumber/Multiplication/multiplication.h" 7 #include "../Interval/interval.h" 10 void ts_modulo (lfixz*, lfixz, lfixz,
int);
24 for (
int i = 0; i < n; ++i)
29 void taylorShiftCVL();
33 void taylorShiftDnC(
int,
int);
37 void taylorShiftDnC(
int);
38 void binomials(lfixz*,
int);
39 void taylorShiftBasePower2(lfixz*,
int);
42 void taylorShiftIncrementalCilkFor(lfixq*,
int,
int);
43 void tableauBase(lfixq*,
int);
44 void polygonBase(lfixq*,
int,
int,
int);
45 void taylorShiftBase(lfixq*,
int);
46 void taylorShift3RegularCilkFor(lfixq*,
int,
int);
49 void taylorShiftTableau(
int);
50 void taylorShiftBase(lfixq*, lfixq*,
int);
51 void tableauBaseInplace(lfixq*, lfixq*,
int,
int);
52 void tableauConstruction(lfixq*, lfixq*,
int,
int,
int);
53 void taylorShiftGeneral(lfixq*, lfixq*,
int,
int);
56 lfixz positiveRootBound();
57 lfixz cauchyRootBound();
58 lfixz complexRootBound();
62 long taylorConstant(
int, lfixz,
int, lfixz);
82 static RingProperties properties;
102 if (s < 1) { s = 1; }
118 coef[0] = mpq_class(e.get_mpz());
123 coef[0] = mpq_class(e.get_mpq());
134 std::copy(b.coef, b.coef+n, coef);
165 for (
size_t i = 0; i <= curd; ++i) {
173 inline Integer numberOfTerms()
const {
175 for (
size_t i = 0; i <= curd; ++i) {
191 std::cout <<
"BPAS: warning, try to access a non-exist coefficient " << k <<
" from DUQP(" << n <<
")." << std::endl;
214 if (k >= n || k < 0) {
215 std::cout <<
"BPAS: error, DUQP(" << n <<
") but trying to access " << k <<
"." << std::endl;
218 coef[k] = value.get_mpq();
219 if (k > curd && value != 0)
246 inline DenseUnivariateRationalPolynomial
unitCanonical(DenseUnivariateRationalPolynomial* u = NULL, DenseUnivariateRationalPolynomial* v = NULL)
const {
249 DenseUnivariateRationalPolynomial ret = *
this * leadInv;
264 inline DenseUnivariateRationalPolynomial&
operator= (
const DenseUnivariateRationalPolynomial& b) {
266 if (n) {
delete [] coef; n = 0; }
271 std::copy(b.coef, b.coef+n, coef);
286 inline bool operator!= (
const DenseUnivariateRationalPolynomial& b)
const {
287 return !(isEqual(b));
295 inline bool operator== (
const DenseUnivariateRationalPolynomial& b)
const {
306 return (coef[0] == 0);
328 return (coef[0] == 1);
340 for (
int i = 1; i < n; ++i)
351 return (coef[0] == -1);
363 for (
int i = 1; i < n; ++i)
373 if (curd) {
return 0; }
374 else if (coef[0] >= 0) {
return 1; }
387 inline DenseUnivariateRationalPolynomial primitivePart()
const {
389 std::cerr <<
"BPAS ERROR: DUQP::primitivePart NOT YET IMPLEMENTED" << std::endl;
399 DenseUnivariateRationalPolynomial
operator^ (
long long int e)
const;
407 inline DenseUnivariateRationalPolynomial&
operator^= (
long long int e) {
418 DenseUnivariateRationalPolynomial
operator<< (
int k)
const;
438 DenseUnivariateRationalPolynomial
operator>> (
int k)
const;
457 DenseUnivariateRationalPolynomial
operator+ (
const DenseUnivariateRationalPolynomial& b)
const;
464 inline DenseUnivariateRationalPolynomial&
operator+= (
const DenseUnivariateRationalPolynomial& b) {
477 void add(
const DenseUnivariateRationalPolynomial& b);
485 DenseUnivariateRationalPolynomial r (*
this);
489 inline DenseUnivariateRationalPolynomial
operator+ (
const mpq_class& c)
const {
490 DenseUnivariateRationalPolynomial r (*
this);
500 coef[0] += lfixq(c.get_mpq());
504 inline DenseUnivariateRationalPolynomial&
operator+= (
const mpq_class& c) {
509 inline friend DenseUnivariateRationalPolynomial
operator+ (
const mpq_class& c,
const DenseUnivariateRationalPolynomial& p) {
518 DenseUnivariateRationalPolynomial
operator- (
const DenseUnivariateRationalPolynomial& b)
const;
525 inline DenseUnivariateRationalPolynomial&
operator-= (
const DenseUnivariateRationalPolynomial& b) {
538 DenseUnivariateRationalPolynomial
operator- ()
const;
545 void subtract(
const DenseUnivariateRationalPolynomial& b);
553 DenseUnivariateRationalPolynomial r (*
this);
557 inline DenseUnivariateRationalPolynomial
operator- (
const mpq_class& c)
const {
558 DenseUnivariateRationalPolynomial r (*
this);
568 coef[0] -= lfixq(c.get_mpq());
572 inline DenseUnivariateRationalPolynomial&
operator-= (
const mpq_class& c) {
577 inline friend DenseUnivariateRationalPolynomial
operator- (
const mpq_class& c,
const DenseUnivariateRationalPolynomial& p) {
586 DenseUnivariateRationalPolynomial
operator* (
const DenseUnivariateRationalPolynomial& b)
const;
593 inline DenseUnivariateRationalPolynomial&
operator*= (
const DenseUnivariateRationalPolynomial& b) {
604 DenseUnivariateRationalPolynomial r (*
this);
608 inline DenseUnivariateRationalPolynomial
operator* (
const mpq_class& e)
const {
609 DenseUnivariateRationalPolynomial r (*
this);
613 inline DenseUnivariateRationalPolynomial
operator* (
const sfixn& e)
const {
614 DenseUnivariateRationalPolynomial r (*
this);
625 DenseUnivariateRationalPolynomial&
operator*= (
const mpq_class& e);
632 DenseUnivariateRationalPolynomial&
operator*= (
const sfixn& e);
634 inline friend DenseUnivariateRationalPolynomial
operator* (
const mpq_class& c,
const DenseUnivariateRationalPolynomial& p) {
638 inline friend DenseUnivariateRationalPolynomial
operator* (
const sfixn& c,
const DenseUnivariateRationalPolynomial& p) {
648 inline DenseUnivariateRationalPolynomial
operator/ (
const DenseUnivariateRationalPolynomial& b)
const{
649 DenseUnivariateRationalPolynomial rem(*
this);
659 DenseUnivariateRationalPolynomial&
operator/= (
const DenseUnivariateRationalPolynomial& b);
661 inline DenseUnivariateRationalPolynomial
operator% (
const DenseUnivariateRationalPolynomial& b)
const {
662 DenseUnivariateRationalPolynomial ret(*
this);
667 inline DenseUnivariateRationalPolynomial&
operator%= (
const DenseUnivariateRationalPolynomial& b) {
678 DenseUnivariateRationalPolynomial r (*
this);
682 inline DenseUnivariateRationalPolynomial
operator/ (
const mpq_class& e)
const {
683 DenseUnivariateRationalPolynomial r (*
this);
694 DenseUnivariateRationalPolynomial&
operator/= (
const mpq_class& e);
696 friend DenseUnivariateRationalPolynomial
operator/ (
const mpq_class& c,
const DenseUnivariateRationalPolynomial& p);
704 DenseUnivariateRationalPolynomial
monicDivide(
const DenseUnivariateRationalPolynomial& b);
713 DenseUnivariateRationalPolynomial
monicDivide(
const DenseUnivariateRationalPolynomial& b, DenseUnivariateRationalPolynomial* rem)
const;
757 DenseUnivariateRationalPolynomial
pseudoDivide (
const DenseUnivariateRationalPolynomial& b, DenseUnivariateRationalPolynomial* rem,
RationalNumber* d)
const;
765 DenseUnivariateRationalPolynomial
halfExtendedEuclidean (
const DenseUnivariateRationalPolynomial& b, DenseUnivariateRationalPolynomial* g)
const;
775 void diophantinEquationSolve(
const DenseUnivariateRationalPolynomial& a,
const DenseUnivariateRationalPolynomial& b, DenseUnivariateRationalPolynomial* s, DenseUnivariateRationalPolynomial* t)
const;
797 inline DenseUnivariateRationalPolynomial
derivative(
int k)
const {
798 DenseUnivariateRationalPolynomial a(*
this);
807 inline DenseUnivariateRationalPolynomial
derivative()
const {
829 inline DenseUnivariateRationalPolynomial
integral()
const {
830 DenseUnivariateRationalPolynomial a(*
this);
855 template <
class LargerRing>
860 LargerRing px = (LargerRing)coef[curd];
861 for (
int i = curd-1; i > -1; --i){
862 a = (LargerRing)coef[i];
867 return (LargerRing)coef[0];
882 DenseUnivariateRationalPolynomial
gcd (
const DenseUnivariateRationalPolynomial& q,
int type)
const;
884 inline DenseUnivariateRationalPolynomial
gcd(
const DenseUnivariateRationalPolynomial& q)
const {
969 univariatePositiveRealRootIsolation(&pIs,
this, width, ts);
970 std::vector<Symbol> xs;
992 univariatePositiveRealRootIsolation(&pIs,
this, width, ts);
993 std::vector<Symbol> xs;
1007 univariateRealRootIsolation(&pIs,
this, width, ts);
1018 refineUnivariateInterval(a, a->right+1,
this, width);
1029 refineUnivariateIntervals(&b, &a,
this, width);
1039 void print(std::ostream &out)
const;
1051 inline DenseUnivariateRationalPolynomial
euclideanDivision(
const DenseUnivariateRationalPolynomial& b, DenseUnivariateRationalPolynomial* q = NULL)
const {
1052 std::cerr <<
"DenseUnivariateRationalPolynomial::euclideanDivision NOT YET IMPLEMENTED" << std::endl;
1057 inline DenseUnivariateRationalPolynomial
extendedEuclidean(
const DenseUnivariateRationalPolynomial& b,
1058 DenseUnivariateRationalPolynomial* s = NULL,
1059 DenseUnivariateRationalPolynomial* t = NULL)
const {
1060 std::cerr <<
"DenseUnivariateRationalPolynomial::extendedEuclidean NOT YET IMPLEMENTED" << std::endl;
1065 inline DenseUnivariateRationalPolynomial
quotient(
const DenseUnivariateRationalPolynomial& b)
const {
1066 std::cerr <<
"DenseUnivariateRationalPolynomial::quotient NOT YET IMPLEMENTED" << std::endl;
1072 inline DenseUnivariateRationalPolynomial
remainder(
const DenseUnivariateRationalPolynomial& b)
const {
1073 std::cerr <<
"DenseUnivariateRationalPolynomial::remainder NOT YET IMPLEMENTED" << std::endl;
DenseUnivariateRationalPolynomial(const DenseUnivariateRationalPolynomial &b)
Copy constructor.
Definition: urpolynomial.h:131
DenseUnivariateRationalPolynomial halfExtendedEuclidean(const DenseUnivariateRationalPolynomial &b, DenseUnivariateRationalPolynomial *g) const
s * a g (mod b), where g = gcd(a, b)
DenseUnivariateRationalPolynomial euclideanSize() const
BPASEuclideanDomain methods.
Definition: urpolynomial.h:1047
DenseUnivariateRationalPolynomial pseudoDivide(const DenseUnivariateRationalPolynomial &b, RationalNumber *d=NULL)
Pseudo dividsion Return the quotient and itself becomes remainder.
bool isConstantTermZero() const
Is the least signficant coefficient zero.
mpq_class * coefficients(int k=0) const
Get coefficients of the polynomial, given start offset.
Definition: urpolynomial.h:188
void setVariableNames(const std::vector< Symbol > &xs)
Set variable names.
Definition: interval.h:189
DenseUnivariateRationalPolynomial operator-() const
Overload operator -, negate.
DenseUnivariateRationalPolynomial operator^(long long int e) const
Overload operator ^ replace xor operation by exponentiation.
DenseUnivariateRationalPolynomial gcd(const DenseUnivariateRationalPolynomial &q) const
Get GCD of *this and other.
Definition: urpolynomial.h:884
DenseUnivariateRationalPolynomial & operator>>=(int k)
Overload operator >>= replace by dividing x^k, and return the quotient.
Definition: urpolynomial.h:447
void zero()
Zero polynomial.
Definition: urpolynomial.h:315
LargerRing evaluate(const LargerRing &x) const
Evaluate f(x)
Definition: urpolynomial.h:856
DenseUnivariateRationalPolynomial operator%(const DenseUnivariateRationalPolynomial &b) const
Get the remainder of *this and b;.
Definition: urpolynomial.h:661
void diophantinEquationSolve(const DenseUnivariateRationalPolynomial &a, const DenseUnivariateRationalPolynomial &b, DenseUnivariateRationalPolynomial *s, DenseUnivariateRationalPolynomial *t) const
s*a + t*b = c, where c in the ideal (a,b)
bool operator==(const DenseUnivariateRationalPolynomial &b) const
Overload operator ==.
Definition: urpolynomial.h:295
void setVariableName(const Symbol &x)
Set variable's name.
Definition: urpolynomial.h:242
DenseUnivariateRationalPolynomial operator*(const DenseUnivariateRationalPolynomial &b) const
Multiply to another polynomial.
DenseUnivariateRationalPolynomial & operator<<=(int k)
Overload operator <<= replace by muplitying x^k.
Definition: urpolynomial.h:426
void negate()
Compute -f(x)
Intervals realRootIsolate(mpq_class width, int ts=-1)
Real root isolation for square-free polynomials.
Definition: urpolynomial.h:1005
bool isOne() const
Is polynomial a constatn 1.
Definition: urpolynomial.h:326
DenseUnivariateRationalPolynomial remainder(const DenseUnivariateRationalPolynomial &b) const
Get the remainder of *this and b.
Definition: urpolynomial.h:1072
void one()
Set polynomial to 1.
Definition: urpolynomial.h:337
void differentiate(int k)
Convert current object to its k-th derivative.
RationalNumber coefficient(int k) const
Get a coefficient of the polynomial.
Definition: urpolynomial.h:201
void differentiate()
Convert current object to its derivative.
Definition: urpolynomial.h:788
An ExpressionTree encompasses various forms of data that can be expressed generically as a binary tre...
Definition: ExpressionTree.hpp:17
DenseUnivariateRationalPolynomial & operator-=(const DenseUnivariateRationalPolynomial &b)
Overload operator -=.
Definition: urpolynomial.h:525
DenseUnivariateRationalPolynomial unitCanonical(DenseUnivariateRationalPolynomial *u=NULL, DenseUnivariateRationalPolynomial *v=NULL) const
Obtain the unit normal (a.k.a canonical associate) of an element.
Definition: urpolynomial.h:246
DenseUnivariateRationalPolynomial(const Integer &e)
Construct a polynomial with a coefficient.
Definition: urpolynomial.h:116
void integrate()
Compute the integral with constant of integration 0.
DenseUnivariateRationalPolynomial lazyPseudoDivide(const DenseUnivariateRationalPolynomial &b, RationalNumber *c, RationalNumber *d=NULL)
Lazy pseudo dividsion Return the quotient and itself becomes remainder e is the exact number of divis...
Data Structure for interval [a, b].
Definition: interval.h:9
Integer degree() const
Get degree of the polynomial.
Definition: urpolynomial.h:151
void refineRoot(Interval *a, mpq_class width)
Refine a root.
Definition: urpolynomial.h:1017
bool isZero() const
Is zero polynomial.
Definition: urpolynomial.h:304
DenseUnivariateRationalPolynomial & operator*=(const DenseUnivariateRationalPolynomial &b)
Overload operator *=.
Definition: urpolynomial.h:593
bool isNegativeOne() const
Is polynomial a constatn -1.
Definition: urpolynomial.h:349
DenseUnivariateRationalPolynomial operator>>(int k) const
Overload operator >> replace by dividing x^k, and return the quotient.
Factors< DenseUnivariateRationalPolynomial > squareFree() const
Square free.
A univariate polynomial with RationalNumber coefficients represented densely.
Definition: urpolynomial.h:15
DenseUnivariateRationalPolynomial & operator=(const DenseUnivariateRationalPolynomial &b)
Overload operator =.
Definition: urpolynomial.h:264
void homothetic(int k=1)
Homothetic operation.
void taylorShift(int ts=-1)
Taylor Shift operation by 1.
DenseUnivariateRationalPolynomial derivative() const
Compute derivative.
Definition: urpolynomial.h:807
DenseUnivariateRationalPolynomial()
Construct a polynomial.
Definition: urpolynomial.h:91
void negativeOne()
Set polynomial to -1.
Definition: urpolynomial.h:360
Intervals refineRoots(Intervals &a, mpq_class width)
Refine the roots.
Definition: urpolynomial.h:1027
DenseUnivariateRationalPolynomial integral() const
Compute integral with constant of integration 0.
Definition: urpolynomial.h:829
A simple data structure for encapsulating a collection of Factor elements.
Definition: Factors.hpp:95
bool divideByVariableIfCan()
Divide by variable if it is zero.
DenseUnivariateRationalPolynomial & operator%=(const DenseUnivariateRationalPolynomial &b)
Assign *this to be the remainder of *this and b.
Definition: urpolynomial.h:667
DenseUnivariateRationalPolynomial derivative(int k) const
Return k-th derivative.
Definition: urpolynomial.h:797
An arbitrary-precision Integer.
Definition: Integer.hpp:22
void negativeVariable()
Compute f(-x)
An abstract class defining the interface of a univariate polynomial over an arbitrary BPASRing...
Definition: polynomial.h:88
RationalNumber evaluate(const RationalNumber &x) const
Evaluate f(x)
void print(std::ostream &out) const
Overload stream operator <<.
mpz_class rootBound()
Return an integer k such that any positive root alpha of the polynomial satisfies alpha < 2^k...
void scaleTransform(int k)
Scale transform operation.
DenseUnivariateRationalPolynomial quotient(const DenseUnivariateRationalPolynomial &b) const
Get the quotient of *this and b.
Definition: urpolynomial.h:1065
An abstract class defining the interface of a Euclidean domain.
Definition: BPASEuclideanDomain.hpp:12
bool operator!=(const DenseUnivariateRationalPolynomial &b) const
Overload operator !=.
Definition: urpolynomial.h:286
DenseUnivariateRationalPolynomial & operator/=(const DenseUnivariateRationalPolynomial &b)
Overload operator /= ExactDivision.
Intervals positiveRealRootIsolate(mpq_class width, int ts=-1)
Positive real root isolation for square-free polynomials.
Definition: urpolynomial.h:967
int isConstant() const
Is a constant.
Definition: urpolynomial.h:372
void setCoefficient(int k, const RationalNumber &value)
Set a coefficient of the polynomial.
Definition: urpolynomial.h:213
An encapsulation of a mathematical symbol.
Definition: Symbol.hpp:23
An arbitrary-precision rational number.
Definition: RationalNumber.hpp:24
virtual mpz_class characteristic()
The characteristic of this ring class.
Definition: BPASRing.hpp:87
DenseUnivariateRationalPolynomial extendedEuclidean(const DenseUnivariateRationalPolynomial &b, DenseUnivariateRationalPolynomial *s=NULL, DenseUnivariateRationalPolynomial *t=NULL) const
Perofrm the extended euclidean division on *this and b.
Definition: urpolynomial.h:1057
DenseUnivariateRationalPolynomial(int s)
Construct a polynomial with degree.
Definition: urpolynomial.h:101
DenseUnivariateRationalPolynomial operator/(const DenseUnivariateRationalPolynomial &b) const
Overload operator / ExactDivision.
Definition: urpolynomial.h:648
RationalNumber leadingCoefficient() const
Get the leading coefficient.
Definition: urpolynomial.h:160
DenseUnivariateRationalPolynomial monicDivide(const DenseUnivariateRationalPolynomial &b)
Monic division Return quotient and itself become the remainder.
int numberOfSignChanges()
Number of coefficient sign variation.
RationalNumber inverse() const
Get the inverse of *this.
Definition: RationalNumber.hpp:392
DenseUnivariateRationalPolynomial & operator^=(long long int e)
Overload operator ^= replace xor operation by exponentiation.
Definition: urpolynomial.h:407
DenseUnivariateRationalPolynomial gcd(const DenseUnivariateRationalPolynomial &q, int type) const
GCD(p, q)
~DenseUnivariateRationalPolynomial()
Destroy the polynomial.
Definition: urpolynomial.h:142
Symbol variable() const
Get variable's name.
Definition: urpolynomial.h:233
Interval lists for real roots of multivariate polynomials.
Definition: interval.h:33
RationalNumber content() const
Content of the polynomial.
Definition: urpolynomial.h:383
DenseUnivariateRationalPolynomial & operator+=(const DenseUnivariateRationalPolynomial &b)
Overload Operator +=.
Definition: urpolynomial.h:464
ExpressionTree convertToExpressionTree() const
Convert this to an expression tree.
DenseUnivariateRationalPolynomial operator+(const DenseUnivariateRationalPolynomial &b) const
Overload operator +.
DenseUnivariateRationalPolynomial euclideanDivision(const DenseUnivariateRationalPolynomial &b, DenseUnivariateRationalPolynomial *q=NULL) const
Perform the eucldiean division of *this and b.
Definition: urpolynomial.h:1051
DenseUnivariateRationalPolynomial operator<<(int k) const
Overload operator << replace by muplitying x^k.
void add(const DenseUnivariateRationalPolynomial &b)
Add another polynomial to itself.
void subtract(const DenseUnivariateRationalPolynomial &b)
Subtract another polynomial from itself.
void reciprocal()
Revert coefficients.