2
$\begingroup$

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$.

1 Answers 1

2

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