1.Function integer_roots
The function integer_roots computes the integer roots, with multiplicity, of a lacunary
(a.k.a. super-sparse) polynomial. This function is implemented in the
file integer_roots.hpp.
The input polynomial is a sparse_polynomial<C,monomial<vector<E>
> > where C
is the type of the coefficients and E
is the type of the exponents. For both, the supported types are int and integer. Note yet that the coefficients
should be at least as large as the exponents since this is needed to
derive the polynomial. For more on sparse_polynomial<…>,
please refer to the documentation of Multimix.
The roots are returned as a vector<
pair<C,E> > where in each pair<C,E> the first component is
the root and the second is its multiplicity.
#include <lacunaryx/integer_roots.hpp>
…
#define E integer // or int
#define C integer // or int
#define Monomial monomial< vector<E> >
#define Sparse_polynomial sparse_polynomial<C, Monomial>
…
Sparse_polynomial x (1, Monomial (vec(1))); // defines the variable x
Sparse_polynomial p= x*x*(x+1)*(x+1)*(x-2)*(x+3)*(x+3)*(x+3)*(2*x+3)*(x*x+x+1);
string s="4356768657564355757856462587657634635";
integer e(s);
p *= (1+3*binpow(x,1345) - 2*(x-4)*binpow(x,e)+(x*x*x-6)*binpow(x,2*e));
vector< pair<C,E> > v= integer_roots(p); // [(0,2),(-1,2),(2,1),(-3,3)] |
2.Use within Mathemagix
2.1.Lacunary polynomials
The lacunaryx package comes with a new type for polynomials
called LPolynomials.
The function integer_roots
is glued within Mmx-light under the name roots and can be used with
LPolynomials as
follows:
Mmx] |
use "lacunaryx"; type_mode? := true; |
Mmx] |
x : LPolynomial Integer == lpolynomial(1:> Integer, 1) |
:
Mmx] |
p : LPolynomial Integer == x^2*(x+1)^2*(x-2)*(x+3)^3*(2*x+3)*(x^2+x+1) |
:
Mmx] |
q : LPolynomial Integer == -x^876546523 + x^876546522 + 2*x^876546520 - 2*x^876546519 + 2*x^156476833 - 12*x^156476832 + 10*x^156476831 + 8*x^1346 - 8*x^1345 - x + 1 |
:
:
2.2.Multivariate polynomials
The function integer_roots can also take as input a multivariate<sparse_polynomial<…>>,
as defined in Multimix. A variant
of Multimix's MVPolynomial,
named LMVPolynomial
(for “Lacunary Multivariate Polynomial”), is defined for
polynomials with very large exponents. While MVPolynomials
have exponents of type Int,
LMVPolynomials have
exponents of type Integer.
The function integer_root
is glued to mmx-light under the name roots, and can be used as follows:
Mmx] |
X : Coordinate == coordinate ('x) |
:
Mmx] |
x : LMVPolynomial Integer == lmvpolynomial(1:>Integer, X) |
:
Mmx] |
p : LMVPolynomial Integer == x^2*(x+1)^2*(x-2)*(x+3)^3*(2*x+3)*(x^2+x+1) |
:
Mmx] |
q : LMVPolynomial Integer == -x^876546523 + x^876546522 + 2*x^876546520 - 2*x^876546519 + 2*x^156476833 - 12*x^156476832 + 10*x^156476831 + 8*x^1346 - 8*x^1345 - x + 1 |
:
:
© 2014 Bruno Grenet
Permission is granted to copy, distribute and/or modify this document
under the terms of the
GNU General Public License. If you
don't have this file, write to the Free Software Foundation, Inc., 59
Temple Place - Suite 330, Boston, MA 02111-1307, USA.