Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm looking for an efficient algorithm to compute the $n$-th power $\alpha^n$ of a real algebraic number $\alpha$ given by an interval representation for $n \in \mathbb{N}$. An interval representation of a real algebraic number is a tupel $(P,(l,r))$ where $P$ is an univariate polynomial and $(l,r)$ is an interval containing exactly one root of $P$.

There are algorithms to compute the sum of two real algebraic numbers $\alpha_1 + \alpha_2$ and the product $\alpha_1 \cdot \alpha_2$. The algorithms can be found in Mishra's "Algorithmic algebra" (p. 332f) (the pages are availble on google books)

The first idea is to apply the multiplication algorithm $n$ times but this turns out to be very inefficient and to slow for my purpose.

I wonder if there is an efficient way to find a polynomial with a root $\alpha^n$. Like a polynomial $P'$ which is the polynomial that has the roots $x_1, ..., x_m$ where $y_1, ..., y_m$ are the roots of $P$ and $x_i = y_i^n$ for each $i$.

share|cite|improve this question
up vote 2 down vote accepted

How about repeated squaring? You'll only need on the order of $\log n$ multiplications.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.