Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

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.