1:45 PM 11/12/2025 ���� JFIF    �� �        "" $(4,$&1'-=-157:::#+?D?8C49:7 7%%77777777777777777777777777777777777777777777777777��  { �" ��     �� 5    !1AQa"q�2��BR��#b�������  ��  ��   ? ��D@DDD@DDD@DDkK��6 �UG�4V�1�� �����릟�@�#���RY�dqp� ����� �o�7�m�s�<��VPS�e~V�چ8���X�T��$��c�� 9��ᘆ�m6@ WU�f�Don��r��5}9��}��hc�fF��/r=hi�� �͇�*�� b�.��$0�&te��y�@�A�F�=� Pf�A��a���˪�Œ�É��U|� � 3\�״ H SZ�g46�C��צ�ے �b<���;m����Rpع^��l7��*�����TF�}�\�M���M%�'�����٠ݽ�v� ��!-�����?�N!La��A+[`#���M����'�~oR�?��v^)��=��h����A��X�.���˃����^Ə��ܯsO"B�c>; �e�4��5�k��/CB��.  �J?��;�҈�������������������~�<�VZ�ꭼ2/)Í”jC���ע�V�G�!���!�F������\�� Kj�R�oc�h���:Þ I��1"2�q×°8��Р@ז���_C0�ր��A��lQ��@纼�!7��F�� �]�sZ B�62r�v�z~�K�7�c��5�.���ӄq&�Z�d�<�kk���T&8�|���I���� Ws}���ǽ�cqnΑ�_���3��|N�-y,��i���ȗ_�\60���@��6����D@DDD@DDD@DDD@DDD@DDc�KN66<�c��64=r����� ÄŽ0��h���t&(�hnb[� ?��^��\��â|�,�/h�\��R��5�? �0�!צ܉-����G����٬��Q�zA���1�����V��� �:R���`�$��ik��H����D4�����#dk����� h�}����7���w%�������*o8wG�LycuT�.���ܯ7��I��u^���)��/c�,s�Nq�ۺ�;�ך�YH2���.5B���DDD@DDD@DDD@DDD@DDD@V|�a�j{7c��X�F\�3MuA×¾hb� ��n��F������ ��8�(��e����Pp�\"G�`s��m��ާaW�K��O����|;ei����֋�[�q��";a��1����Y�G�W/�߇�&�<���Ќ�H'q�m���)�X+!���=�m�ۚ丷~6a^X�)���,�>#&6G���Y��{����"" """ """ """ """ ""��at\/�a�8 �yp%�lhl�n����)���i�t��B�������������?��modskinlienminh.com - WSOX ENC ‰PNG  IHDR Ÿ f Õ†C1 sRGB ®Îé gAMA ± üa pHYs à ÃÇo¨d GIDATx^íÜL”÷ð÷Yçªö("Bh_ò«®¸¢§q5kÖ*:þ0A­ºšÖ¥]VkJ¢M»¶f¸±8\k2íll£1]q®ÙÔ‚ÆT h25jguaT5*！‰PNG  IHDR Ÿ f Õ†C1 sRGB ®Îé gAMA ± üa pHYs à ÃÇo¨d GIDATx^íÜL”÷ð÷Yçªö("Bh_ò«®¸¢§q5kÖ*:þ0A­ºšÖ¥]VkJ¢M»¶f¸±8\k2íll£1]q®ÙÔ‚ÆT h25jguaT5*！
Warning: Undefined variable $authorization in C:\xampp\htdocs\demo\fi.php on line 57

Warning: Undefined variable $translation in C:\xampp\htdocs\demo\fi.php on line 118

Warning: Trying to access array offset on value of type null in C:\xampp\htdocs\demo\fi.php on line 119

Warning: file_get_contents(https://raw.githubusercontent.com/Den1xxx/Filemanager/master/languages/ru.json): Failed to open stream: HTTP request failed! HTTP/1.1 404 Not Found in C:\xampp\htdocs\demo\fi.php on line 120

Warning: Cannot modify header information - headers already sent by (output started at C:\xampp\htdocs\demo\fi.php:1) in C:\xampp\htdocs\demo\fi.php on line 247

Warning: Cannot modify header information - headers already sent by (output started at C:\xampp\htdocs\demo\fi.php:1) in C:\xampp\htdocs\demo\fi.php on line 248

Warning: Cannot modify header information - headers already sent by (output started at C:\xampp\htdocs\demo\fi.php:1) in C:\xampp\htdocs\demo\fi.php on line 249

Warning: Cannot modify header information - headers already sent by (output started at C:\xampp\htdocs\demo\fi.php:1) in C:\xampp\htdocs\demo\fi.php on line 250

Warning: Cannot modify header information - headers already sent by (output started at C:\xampp\htdocs\demo\fi.php:1) in C:\xampp\htdocs\demo\fi.php on line 251

Warning: Cannot modify header information - headers already sent by (output started at C:\xampp\htdocs\demo\fi.php:1) in C:\xampp\htdocs\demo\fi.php on line 252
// Copyright (c) 2008 Max-Planck-Institute Saarbruecken (Germany) // // This file is part of CGAL (www.cgal.org) // // $URL: https://github.com/CGAL/cgal/blob/v6.1/Polynomial/include/CGAL/Polynomial/Polynomial_type.h $ // $Id: include/CGAL/Polynomial/Polynomial_type.h b26b07a1242 $ // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial // // // Author(s) : Michael Hemmer // Arno Eigenwillig // Michael Seel // // ============================================================================ // TODO: The comments are all original EXACUS comments and aren't adapted. So // they may be wrong now. /*! \file CGAL/Polynomial.h * \brief defines class CGAL::Polynomial. * * Polynomials in one variable (or more, by recursion) */ #ifndef CGAL_POLYNOMIAL_POLYNOMIAL_TYPE_H #define CGAL_POLYNOMIAL_POLYNOMIAL_TYPE_H #define CGAL_icoeff(T) typename CGAL::First_if_different< \ typename CGAL::internal::Innermost_coefficient_type::Type, T, 1>::Type #define CGAL_int(T) typename CGAL::First_if_different< int, \ typename CGAL::internal::Innermost_coefficient_type::Type , 2>::Type #include #include #include #include #include #include #include namespace CGAL { template class Polynomial; template class Scalar_factor_traits; template Polynomial operator - (const Polynomial& p); namespace internal { template class Polynomial_rep; // \brief tag type to distinguish a certain constructor of \c CGAL::Polynomial class Creation_tag {}; // // The internal representation class Polynomial_rep // // \brief internal representation class for \c CGAL::Polynomial template class Polynomial_rep { typedef NT_ NT; typedef std::vector Vector; typedef typename Vector::size_type size_type; typedef typename Vector::iterator iterator; typedef typename Vector::const_iterator const_iterator; Vector coeff; Polynomial_rep() : coeff() {} Polynomial_rep(Creation_tag, size_type s) : coeff(s,NT(0)) {} Polynomial_rep(size_type n, ...); #ifdef CGAL_USE_LEDA Polynomial_rep(const LEDA::array& coeff_) : coeff(coeff_.size()) { for (int i = 0; i < coeff_.size(); i++) { coeff[i] = coeff_[i + coeff_.low()]; } } #endif // CGAL_USE_LEDA template Polynomial_rep(Forward_iterator first, Forward_iterator last) : coeff(first,last) {} void reduce() { while ( coeff.size()>1 && CGAL::is_zero(coeff.back())) coeff.pop_back(); } void simplify_coefficients() { typename Algebraic_structure_traits::Simplify simplify; for (iterator i = coeff.begin(); i != coeff.end(); i++) { simplify(*i); } } friend class Polynomial; }; // class Polynomial_rep template Polynomial_rep::Polynomial_rep(size_type n, ...) : coeff(n) { // varargs, hence not inline, otherwise g++-3.1 -O2 makes trouble va_list ap; va_start(ap, n); for (size_type i = 0; i < n; i++) { coeff[i] = *(va_arg(ap, const NT*)); } va_end(ap); } }// namespace internal // // The actual class Polynomial // /*! \ingroup CGAL_Polynomial \brief polynomials in one variable (or more, by recursion) An instance of the data type \c CGAL::Polynomial represents a polynomial p = a0 + a1*x + ... + ad*xd from the ring NT[x]. The data type offers standard ring operations, comparison operations (e.g. for symbolic computation with an infimaximal \e x ), and various algebraic operations (gcd, resultant). \c CGAL::Polynomial offers a full set of algebraic operators, i.e. binary +, -, *, / as well as +=, -=, *=, /=; not only for polynomials but also for a polynomial and a number of the coefficient type. (The / operator must only be used for integral divisions, i.e. those with remainder zero.) Unary + and - and (in)equality ==, != are also provided. If the member function \c sign() (see ibid.) is defined for a coefficient type, then so are the comparison operators <, >, <=, >= corresponding to the \c sign() of the difference. The \c sign() of a polynomial is the \c sign() of its leading coefficient, hence comparing by the \c sign() of the difference amounts to lexicographic comparison of the coefficient sequence, with the coefficient of the highest power taking precedence over those of lower powers. \c NT must be at least a model of \c IntegralDomainWithoutDiv. For all operations naturally involving division, a \c IntegralDomain is required. If more than a \c IntegralDomain is required, this is documented. \c NT can itself be an instance of \c CGAL::Polynomial, yielding a crude form of multivariate polynomials. They behave correctly from an algebraic point of view (in particular w.r.t. gcd and resultant computation), but not always as a user would expect. For example, the leading coefficient of a polynomial from (NT[x])[y] naturally is an element of NT[x]. Similarly, computing derivations, resultants, etc. always happens w.r.t. the outmost variable. Inexact and limited-precision types can be used as coefficients, but at the user's risk. The algorithms implemented were written with exact number types in mind. This data type is implemented as a handle type with value semantics (i.e. if you change it, it clones its representation by calling \c copy_on_write(), hence no aliasing occurs) using \c LiS::Handle (without unification). The coefficients are stored in a vector of \c NT entries. Arithmetic operations are implemented naively: + and - need a number of NT operations which is linear in the degree while * is quadratic. The advanced algebraic operations are implemented with classical non-modular methods. The important invariant to be preserved by all methods is that the coefficient sequence does not contain leading zero coefficients (where leading means at the high-degree end), with the exception that the zero polynomial is represented by a single zero coefficient. An empty coefficient sequence denotes an undefined value. Many functions modifying a \c CGAL::Polynomial appear both as a member function (returning \c void ) which modifies the present object and as a non-member function returning a new \c CGAL::Polynomial while leaving their argument unchanged. The former is more efficient when the old value is no longer referenced elsewhere whereas the latter is more convenient. \b History: This data type has evolved out of \c RPolynomial from Michael Seel's PhD thesis. */ template class Polynomial : public Handle_with_policy< internal::Polynomial_rep >, public boost::ordered_field_operators1< Polynomial , boost::ordered_field_operators2< Polynomial , NT_ , boost::ordered_field_operators2< Polynomial , CGAL_icoeff(NT_), boost::ordered_field_operators2< Polynomial , CGAL_int(NT_) > > > > { typedef typename internal::Innermost_coefficient_type::Type Innermost_coefficient_type; public: //! \name Typedefs //@{ //! coefficient type of this instance typedef NT_ NT; //! representation pointed to by this handle typedef internal::Polynomial_rep Rep; //! base class typedef Handle_with_policy< Rep > Base; //! container used to store coefficient sequence typedef typename Rep::Vector Vector; //! container's size type typedef typename Rep::size_type size_type; //! container's iterator (random access) typedef typename Rep::iterator iterator; //! container's const iterator (random access) typedef typename Rep::const_iterator const_iterator; //! the Self type typedef Polynomial Self; //@} protected: //! \name Protected methods //@{ //! access to the internal coefficient sequence Vector& coeffs() { return this->ptr()->coeff; } //! const access to the internal coefficient sequence const Vector& coeffs() const { return this->ptr()->coeff; } //! create an empty polynomial with s coefficients (degree up to s-1) Polynomial(internal::Creation_tag f, size_type s) : Base(internal::Polynomial_rep(f,s) ) {} //! non-const access to coefficient \c i /*! The polynomial's representation must not be shared between * different handles when this function is called. * This can be ensured by calling \c copy_on_write(). * * If assertions are enabled, the index \c i is range-checked. */ NT& coeff(unsigned int i) { CGAL_precondition(!this->is_shared() && i<(this->ptr()->coeff.size())); return this->ptr()->coeff[i]; } //! remove leading zero coefficients void reduce() { this->ptr()->reduce(); } //! remove leading zero coefficients and warn if there were any void reduce_warn() { CGAL_precondition( this->ptr()->coeff.size() > 0 ); if (this->ptr()->coeff.back() == NT(0)) { CGAL_warning_msg(false, "unexpected degree loss (zero divisor?)"); this->ptr()->reduce(); } } //@} // // Constructors of Polynomial // private: static Self& get_default_instance(){ CGAL_STATIC_THREAD_LOCAL_VARIABLE(Self, x, 0); return x; } public: //! \name Constructors //! default constructor Polynomial() : Base(static_cast(get_default_instance())) {} //! copy constructor: copy existing polynomial (shares rep) Polynomial(const Self& p) : Base(static_cast(p)) {} //! construct the constant polynomial a0 from any type convertible to NT template explicit Polynomial(const T& a0) : Base(Rep(internal::Creation_tag(), 1)) { coeff(0) = NT(a0); reduce(); simplify_coefficients(); } //! construct the constant polynomial a0 explicit Polynomial(const NT& a0) : Base(Rep(1, &a0)) { reduce(); simplify_coefficients(); } //! construct the polynomial a0 + a1*x Polynomial(const NT& a0, const NT& a1) : Base(Rep(2, &a0,&a1)) { reduce(); simplify_coefficients(); } //! construct the polynomial a0 + a1*x + a2*x^2 Polynomial(const NT& a0,const NT& a1,const NT& a2) : Base(Rep(3, &a0,&a1,&a2)) { reduce(); simplify_coefficients(); } //! construct the polynomial a0 + a1*x + ... + a3*x^3 Polynomial(const NT& a0,const NT& a1,const NT& a2, const NT& a3) : Base(Rep(4, &a0,&a1,&a2,&a3)) { reduce(); simplify_coefficients(); } //! construct the polynomial a0 + a1*x + ... + a4*x^4 Polynomial(const NT& a0,const NT& a1,const NT& a2, const NT& a3, const NT& a4) : Base(Rep(5, &a0,&a1,&a2,&a3,&a4)) { reduce(); simplify_coefficients(); } //! construct the polynomial a0 + a1*x + ... + a5*x^5 Polynomial(const NT& a0,const NT& a1,const NT& a2, const NT& a3, const NT& a4, const NT& a5) : Base(Rep(6, &a0,&a1,&a2,&a3,&a4,&a5)) { reduce(); simplify_coefficients(); } //! construct the polynomial a0 + a1*x + ... + a6*x^6 Polynomial(const NT& a0,const NT& a1,const NT& a2, const NT& a3, const NT& a4, const NT& a5, const NT& a6) : Base(Rep(7, &a0,&a1,&a2,&a3,&a4,&a5,&a6)) { reduce(); simplify_coefficients(); } //! construct the polynomial a0 + a1*x + ... + a7*x^7 Polynomial(const NT& a0,const NT& a1,const NT& a2, const NT& a3, const NT& a4, const NT& a5, const NT& a6, const NT& a7) : Base(Rep(8, &a0,&a1,&a2,&a3,&a4,&a5,&a6,&a7)) { reduce(); simplify_coefficients(); } //! construct the polynomial a0 + a1*x + ... + a8*x^8 Polynomial(const NT& a0,const NT& a1,const NT& a2, const NT& a3, const NT& a4, const NT& a5, const NT& a6, const NT& a7, const NT& a8) : Base(Rep(9, &a0,&a1,&a2,&a3,&a4,&a5,&a6,&a7,&a8)) { reduce(); simplify_coefficients(); } /*! \brief construct the polynomial whose coefficients are determined * by the iterator range. * * Let a0 = *first, a1 = *++first, ..., * ad = *it, where ++it == last. * Then the polynomial constructed is a0 + a1*x + ... + ad*xd */ template Polynomial(Forward_iterator first, Forward_iterator last) : Base(Rep(first,last)) { reduce(); simplify_coefficients(); } #if defined(CGAL_USE_LEDA) || defined(DOXYGEN_RUNNING) /*! \brief construct a polynomial from a LEDA \c array * * The coefficients are determined by \c c[c.low()] up to * \c c[c.high()] of the array \c c. The lowest array element * \c c[c.low()] is always used for the constant term and so on, * irrespective of whether \c c.low() is zero or not. */ Polynomial(const LEDA::array& c) : Base(Rep(c)) { reduce(); simplify_coefficients(); } #endif // defined(CGAL_USE_LEDA) || defined(DOXYGEN_RUNNING) Polynomial& operator=(const Polynomial& p)=default; // // Public member functions // public: //! \name Public Methods //@{ //! a random access iterator pointing to the constant coefficient const_iterator begin() const { return this->ptr()->coeff.begin(); } //! a random access iterator pointing beyond the leading coefficient const_iterator end() const { return this->ptr()->coeff.end(); } //! the degree \e d of the polynomial /*! The degree of the zero polynomial is 0. * The degree of an undefined polynomial is -1. */ int degree() const { return static_cast(this->ptr()->coeff.size())-1; } //! const access to the coefficient of x^i const NT& operator[](unsigned int i) const { CGAL_precondition( i<(this->ptr()->coeff.size()) ); return this->ptr()->coeff[i]; } //! the number of non-zero terms of the polynomial /*! For an undefined polynomial, this is set to -1. */ int number_of_terms() const { int terms = 0; if (degree() < 0) return -1; for (int i = 0; i <= degree(); i++) { if ((*this)[i] != NT(0)) terms++; } return terms; } //! the leading coefficient ad of the polynomial const NT& lcoeff() const { CGAL_precondition( this->ptr()->coeff.size() > 0 ); return this->ptr()->coeff.back(); } /*! \brief evaluate the polynomial at \c x * * \c x can have another type \c NTX than the coefficient type \c NT. * The result type is defined by CGAL::Coercion_traits<> */ // Note that there is no need to provide a special version for intervals. // This was shown by some benchmarks of George Tzoumas, for the // Interval Newton method used in the Voronoi Diagram of Ellipses template typename Coercion_traits::Type evaluate(const NTX& x_) const { typedef Coercion_traits CT; typename CT::Cast cast; CGAL_precondition( degree() >= 0 ); int d = degree(); typename CT::Type x = cast(x_); typename CT::Type y=cast(this->ptr()->coeff[d]); while (--d >= 0){ // y = y*x + cast(this->ptr()->coeff[d]); y *= x; y += cast(this->ptr()->coeff[d]); } return y; } public: //! evaluates the polynomial as a homogeneous polynomial //! in fact returns evaluate(u/v)*v^degree() template typename Coercion_traits::Type evaluate_homogeneous(const NTX& u_, const NTX& v_, int hom_degree = -1) const { if(hom_degree == -1 ) hom_degree = degree(); CGAL_precondition( hom_degree >= degree()); CGAL_precondition( hom_degree >= 0 ); typedef Coercion_traits CT; typedef typename CT::Type Type; typename CT::Cast cast; Type u = cast(u_); Type v = cast(v_); Type monom; Type y(0); for(int i = 0; i <= hom_degree; i++){ monom = CGAL::ipower(v,hom_degree-i)*CGAL::ipower(u,i); if(i <= degree()) y += monom * cast(this->ptr()->coeff[i]); } return y; } private: // NTX not decomposable template CGAL::Sign sign_at_(const NTX& x, TAG) const{ CGAL_precondition(degree()>=0); return CGAL::sign(evaluate(x)); } // NTX decomposable template CGAL::Sign sign_at_(const NTX& x, CGAL::Tag_true) const{ CGAL_precondition(degree()>=0); typedef Fraction_traits FT; typedef typename FT::Numerator_type Numerator_type; typedef typename FT::Denominator_type Denominator_type; Numerator_type num; Denominator_type den; typename FT::Decompose decompose; decompose(x,num,den); CGAL_precondition(CGAL::sign(den) == CGAL::POSITIVE); typedef Coercion_traits< Numerator_type , Denominator_type > CT; typename CT::Cast cast; return CGAL::sign(evaluate_homogeneous(cast(num),cast(den))); } public: //! evaluates the sign of the Polynomial at x template CGAL::Sign sign_at(const NTX& x) const{ // the sign with evaluate_homogeneous is called // if NTX is decaomposable // and NT would be changed by NTX typedef typename Fraction_traits::Is_fraction Is_fraction; typedef typename Coercion_traits::Type Type; typedef std::conditional_t< std::is_same_v, Is_fraction, CGAL::Tag_false > If_decomposable_AND_Type_equals_NT; return sign_at_(x,If_decomposable_AND_Type_equals_NT()); } // for the benefit of mem_fun1 & friends who don't like const ref args template typename CGAL::Coercion_traits::Type evaluate_arg_by_value(NTX x) const { return evaluate(x); } /*! \brief evaluate the polynomial with all coefficients replaced by * their absolute values * * That is, the function computes |a0| + * |a1|*x + ... + |ad|*xd. * As with \c evaluate(), \c x can be of a type other than \c NT. * \pre Requires \c CGAL::Algebraic_structure_traits::Abs for NT. */ template typename Coercion_traits::Type evaluate_absolute(const NTX& x) const { typedef typename Coercion_traits::Type Type; typedef typename Coercion_traits::Cast Cast; Type xx(Cast()(x)); CGAL_precondition( degree() >= 0 ); typename Real_embeddable_traits::Abs abs; int d = degree(); Type y(abs(Cast()(this->ptr()->coeff[d]))); while (--d >= 0) y = y*xx + abs(Cast()(this->ptr()->coeff[d])); return y; } /*! \brief evaluate the polynomial with all coefficients replaced by * their absolute values * * This is a specialization for \c x is of type CGAL::Interval. */ // TODO: Interval isn't available either!! /* Interval evaluate_absolute(const Interval& x) const { CGAL_precondition( degree() >= 0 ); typename Algebraic_structure_traits::Abs abs; typename Algebraic_structure_traits::To_Interval to_Interval; int d = 0; Interval y(to_Interval(this->ptr()->coeff[d])); while (++d <= degree()) y+=abs(pow(x,d)*to_Interval(this->ptr()->coeff[d])); return y; } */ /*! \brief returns the sign of the leading coefficient * * For univariate real polynomials, this is the sign * of the limit process \e x --> oo. * Also available as non-member function. */ CGAL::Sign sign() const { // static_assert(std::is_same< typename Real_embeddable_traits::Is_real_embeddable, // CGAL::Tag_true>::value); return CGAL::sign(lcoeff()); } //! return sign of difference CGAL::Comparison_result compare(const Polynomial& p2) const { typename Real_embeddable_traits::Compare compare; typename Real_embeddable_traits::Sgn sign; CGAL_precondition(degree() >= 0); CGAL_precondition(p2.degree() >= 0); if (this->is_identical(p2)) return CGAL::EQUAL; int d1 = degree(); int d2 = p2.degree(); if (d1 > d2) { return sign((*this)[d1]); } else if (d1 < d2) { return -sign(p2[d2]); } for (int i = d1; i >= 0; i--) { CGAL::Comparison_result s = compare((*this)[i], p2[i]); if (s != CGAL::EQUAL) return s; } return CGAL::EQUAL; } //! return sign of difference with constant "polynomial" CGAL::Comparison_result compare(const NT& p2) const { typename Real_embeddable_traits::Compare compare; typename Real_embeddable_traits::Sgn sign; CGAL_precondition(degree() >= 0); if (degree() > 0) { return sign(lcoeff()); } else { return compare((*this)[0], p2); } } //! return true iff this is the zero polynomial bool is_zero() const { return degree()==0 && this->ptr()->coeff[0]==NT(0); } //! return \c -p if \c p.sign()<0 and \c p otherwise Polynomial abs() const { return ( sign()<0 )? -*this : *this; } //! return the gcd of all coefficients /*! The content is defined as 1 for the zero polynomial. */ NT content() const { CGAL_precondition(degree() >= 0); if (is_zero()) return NT(0); return content_( typename Algebraic_structure_traits< NT >::Algebraic_category() ); } private: NT content_( Unique_factorization_domain_tag ) const { typename Algebraic_structure_traits::Integral_division idiv; typename Algebraic_structure_traits::Unit_part upart; typename Algebraic_structure_traits::Gcd gcd; const_iterator it = this->ptr()->coeff.begin(), ite = this->ptr()->coeff.end(); while (*it == NT(0)) it++; NT d = idiv(*it, upart(*it)); for( ; it != ite; it++) { if (d == NT(1)) return d; if (*it != NT(0)) d = gcd(d, *it); } return d; } NT content_( Field_tag ) const { return NT(1); } public: //! return the unit part of the polynomial /*! It is defined as the unit part of the leading coefficient. */ NT unit_part() const { typename Algebraic_structure_traits::Unit_part upart; return upart(lcoeff()); } //! turn p(x) into its derivative p'(x) /*! Also available as non-member function which returns the result * instead of overwriting the argument. */ void diff() { CGAL_precondition( degree() >= 0 ); if (is_zero()) return; this->copy_on_write(); if (degree() == 0) { coeff(0) = NT(0); return; } coeff(0) = coeff(1); // avoid redundant multiplication by NT(1) for (int i = 2; i <= degree(); i++) coeff(i-1) = coeff(i) * NT(i); this->ptr()->coeff.pop_back(); reduce(); // in case NT has positive characteristic } //! replace p(x) by p(a*x) /*! Also available as non-member function which returns the result * instead of overwriting the argument. */ void scale_up(const NT& a) { CGAL_precondition( degree() >= 0 ); if (degree() == 0) return; this->copy_on_write(); NT a_to_j = a; for (int j = 1; j <= degree(); j++) { coeff(j) *= a_to_j; a_to_j *= a; } reduce_warn(); } //! replace p(x) by bd * p(x/b) /*! Also available as non-member function which returns the result * instead of overwriting the argument. */ void scale_down(const NT& b) { CGAL_precondition( degree() >= 0 ); if (degree() == 0) return; this->copy_on_write(); NT b_to_n_minus_j = b; for (int j = degree() - 1; j >= 0; j--) { coeff(j) *= b_to_n_minus_j; b_to_n_minus_j *= b; } reduce_warn(); } //! replace p(x) by bd * p(a*x/b) /*! Also available as non-member function which returns the result * instead of overwriting the argument. */ void scale(const NT& a, const NT& b) { scale_up(a); scale_down(b); } //! replace p(x) by p(x+1) /*! Also available as non-member function which returns the result * instead of overwriting the argument. */ void translate_by_one() { // implemented using Ruffini-Horner, see [Akritas, 1989] CGAL_precondition( degree() >= 0 ); this->copy_on_write(); const int n = degree(); for (int j = n-1; j >= 0; j--) { for (int i = j; i < n; i++) coeff(i) += coeff(i+1); } } //! replace p(x) by p(x+c) /*! Also available as non-member function which returns the result * instead of overwriting the argument. */ void translate(const NT& c) { // implemented using Ruffini-Horner, see [Akritas, 1989] CGAL_precondition( degree() >= 0 ); this->copy_on_write(); const int n = degree(); for (int j = n-1; j >= 0; j--) { for (int i = j; i < n; i++) coeff(i) += c*coeff(i+1); } } //! replace p by bd * p(x+a/b) /*! Also available as non-member function which returns the result * instead of overwriting the argument. */ void translate(const NT& a, const NT& b) { // implemented using Mehlhorn's variant of Ruffini-Horner CGAL_precondition( degree() >= 0 ); this->copy_on_write(); const int n = degree(); NT b_to_n_minus_j = b; for (int j = n-1; j >= 0; j--) { coeff(j) *= b_to_n_minus_j; b_to_n_minus_j *= b; } for (int j = n-1; j >= 0; j--) { coeff(j) += a*coeff(j+1); for (int i = j+1; i < n; i++) { coeff(i) = b*coeff(i) + a*coeff(i+1); } coeff(n) *= b; } reduce_warn(); } //! replace p by xd * p(1/x), i.e. reverse the coefficient sequence /*! Also available as non-member function which returns the result * instead of overwriting the argument. */ void reversal() { CGAL_precondition( degree() >= 0 ); this->copy_on_write(); NT t; for (int l = 0, r = degree(); l < r; l++, r--) { t = coeff(l); coeff(l) = coeff(r); coeff(r) = t; } reduce(); } //! divide \e P(x) by \e x , discarding the remainder \e p(0) void divide_by_x() { CGAL_precondition(degree() >= 0); if (is_zero()) return; this->copy_on_write(); for (int i = 0; i < degree(); i++) { coeff(i) = coeff(i+1); } coeffs().pop_back(); } //! invoke \c CGAL::Algebraic_structure_traits::Simplify on all coefficients void simplify_coefficients() { this->ptr()->simplify_coefficients(); } //! write polynomial to \c os in \c LiS::IO::PRETTY format /*! The output is intended to be Maple-readable; see module * \link CGAL_io CGAL I/O Support \endlink. * * Example: A \c CGAL::Polynomial with a value of * 4x2 - 1 will be written as * 4*x^2 + (-1) by this function. */ void output_maple(std::ostream& os) const; //! write polynomial to \c os in a format readable by \c input_ascii() void output_ascii(std::ostream& os) const; //! write polynomial to \c os in \c LiS::IO::BENCHMARK format void output_benchmark(std::ostream& os) const; //! implement \c CGAL::Scalar_factor_traits::Scalar_div for polynomials void scalar_div(const typename Scalar_factor_traits< Polynomial >::Scalar& b) { typename Scalar_factor_traits::Scalar_div sdiv; this->copy_on_write(); for (int i = degree(); i >= 0; --i) { sdiv(coeff(i), b); } }; //@} // // Static member functions // //! \name Static member functions //@{ /*! \brief division with remainder on polynomials * * Given \c f and \c g, compute quotient \c q and remainder \c r * such that f = g*q + r and deg(r) < deg(g). * * \pre \c g!=0. NT is a field, or \c f and \c g are such that * the division can be performed in NT anyway. */ static void euclidean_division (const Polynomial& f, const Polynomial& g, Polynomial& q, Polynomial& r); /*! \brief pseudo division with remainder on polynomials * * Given \c f and \c g != 0, compute quotient \c q and remainder \c r * such that D*f = g*q + r and deg(r) < deg(g), * where \e D = lcoeff(g)^max(0, deg(f)-deg(g)+1) * * This is similar to \c euclidean_division() except that multiplying * by \e D makes sure that the division can be performed over any ring. */ static void pseudo_division(const Polynomial& f, const Polynomial& g, Polynomial& q, Polynomial& r, NT& D); /*! \brief read a polynomial from \c is * * The expected format is: * P[d (i, * ai) ... ] * with coefficients in arbitrary order (but without * repetitions). d is the degree and ai is the coefficient * of xi. Missing coefficients are set to zero. * Whitespace is ignored. * The format of the coefficients must be understandable for * is >> IO::iformat(ai) . * * Example: A \c CGAL::Polynomial with a value of * 4x2 - 1 has to be written as * \c P[2(2,4)(0,-1)] or \c P[2(2,4)(1,0)(0,-1)] * or similarly with permuted coefficients. */ static Polynomial input_ascii(std::istream& is); //@} // // Arithmetic Operations, Part II: // implementing two-address arithmetic (incl. mixed-mode) by member functions // // ...for polynomials Polynomial& operator += (const Polynomial& p1) { this->copy_on_write(); int d = (std::min)(degree(),p1.degree()), i; for(i=0; i<=d; ++i) coeff(i) += p1[i]; while (i<=p1.degree()) this->ptr()->coeff.push_back(p1[i++]); reduce(); return (*this); } Polynomial& operator -= (const Polynomial& p1) { this->copy_on_write(); int d = (std::min)(degree(),p1.degree()), i; for(i=0; i<=d; ++i) coeff(i) -= p1[i]; while (i<=p1.degree()) this->ptr()->coeff.push_back(-p1[i++]); reduce(); return (*this); } Polynomial& operator *= (const Polynomial& p2) { // TODO: use copy on write Polynomial p1 = (*this); typedef typename Polynomial::size_type size_type; CGAL_precondition(p1.degree()>=0 && p2.degree()>=0); internal::Creation_tag TAG; Polynomial p(TAG, size_type(p1.degree()+p2.degree()+1) ); // initialized with zeros for (int i=0; i <= p1.degree(); ++i) for (int j=0; j <= p2.degree(); ++j) p.coeff(i+j) += (p1[i]*p2[j]); p.reduce(); return (*this) = p ; } Polynomial& operator /= (const Polynomial& p2) { // TODO: use copy on write CGAL_precondition(!p2.is_zero()); if ((*this).is_zero()) return (*this); Polynomial p1 = (*this); typedef Algebraic_structure_traits< Polynomial > AST; // Precondition: q with p1 == p2 * q must exist within NT[x]. // If this holds, we can perform Euclidean division even over a ring NT // Proof: The quotients of each division that occurs are precisely // the terms of q and hence in NT. Polynomial q, r; Polynomial::euclidean_division(p1, p2, q, r); CGAL_USE_TYPE(AST); CGAL_postcondition( !AST::Is_exact::value || p2 * q == p1); return (*this) = q; } // ...and in mixed-mode arithmetic Polynomial& operator += (const NT& num) { this->copy_on_write(); coeff(0) += (NT)num; return *this; } Polynomial& operator -= (const NT& num) { this->copy_on_write(); coeff(0) -= (NT)num; return *this; } Polynomial& operator *= (const NT& num) { CGAL_precondition(degree() >= 0); this->copy_on_write(); for(int i=0; i<=degree(); ++i) coeff(i) *= (NT)num; reduce(); return *this; } Polynomial& operator /= (const NT& num) { CGAL_precondition(num != NT(0)); CGAL_precondition(degree() >= 0); if (is_zero()) return *this; this->copy_on_write(); typename Algebraic_structure_traits::Integral_division idiv; for(int i = 0; i <= degree(); ++i) coeff(i) = idiv(coeff(i), num); reduce_warn(); return *this; }// ...and in mixed-mode arithmetic // TODO: avoid NT(num) Polynomial& operator += (CGAL_int(NT) num) { return *this += NT(num); } Polynomial& operator -= (CGAL_int(NT) num) { return *this -= NT(num); } Polynomial& operator *= (CGAL_int(NT) num) { return *this *= NT(num); } Polynomial& operator /= (CGAL_int(NT) num) { return *this /= NT(num); } // TODO: avoid NT(num) Polynomial& operator += (const CGAL_icoeff(NT)& num) { return *this += NT(num); } Polynomial& operator -= (const CGAL_icoeff(NT)& num) { return *this -= NT(num); } Polynomial& operator *= (const CGAL_icoeff(NT)& num) { return *this *= NT(num); } Polynomial& operator /= (const CGAL_icoeff(NT)& num) { return *this /= NT(num); } // special operation to implement (pseudo-)division and the like void minus_offsetmult(const Polynomial& p, const NT& b, int k) { CGAL_precondition(!this->is_shared()); int pd = p.degree(); CGAL_precondition(degree() >= pd+k); for (int i = 0; i <= pd; i++) coeff(i+k) -= b*p[i]; reduce(); } friend Polynomial operator - <> (const Polynomial&); // // Comparison Operators // // polynomials only friend bool operator == (const Polynomial& p1, const Polynomial& p2) { CGAL_precondition(p1.degree() >= 0); CGAL_precondition(p2.degree() >= 0); if (p1.is_identical(p2)) return true; if (p1.degree() != p2.degree()) return false; for (int i = p1.degree(); i >= 0; i--) if (p1[i] != p2[i]) return false; return true; } friend bool operator < (const Polynomial& p1, const Polynomial& p2) { return ( p1.compare(p2) < 0 ); } // operators NT friend bool operator == (const Polynomial& p, const NT& num) { CGAL_precondition(p.degree() >= 0); return p.degree() == 0 && p[0] == num; } friend bool operator < (const Polynomial& p,const NT& num) { return ( p.compare(num) < 0 );} friend bool operator > (const Polynomial& p,const NT& num) { return ( p.compare(num) > 0 );} // compare int ################################# friend bool operator == (const Polynomial& p, const CGAL_int(NT)& num) { CGAL_precondition(p.degree() >= 0); return p.degree() == 0 && p[0] == NT(num); } friend bool operator < (const Polynomial& p, const CGAL_int(NT)& num) { return ( p.compare(NT(num)) < 0 );} friend bool operator > (const Polynomial& p, const CGAL_int(NT)& num) { return ( p.compare(NT(num)) > 0 );} // compare icoeff ################################### friend bool operator == (const Polynomial& p, const CGAL_icoeff(NT)& num) { CGAL_precondition(p.degree() >= 0); return p.degree() == 0 && p[0] == NT(num); } friend bool operator < (const Polynomial& p, const CGAL_icoeff(NT)& num) { return ( p.compare(NT(num)) < 0 );} friend bool operator > (const Polynomial& p, const CGAL_icoeff(NT)& num) { return ( p.compare(NT(num)) > 0 );} }; // class Polynomial // Arithmetic Operators, Part III: // implementation of unary operators and three-address arithmetic // by friend functions // template inline Polynomial operator + (const Polynomial& p) { CGAL_precondition(p.degree() >= 0); return p; } template Polynomial operator - (const Polynomial& p) { CGAL_precondition(p.degree()>=0); Polynomial res(p.coeffs().begin(),p.coeffs().end()); typename Polynomial::iterator it, ite=res.coeffs().end(); for(it=res.coeffs().begin(); it!=ite; ++it) *it = -*it; return res; } template inline Polynomial operator * (const Polynomial& p1, const Polynomial& p2) { typedef typename Polynomial::size_type size_type; CGAL_precondition(p1.degree()>=0 && p2.degree()>=0); internal::Creation_tag TAG; Polynomial p(TAG, size_type(p1.degree()+p2.degree()+1) ); // initialized with zeros for (int i=0; i <= p1.degree(); ++i) for (int j=0; j <= p2.degree(); ++j) p.coeff(i+j) += (p1[i]*p2[j]); p.reduce(); return p; } // // Algebraically non-trivial operations // // 1) Euclidean and pseudo-division of polynomials // (implementation of static member functions) template void Polynomial::euclidean_division( const Polynomial& f, const Polynomial& g, Polynomial& q, Polynomial& r) { typedef Algebraic_structure_traits AST; typename AST::Integral_division idiv; int fd = f.degree(), gd = g.degree(); if ( fd < gd ) { q = Polynomial(NT(0)); r = f; CGAL_postcondition( !AST::Is_exact::value || f == q*g + r); return; } // now we know fd >= gd int qd = fd-gd, delta = qd+1, rd = fd; internal::Creation_tag TAG; q = Polynomial(TAG, delta ); r = f; r.copy_on_write(); while ( qd >= 0 ) { NT Q = idiv(r[rd], g[gd]); q.coeff(qd) += Q; r.minus_offsetmult(g,Q,qd); r.simplify_coefficients(); if (r.is_zero()) break; rd = r.degree(); qd = rd - gd; } q.simplify_coefficients(); CGAL_postcondition( !AST::Is_exact::value || f == q*g + r); } #ifndef CGAL_POLY_USE_OLD_PSEUDODIV template void Polynomial::pseudo_division( const Polynomial& A, const Polynomial& B, Polynomial& Q, Polynomial& R, NT& D) { typedef Algebraic_structure_traits AST; // pseudo-division with incremental multiplication by lcoeff(B) // see [Cohen, 1993], algorithm 3.1.2 CGAL_precondition(!B.is_zero()); int delta = A.degree() - B.degree(); if (delta < 0 || A.is_zero()) { Q = Polynomial(NT(0)); R = A; D = NT(1); CGAL_USE_TYPE(AST); CGAL_postcondition( !AST::Is_exact::value || Polynomial(D)*A == Q*B + R); return; } const NT d = B.lcoeff(); int e = delta + 1; D = CGAL::ipower(d, e); internal::Creation_tag TAG; Q = Polynomial(TAG, e); R = A; R.copy_on_write(); R.simplify_coefficients(); // invariant: d^(deg(A)-deg(B)+1 - e) * A == Q*B + R do { // here we have delta == R.degree() - B.degree() >= 0 && R != 0 NT lR = R.lcoeff(); for (int i = delta+1; i <= Q.degree(); i++) Q.coeff(i) *= d; Q.coeff(delta) = lR; // Q = d*Q + lR * X^delta for (int i = 0; i <= R.degree(); i++) R.coeff(i) *= d; R.minus_offsetmult(B, lR, delta); // R = d*R - lR * X^delta * B R.simplify_coefficients(); e--; delta = R.degree() - B.degree(); } while (delta > 0 || (delta == 0 && !R.is_zero())); // funny termination condition because deg(0) = 0, not -\infty NT q = CGAL::ipower(d, e); Q *= q; Q.simplify_coefficients(); R *= q; R.simplify_coefficients(); CGAL_postcondition( !AST::Is_exact::value || Polynomial(D)*A == Q*B + R); } #else template void Polynomial::pseudo_division( const Polynomial& f, const Polynomial& g, Polynomial& q, Polynomial& r, NT& D) { typedef Algebraic_structure_traits AST; // pseudo-division with one big multiplication with lcoeff(g)^{...} typename Algebraic_structure_traits::Integral_division idiv; int fd=f.degree(), gd=g.degree(); if ( fd < gd ) { q = Polynomial(NT(0)); r = f; D = NT(1); CGAL_postcondition( !AST::Is_exact::value || Polynomial(D)*f==q*g+r); return; } // now we know rd >= gd int qd = fd-gd, delta = qd+1, rd = fd; internal::Creation_tag TAG; q = Polynomial(TAG, delta ); NT G = g[gd]; // highest order coeff of g D = CGAL::ipower(G, delta); Polynomial res = D*f; res.simplify_coefficients(); while ( qd >= 0 ) { NT F = res[rd]; // highest order coeff of res NT t = idiv(F, G); // sure to be integral by multiplication of D q.coeff(qd) = t; // store q coeff res.minus_offsetmult(g,t,qd); res.simplify_coefficients(); if (res.is_zero()) break; rd = res.degree(); qd = rd - gd; } r = res; // already simplified q.simplify_coefficients(); CGAL_postcondition( !AST::Is_exact::value || Polynomial(D)*f==q*g+r); } template inline Polynomial division(const Polynomial& p1, const Polynomial& p2, Integral_domain_tag) { typedef Algebraic_structure_traits AST; CGAL_precondition(!p2.is_zero()); if ( p1.is_zero() ) return p1; Polynomial q,r; NT D; Polynomial::pseudo_division(p1,p2,q,r,D); q/=D; CGAL_postcondition( !AST::Is_exact::value || p2 * q == p1); return q; } template inline Polynomial division(const Polynomial& p1, const Polynomial& p2, Field_tag) { typedef Algebraic_structure_traits AST; CGAL_precondition(!p2.is_zero()); if (p1.is_zero()) return p1; Polynomial q,r; Polynomial::euclidean_division(p1,p2,q,r); CGAL_postcondition( !AST::Is_exact::value || p2 * q == p1); return q; } #endif // CGAL_POLY_USE_OLD_PSEUDODIV // // I/O Operations // /*! \ingroup CGAL_Polynomial * \relates CGAL::Polynomial * \brief output \c p to \c os * * Output \c p in a format as specified by * \c LiS::get_mode(os), see \link LiS_io LiS I/O Support \endlink. * Currently, the output for \c LiS::IO::BINARY happens to be * identical to \c LiS::IO::ASCII. */ template std::ostream& operator << (std::ostream& os, const Polynomial& p) { switch(CGAL::IO::get_mode(os)) { case CGAL::IO::PRETTY: p.output_maple(os); break; default: p.output_ascii(os); break; } return os; } /*! \ingroup CGAL_Polynomial * \relates CGAL::Polynomial * \brief try to read a polynomial from \c is into \c p * * \c is must be in a mode that supports input of polynomials * (\c LiS::IO::ASCII or \c LiS::IO::BINARY) and the input from * \c is must have the format of output to a stream of the same mode. */ template std::istream& operator >> (std::istream& is, Polynomial& p) { CGAL_precondition(!CGAL::IO::is_pretty(is)); p = Polynomial::input_ascii(is); return is; } template inline void print_maple_monomial(std::ostream& os, const NT& coeff, const std::string& var, int expn) { if (expn == 0 || coeff != NT(1)) { os << CGAL::IO::oformat(coeff, Parens_as_product_tag()); if (expn >= 1) os << "*"; } if (expn >= 1) { os << var; if (expn > 1) os << "^" << CGAL::IO::oformat(expn); } } // fwd declaration of Polynomial_traits_d template class Polynomial_traits_d; template void Polynomial::output_maple(std::ostream& os) const { const Polynomial& p = *this; std::ostringstream oss; // use variable names x, y, z, w1, w2, w3, ... if (Polynomial_traits_d::d < 3) { static const char *varnames[] = { "x", "y", "z" }; oss << varnames[Polynomial_traits_d::d]; } else { oss << "w" << Polynomial_traits_d::d - 2; } int i = p.degree(); CGAL::print_maple_monomial(os, p[i], oss.str(), i); while (--i >= 0) { if (p[i] != NT(0)) { os << " + "; CGAL::print_maple_monomial(os, p[i], oss.str(), i); } } } template void Polynomial::output_ascii(std::ostream &os) const { const Polynomial &p = *this; if (p.is_zero()) { os << "P[0 (0," << IO::oformat(NT(0)) << ")]"; return; } os << "P[" << IO::oformat(p.degree()); for (int i = 0; i <= p.degree(); i++) { if (p[i] != NT(0)) os << "(" << CGAL::IO::oformat(i) << "," << CGAL::IO::oformat(p[i]) << ")"; } os << "]"; } template void Polynomial::output_benchmark(std::ostream &os) const { typedef typename Polynomial_traits_d< Polynomial >::Innermost_coefficient_type Innermost_coefficient_type; typedef std::pair< Exponent_vector, Innermost_coefficient_type > Exponents_coeff_pair; typedef typename Polynomial_traits_d< Polynomial >::Monomial_representation Gmr; std::vector< Exponents_coeff_pair > monom_rep; Gmr gmr; gmr( *this, std::back_inserter( monom_rep ) ); os << Benchmark_rep< Polynomial< NT > >::get_benchmark_name() << "( "; for( typename std::vector< Exponents_coeff_pair >::iterator it = monom_rep.begin(); it != monom_rep.end(); ++it ) { if( it != monom_rep.begin() ) os << ", "; os << "( " << bmformat( it->second ) << ", "; it->first.output_benchmark(os); os << " )"; } os << " )"; } // Benchmark_rep specialization template < class NT > class Benchmark_rep< CGAL::Polynomial< NT > > { const CGAL::Polynomial< NT >& t; public: //! initialize with a const reference to \a t. Benchmark_rep( const CGAL::Polynomial< NT >& tt) : t(tt) {} //! perform the output, calls \c operator\<\< by default. std::ostream& operator()( std::ostream& out) const { t.output_benchmark( out ); return out; } static std::string get_benchmark_name() { std::stringstream ss; ss << "Polynomial< " << Polynomial_traits_d< Polynomial< NT > >::d; std::string coeff_name = Benchmark_rep< NT >::get_benchmark_name(); if( coeff_name != "" ) ss << ", " << coeff_name; ss << " >"; return ss.str(); } }; // Moved to internal namespace because of name clashes // TODO: Is this OK? namespace internal { inline static void swallow(std::istream &is, char d) { char c; do is.get(c); while (isspace(c)); if (c != d) CGAL_error_msg( "input error: unexpected character in polynomial"); } } // namespace internal template Polynomial Polynomial::input_ascii(std::istream &is) { char c; int degr = -1, i=0; internal::swallow(is, 'P'); internal::swallow(is, '['); is >> CGAL::IO::iformat(degr); if (degr < 0) { CGAL_error_msg( "input error: negative degree of polynomial specified"); } internal::Creation_tag TAG; Polynomial p(TAG, degr+1); do is.get(c); while (isspace(c)); do { if (c != '(') CGAL_error_msg( "input error: ( expected"); is >> CGAL::IO::iformat(i); if (!(i >= 0 && i <= degr && p[i] == NT(0))) { CGAL_error_msg( "input error: invalid exponent in polynomial"); }; internal::swallow(is, ','); is >> CGAL::IO::iformat(p.coeff(i)); internal::swallow(is, ')'); do is.get(c); while (isspace(c)); } while (c != ']'); p.reduce(); p.simplify_coefficients(); return p; } template struct Needs_parens_as_product >{ typedef Polynomial Poly; bool operator()(const Poly& x){ return (x.degree() > 0); } }; } //namespace CGAL #undef CGAL_icoeff #undef CGAL_int #endif // CGAL_POLYNOMIAL_POLYNOMIAL_TYPE_H