Как правильно реализовать возведение полинома в степень?

Question

[Silence]

Добрый вечер.
Проблема возникла такая, не могу понять как правильно возводить полином в степень.
Так хранится полином:

class Polynom  {
	private: 
		int deg; //степень полинома
		double *koef; //указатель на массив коэффициентов полинома

Есть перегруженный оператор умножения (*) между объектами, но он не следит за степенями, то есть
При умножении полинома на полином, результирующий полином необходимо инициализировать как

Polynom "имя объекта"(степень первого полинома умножаемого + степень второго умножаемого);

Таким образом вызовется конструктор выделяющий память под необходимое кол-во элементов.
Конструктор:

Polynom::Polynom(int count)
{
        deg=count;
        koef=new double[deg+1];
}

А вот как реализовать адекватное возведение в степень при этом инициализировать результирующий полином необходимой степень, не понимаю
Может получится реализовать это в самой функции возведения в степени
Подскажите, пожалуйста, кому не сложно и понимает.

Answer 1

[Rsa97]

Если полином степени m возвести в степень n, то результирующий полином будет иметь степень m*n.

Comments

[Silence]

Rsa97 ,Так, этот момент понял, спасибо. Ещё один, наверное, очевидный вопрос, но тем не менее. Если возводить полином в степень 0. Результатом будет просто число 1?
Если следовать тому, что вы написали будет умножена степень полинома на 0.
И будет выделена память только под 1 элемент, который и будет = 1.
Верны мои рассуждения?

[Rsa97]

Silence, Да

[Silence]

Rsa97, хорошо, спасибо большое за отзывчивость)

[Roman]

Silence, rain.ifmo.ru/cat/view.php/theory/math/fft-2004

[Silence]

Roman, Спасибо)
Простите, что заставляю "гуглить за себя", с мат. частью не сильно дружу)
Поэтому пришел за помощью объяснения простым языком)
Теперь, думаю, разобрался.

[Silence]

Roman, Rsa97, Можно у вас попросить помощи ещё в одном моменте.
Мне нужно написать метод композиции полиномов.
Это один полином принимает в качестве аргумента другой.
Например:
Первый полином:
2x^2+2x+3
Второй полином:
x+2

Промежуточный результат:
2(x+2)^2+2(x+2)+3
Результат:
2(x^2+4x+4)+2(x+2)+3

Натолкните на алгоритм реализации данного метода, пожалуйста.
Промежуточный результат не нужен. Нужен конечный вариант.

Функцию для возведения полинома в степень, писал как раз для реализации этого метода.

//------------ФУНКЦИЯ ВОЗВЕДЕНИЯ ПОЛИНОМА В ПОЛОЖИТЕЛЬНУЮ СТЕПЕНЬ-------------------
Polynom Polynom::upDegree(int degree)
{
    Polynom result(getDegree()*degree);
    Polynom tmp=*this;
    if (degree == 1)
        return *this;
    if (degree == 0){
    	result.koef[0]=1;
    	return result;
	}
    else if (degree>=2)
    {
    	for(int i=0;i<degree-1;i++){
    		tmp=*this*tmp;
		}
        return result=tmp;
    }
}

[Rsa97]

Silence, А, собственно, в чём проблема то?

Просто опишите все операции - сложение, умножение на коэффициент, умножение на полином. Возведение в степень особо то и не нужно, у вас всё равно надо получать все степени, так что просто в цикле домножаете на один и тот же полином.
Примерно так:

Polynom composition(Polynom main, Polynom arg) {
  Polynom inter(0); // необходимо проинициализировать как 1
  Polynom result(0); // необходимо проинициализировать как 0
  for (int i = 0; i <= main.degree; i++) {
    result = result + inter * main.koef[i];
    inter = inter * arg;
  }
  return result;
}

[Roman]

Silence,
https://www.boost.org/doc/libs/1_69_0/libs/math/ex...

в исходниках boost/math/tools/polynomial.hpp

там все есть.

template <typename U, typename V>
   void multiply(const polynomial<U>& a, const polynomial<V>& b) {
       if (!a || !b)
       {
           this->set_zero();
           return;
       }
       std::vector<T> prod(a.size() + b.size() - 1, T(0));
       for (unsigned i = 0; i < a.size(); ++i)
           for (unsigned j = 0; j < b.size(); ++j)
               prod[i+j] += a.m_data[i] * b.m_data[j];
       m_data.swap(prod);
   }

   template <class U>
   polynomial& operator *=(const polynomial<U>& value)
   {
      this->multiply(*this, value);
      return *this;
   }

Функцию для возведения полинома в степень, писал как раз для реализации этого метода.

polynomial<T> pow(polynomial<T> base, int exp)
{
    if (exp < 0)
        return policies::raise_domain_error(
                "boost::math::tools::pow<%1%>",
                "Negative powers are not supported for polynomials.",
                base, policies::policy<>());
        // if the policy is ignore_error or errno_on_error, raise_domain_error
        // will return std::numeric_limits<polynomial<T>>::quiet_NaN(), which
        // defaults to polynomial<T>(), which is the zero polynomial
    polynomial<T> result(T(1));
    if (exp & 1)
        result = base;
    /* "Exponentiation by squaring" */
    while (exp >>= 1)
    {
        base *= base;
        if (exp & 1)
            result *= base;
    }
    return result;
}

[Silence]

Rsa97, Спасибо, понял принцип)