%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%  quadratic_number_power_product.tex        LiDIA documentation
%%
%%  This file contains the documentation of the class
%%  quadratic_number_power_product.
%%
%%  Copyright (c) 1999 by the LiDIA Group
%%
%%  Author: Markus Maurer
%%

\newcommand{\num}{\mathit{num}}
\newcommand{\den}{\mathit{den}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\NAME

\CLASS{quadratic_number_power_product} \dotfill power products of quadratic numbers.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ABSTRACT

\code{quadratic_number_power_product} is a class that represents power products of quadratic
numbers.  It uses the class \SEE{quadratic_number_power_product_basis} to represent the basis of
the power product and a vector of \SEE{bigint} to represent the exponents.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DESCRIPTION

A \code{quadratic_number_power_product} is a pair $p = (b,e)$, where $b$ is of type
\SEE{quadratic_number_power_product_basis} and $e$ is of type \SEE{math_vector} over
\SEE{bigint}.  Let $b = (b_{0}, \dots, b_{n-1})$ and $e = (e_{0}, \dots, e_{n-1})$.  Then the
pair $p$ represents the power product
\begin{displaymath}
  p = \prod_{i=0}^{n-1} b_{i}^{e_{i}} \enspace.
\end{displaymath}
The class manages a list of elements of type \SEE{quadratic_number_power_product_basis}.  When a
power product is the result of an operation, then the basis object for the result is the same as
that for the operands and only a reference is copied.  This applies for all operations on power
products, unless stated otherwise.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\CONS

\begin{fcode}{ct}{quadratic_number_power_product}{}
  creates a power product with no elements.
\end{fcode}

\begin{fcode}{ct}{quadratic_number_power_product}{const quadratic_number_power_product & $q$}
  initializes with $q$.
\end{fcode}

\begin{fcode}{dt}{~quadratic_number_power_product}{}
  deletes the object.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ASGN

Let $p$ be of type \code{quadratic_number_power_product}.  The operator \code{=} is overloaded
for \SEE{quadratic_number_power_product} and \SEE{quadratic_number_standard}.  The following
functions are also implemented:

\begin{fcode}{void}{$p$.set_basis}{const quadratic_number_power_product_basis & $x$}
  Assigns a copy of $x$ to the basis of $p$ and leaves the exponent vector unchanged.
\end{fcode}

\begin{fcode}{void}{$p$.set_basis}{const quadratic_number_power_product & $x$}
  Assigns the basis of $x$ to the basis of $p$.
\end{fcode}

\begin{fcode}{void}{$p$.set_exponents}{const base_vector< exp_type > & $e$}
  Assigns $e$ to the exponent vector of $p$.
\end{fcode}

\begin{fcode}{void}{$p$.reset}{}
  Deletes the basis and the exponent vector of $p$.
\end{fcode}

\begin{fcode}{void}{$p$.assign}{const quadratic_number_power_product & $q$}
  $p = q$.
\end{fcode}

\begin{fcode}{void}{$p$.assign}{const quadratic_number_standard & $g$}
  $p = g^1$.
\end{fcode}

\begin{fcode}{void}{$p$.assign_one}{const quadratic_order & $\Or$}
  $p = 1^1$ with $1 \in \Or$.
\end{fcode}

\begin{fcode}{void}{$p$.assign}{const quadratic_ideal & $I$, const xbigfloat & $t$, int $s$}
  Let $\Or$ be the real quadratic order of $I$.  It is assumed that $I$ is a principal ideal in
  $\Or$ with $a \Or = I$ and $|t - \Ln(a)| < 2^{-4}$, $\sgn(a) = s$.  Then $a$ is uniquely
  determined by $I,t,s$.  The function initializes the power product by a compact representation
  of $a$.  If the above conditions are not satisfied, the result is undefined.  The $\sgn(a)$ is
  $-1$, if $a < 0$, and $1$ otherwise.
  
  Let $\Or$ be a quadratic order of discriminant $\D$, $K$ the field of fractions, and
  $\alpha\in K$.  Extending the definition in \cite{Buchmann/Thiel/Williams:1995} from quadratic
  integers to numbers in $K$, we say that $\alpha$ is in compact representation with respect to
  $\D$, if
  \begin{displaymath}
    \alpha = \gamma \prod_{j=1}^k \left(\frac{\alpha_j}{d_j}\right)^{2^{k-j}} \enspace,
  \end{displaymath}
  where $\gamma\in K$, $\alpha_j\in \Or$, $d_j\in\bbfZ_{>0}$, $1\leq j\leq k \leq \max\{ 1,
  \ln_2 \ln_2(H(\alpha) d(\alpha))+2 \}$,
  \begin{displaymath}
    d(\gamma) \leq d(\alpha) \enspace, \quad H(\gamma) \leq |N(\alpha)| d(\alpha) \enspace,
  \end{displaymath}
  and
  \begin{displaymath}
    0 < d_j \leq |\D|^{1/2}\enspace, \quad H(\alpha_j) \leq 2|\D|^{7/4} \quad\text{ for } 1 \leq j \leq k .
  \end{displaymath}
  Here, $H(\alpha)$ is the height, $N(\alpha)$ the norm, and $d(\alpha)$ the denominator of
  $\alpha$.  For further details see \cite{Maurer_Thesis:2000}.
\end{fcode}

\begin{fcode}{void}{swap}{const quadratic_number_power_product & $p$,
    const quadratic_number_power_product & $q$}%
  Swaps $p$ and $q$.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ACCS

Let $p$ be of type \code{quadratic_number_power_product}.

\begin{fcode}{const quadratic_number_power_product_basis &}{$p$.get_basis}{}
  Returns a \code{const} reference to the basis of $p$.  As usual, the \code{const} reference
  should only be used to create a copy or to immediately apply another operation to it, because
  after the next operation applied to $p$ the obtained reference may be invalid.
\end{fcode}

\begin{fcode}{const base_vector< bigint > &}{$p$.get_exponents}{}
  Returns a \code{const} reference to the vector of exponents of $p$.  As usual, the
  \code{const} reference should only be used to create a copy or to immediately apply another
  operation to it, because after the next operation applied to $p$ the obtained reference may be
  invalid.
\end{fcode}

\begin{fcode}{const quadratic_order &}{$p$.get_order}{}
  Returns a \code{const} reference to the order of the first element in the basis of $p$.  If
  there is no element in the basis of $p$, the \LEH is called.  This function is for
  convenience, in the case, that all base elements are defined over the same order.  As usual,
  the \code{const} reference should only be used to create a copy or to immediately apply
  another operation to it, because after the next operation applied to $p$ the obtained
  reference may be invalid.
\end{fcode}

\begin{fcode}{bool}{$p$.is_initialized}{}
  Returns \TRUE, if a basis and a vector of exponents has been assigned to $p$, and if both are
  of same length.  Otherwise, it returns \FALSE.
\end{fcode}

\begin{fcode}{int}{$p$.get_sign}{}
  Returns $1$, if $p \geq 0$, and $-1$ otherwise.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ARTH

Let $p$ be of type \code{quadratic_number_power_product}.  In the following, writing
$(b,c),(e,f)$ means, that the basis $b$ is concatenated with $c$ and that the exponent vector
$e$ is concatenated with $f$.

\begin{fcode}{void}{$p$.negate}{}
  $p \assign -p$.
\end{fcode}

\begin{fcode}{void}{$p$.multiply}{const quadratic_number_power_product & $x$,
    const quadratic_number_standard & $y$}%
  Let $x = (b,e)$.  Then $p \assign \bigl((b,y),(e,1)\bigr)$.
\end{fcode}

\begin{fcode}{void}{$p$.multiply}{const quadratic_number_standard & $y$,
    const quadratic_number_power_product & $x$}%
  Let $x = (b,e)$.  Then $p \assign \bigl((b,y),(e,1)\bigr)$.
\end{fcode}

\begin{fcode}{void}{$p$.multiply}{const quadratic_number_power_product & $x$,
    const quadratic_number_power_product & $y$}%
  Let $x = (b,e)$ and $y = (c,f)$.  Then $p \assign \bigl((b,c),(e,f)\bigr)$.
\end{fcode}

\begin{fcode}{void}{$p$.invert}{const quadratic_number_power_product & $x$}
  Let $p = (b,e)$.  Then $p \assign (b,-e)$.
\end{fcode}

\begin{fcode}{void}{$p$.invert_base_elements}{}
  Let $p = (b,e)$.  Then $p \assign (b^{-1},e)$, i.e., each element of the basis is inverted.
\end{fcode}

\begin{fcode}{void}{$p$.divide}{const quadratic_number_power_product & $x$,
    const quadratic_number_standard & $y$}%
  Let $x = (b,e)$.  Then $p \assign \bigl((b,y),(e,-1)\bigr)$.
\end{fcode}

\begin{fcode}{void}{$p$.divide}{const quadratic_number_standard & $y$,
    const quadratic_number_power_product & $x$}%
  Let $x = (b,e)$.  Then $p \assign \bigl((b,y),(-e,1)\bigr)$.
\end{fcode}

\begin{fcode}{void}{$p$.divide}{const quadratic_number_power_product & $x$,
    const quadratic_number_power_product & $y$}%
  Let $x = (b,e)$ and $y = (c,f)$.  Then $p \assign \bigl((b,c),(e,-f)\bigr)$.
\end{fcode}

\begin{fcode}{void}{$p$.square}{const quadratic_number_power_product & $x$}
  Let $x = (b,e)$.  Then $p \assign (b,2 \cdot e)$.
\end{fcode}

\begin{fcode}{void}{$p$.power}{const quadratic_number_power_product & $x$, const bigint & $f$}
  Let $x = (b,e)$.  Then $p \assign (b,f \cdot e)$.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\COMP

The binary operators \code{==} and \code{!=} are overloaded for comparison with
\code{quadratic_number_power_product} and \SEE{quadratic_number_standard}.

These functions are not efficient, because they evaluate the power products for comparison.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\BASIC

Let $p$ be of type \code{quadratic_number_power_product}.

\begin{fcode}{void}{$p$.conjugate}{}
  Maps $p$ to its conjugate by replacing each element of the basis of $p$ by its conjugate.
\end{fcode}

\begin{cfcode}{void}{$p$.norm_modulo}{bigint & $\num$, bigint & $\den$, const bigint & $m$}
  Returns $\num$ and $\den$, i.e., the numerator and denominator of the norm of $p$ modulo $m$,
  respectively.  If $m$ is zero, the \LEH will be called.  It is $0 \leq \num, \den < m$.
\end{cfcode}

\begin{cfcode}{quadratic_number_standard}{$p$.evaluate}{}
  Returns the evaluation of $p$.
\end{cfcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\HIGH

\begin{fcode}{void}{$p$.compact_representation}{const quadratic_ideal & $I$}
  Let $\Or$ be the real quadratic order of $I$.  If $p \Or = q I$, then this function transforms
  $p$ into compact representation.  Otherwise, the result is undefined.  For a definition of
  compact representation, see the corresponding \code{assign} function of the class.
\end{fcode}

\begin{fcode}{void}{$p$.get_short_principal_ideal_generator}{xbigfloat & $l$, bigint & $z$,
    const quadratic_unit & $\varrho$, long $b$, long $k$}%
  Let $\Or$ be the real quadratic order of $p$, $\varrho$ its fundamental unit, and let $R =
  |\Ln(\varrho)|$ denote the regulator of $\Or$.  If $|b - b(\Ln(\varrho))| \leq 1$ and $p$ is a
  non-rational number in the field of fractions of $\Or$, then this functions computes $z$, such
  that either $-R/2 < \Ln(p) - z R \leq R/2$ or $0 \leq \Ln p - z R < R$ and also an absolute $k$
  approximation to $\Ln(a)$, where $a = p / \varrho^z$.  If the conditions are not satisfied,
  the result is undefined.
  
  If $k\geq 4$, then $l$ and the ideal $I = p \Or$ can be used to compute a compact
  representation of $a$ using the \code{assign} function of the class.  If the caller is only
  interested in $z$, he should choose $k = -b+6$.
  
  NOTE: The interface of that function will be changed in the future, so that it is not
  necessary to give the parameters $\varrho$ and $b$ anymore.
\end{fcode}


\SSTITLE{$\Ln$ approximation}

Let $\Ln$ denote the Lenstra logarithm: $\Ln(x) = 1/2 \ln |x / \sigma(x)|$.

\begin{cfcode}{void}{$p$.get_absolute_Ln_approximation}{xbigfloat & $l$, long $k$}  
  Computes an absolute $k$-approximation $l$ to $\Ln(p)$.  See \SEE{xbigfloat} for definition of
  absolute approximation.
\end{cfcode}

\begin{cfcode}{void}{$p$.absolute_Ln_approximation}{xbigfloat & $l$, long $k$}
  Computes an absolute $k$-approximation $l$ to $\Ln(p)$.  See \SEE{xbigfloat} for definition of
  absolute approximation.
\end{cfcode}

\begin{cfcode}{xbigfloat}{$p$.get_absolute_Ln_approximation}{long $k$}
  Returns an absolute $k$-approximation to $\Ln(p)$.  See \SEE{xbigfloat} for definition of
  absolute approximation.
\end{cfcode}

\begin{cfcode}{xbigfloat}{$p$.absolute_Ln_approximation}{long $k$}
  Returns an absolute $k$-approximation to $\Ln(p)$.  See \SEE{xbigfloat} for definition of
  absolute approximation.
\end{cfcode}

\begin{cfcode}{void}{$p$.get_relative_Ln_approximation}{xbigfloat & $l$, long $k$, long $m$}
  Computes a relative $k$-approximation $l$ to $\Ln(p)$.  It requires $|\Ln p| > 2^m$.  See
  \SEE{xbigfloat} for definition of relative approximation.
\end{cfcode}

\begin{cfcode}{xbigfloat}{$p$.get_relative_Ln_approximation}{long $k$, long $m$}
  Returns a relative $k$-approximation to $\Ln(p)$.  It requires $|\Ln p| > 2^m$.  See
  \SEE{xbigfloat} for definition of relative approximation.
\end{cfcode}

\begin{cfcode}{xbigfloat}{$p$.relative_Ln_approximation}{long $k$, long $m$}
  Returns a relative $k$-approximation to $\Ln(p)$.  It requires $|\Ln p| > 2^m$.  See
  \SEE{xbigfloat} for definition of relative approximation.
\end{cfcode}


\SSTITLE{Operations on quasi-units, i.e., numbers of $\bbfQ^* \cdot \Or^*$}

Let $u$ be a power product of quadratic numbers.  We call $u$ a \emph{quasi-unit} of $\Or$, if
$u \in \bbfQ^* \cdot \Or^*$, for a real quadratic order $\Or$, i.e., $u$ is the product of a
rational number and a unit of $\Or$.  The set $\bbfQ^* \cdot \Or^*$ together with multiplication
forms a group with subgroup $(\bbfQ^*,\cdot)$.  The factor group $\bbfQ^* \cdot \Or^* / \bbfQ^*$
is isomorphic to $\Or^*$ by mapping $a \cdot \bbfQ^*$ to $a$ for $a\in \Or^*$.  If $u$ is a
unit, $q$ a non-zero rational number, then $\pm u$ are the only units in the equivalence class
$(qu)\bbfQ^*$.  Here, $\bbfQ^*$ denotes $\bbfQ\setminus\{0\}$.

\begin{fcode}{void}{$u$.compact_representation_of_unit}{}
  Transforms $u$ into a compact representation of the positive unit in the equivalence class $u
  \bbfQ^*$, assuming that $u$ is a quasi unit of its order $\Or$.  Calls
  \code{$u$.compact_representation($\Or$)}.  If $u$ is not a quasi unit, the result is
  undefined.  For a definition of compact representation, see the corresponding \code{assign}
  function of the class.
\end{fcode}

\begin{cfcode}{bool}{$u$.is_rational}{long $m$}
  Let $u$ be a quasi-unit of the real quadratic order $\Or$ and let $R > 2^m$, where $R$ is the
  regulator of $\Or$.  This functions returns \TRUE, if $u$ is rational, and \FALSE otherwise.  If
  $u$ is not a quasi-unit of its order, the result is undefined.
\end{cfcode}

\begin{fcode}{void}{$u$.generating_unit}{const quadratic_number_power_product & $q_1$,
    const quadratic_number_power_product & $q_2$, long $m$}%
  Let $q_1$ and $q_2$ be quasi-units of the real quadratic order $\Or$ and let $R > 2^m$, where
  $R$ is the regulator of $\Or$.  The function computes a quasi-unit $u$ of $\Or$, such that the
  subgroup generated by the canonical embedding of $u$ in $\Or^*$ is the same as the subgroup
  generated by the embeddings of $q_1$ and $q_2$.
\end{fcode}

\begin{fcode}{void}{$u$.generating_unit}{bigint & $x$, bigint & $y$,
    bigint & $M_1$, bigint & $M_2$, const quadratic_number_power_product & $q_1$,
    const quadratic_number_power_product & $q_2$, long $m$}%
  Let $q_1$ and $q_2$ be quasi-units of a real quadratic order $\Or$ and let $R > 2^m$, where
  $R$ is the regulator of $\Or$.  The function computes a quasi-unit $u$ of $\Or$, such that the
  subgroup generated by the canonical embedding of $u$ in $\Or^*$ is the same as the subgroup
  generated by the embeddings of $q_1$ and $q_2$.
  
  Identify $u$, $q_1$, and $q_2$ by its embeddings.  The function also returns $M_1$ and $M_2$
  such that $u^{M_1} = q_1$ and $u^{M_2} = q_2$, as well as $x$ and $y$ such that $q_1^x q_2^y =
  u$, respectively.  It is $x M_1 + y M_2 = 1$.
\end{fcode}

\begin{fcode}{void}{$u$.generating_unit}{base_vector< quadratic_number_power_product > & $q$, long $m$}
  Let $q$ be a vector of quasi-units of a real quadratic order $\Or$ and let $R > 2^m$, where
  $R$ is the regulator of $\Or$.  The function computes a quasi-unit $u$ of $\Or$, such that the
  subgroup generated by the canonical embedding of $u$ in $\Or^*$ is the same as the subgroup
  generated by the embeddings of the quasi-units in $q$.
\end{fcode}

\begin{fcode}{void}{$u$.generating_unit}{const matrix< bigint > & $M$,
    const base_vector< quadratic_number_standard > & $v$, long $l$}%
  Let $M$ be a matrix with $m$ rows and $n$ columns and $e$ be a vector of size $m$ of quadratic
  numbers.  It is assumed that $q_j = \prod_{i=0,\dots,m-1} v_i^{M(i,j)}$ for $j = 0,\dots,n-1$
  are quasi-units of a real quadratic order $\Or$ and $R > 2^l$, where $R$ is the regulator of
  $\Or$.  The function computes a quasi-unit $u$ of $\Or$, such that the subgroup generated by
  the canonical embedding of $u$ in $\Or^*$ is the same as the subgroup generated by the
  embeddings of the quasi-units $q_0,\dots,q_n-1$.
\end{fcode}

\begin{fcode}{void}{$u$.generating_unit}{const char * units_input_file}
  Assumes that the \code{units_input_file} contains a matrix $M$ over \SEE{bigint}, a
  \SEE{base_vector} $v$ over \SEE{quadratic_number_standard} and a \code{long} $l$.  The
  functions reads $M$, $v$, and $l$ and calls \code{$u$.generating_unit($M$, $v$, $l$)} to
  determine the generating quasi-unit $u$.
  
  Note that \code{quadratic_order::qo_l().set_last} must be called with the quadratic order of the
  quadratic numbers in $v$.  See input operator of \SEE{quadratic_number_standard} for further
  details.
\end{fcode}

\begin{fcode}{void}{quadratic_number_power_product::remove_rationals_from_quasi_units}{
    base_vector< quadratic_number_power_product > & $p$, long $l$}%
  Let $p$ be a vector of quasi units of an order $\Or$ and let the regulator of $R$ be strictly
  larger than $2^l$.  The function removes those quasi units from the vector $q$ that a rational
  numbers and adjusts the size of $q$.
\end{fcode}

\begin{Tfcode}{void}{quadratic_number_power_product::cfrac_expansion_bounded_den}{
    bigint & $\mathit{conv\uscore num}$, bigint & $\mathit{conv\uscore den}$,
    bigint $\num$, bigint $\den$, const bigint & $S$}%
  Computes the last convergent $\mathit{conv\uscore num} / \mathit{conv\uscore den}$ of the
  continued fraction expansion of $\num / \den$, of which absolute value of the denominator is
  less or equal to $S$, where $S$ must be positive.
\end{Tfcode}

\begin{Tfcode}{long}{quadratic_number_power_product::estimate_pp_accuracy}{
    const matrix < bigint > & $M$, long $m$, xbigfloat c}%
  Returns $k$ such that $k$ heuristically is an upper bound on the largest absolute accuracy
  needed in the rgcd algorithm.  $2^m$ should be a lower bound on the regulator and $c$ an upper
  bound on the absolute values of $\Ln(q)$, where $q$ runs over all principal ideal generators,
  which form the bases in the power products of the quasi units.  $k = b(c) + \max(j) b(\sum_i
  |M(i,j)|) - 2m + 9$.
\end{Tfcode}


\SSTITLE{Tests for units and quasi units}

Let $u$ be of type \code{quadratic_number_power_product}.

If a test for quasi unit on $u$ returns \FALSE, then $u$ is not a unit.  If a test for unit on
$u / \sigma(u)$ returns \FALSE, then $u$ is not a quasi unit.  In this way, tests for units can
be applied for quasi units and vice versa.  This is because a unit is a quasi unit too and if $v
= q u$ is a quasi unit, $q \in \bbfQ^*$, $u\in \Or^*$, then $v / \sigma(v) = u / \sigma(u) =
u^{2}/N(u) = u^{2}$ is a unit.

\begin{cfcode}{bool}{$u$.could_be_unit_norm_test}{int $\mathit{trials}$ = 5}
  If the function returns \FALSE, $u$ is not a unit.  The function computes the numerator $n$ and
  denominator $d$ of the norm modulo some integer $m$, respectively.  It then checks whether $n
  \equiv d$ modulo $m$.  If this is not the case, the function returns \FALSE.  If the test is
  positive for $\mathit{trials}$ chosen moduli $m$, the function returns \TRUE.
  
  Note that numbers of the form $a / \sigma(a)$ always have norm $1$, but are not necessarily
  units.
\end{cfcode}

\begin{cfcode}{bool}{$u$.could_be_quasi_unit_close_test}{}
  If the function returns \FALSE, $u$ is not a quasi unit of its order $\Or$.  The function
  approximates $\Ln(u)$ by $t$ close enough, such that one out of three ideals that are close to
  $t$ must be $\Or$.  If this is not the case, the function returns \FALSE, otherwise it returns
  \TRUE.  It uses the \code{order_close} function of \SEE{quadratic_ideal} to do this test.
\end{cfcode}

\begin{cfcode}{int}{$u$.could_be_unit_refinement_test}{}
  If the function returns $0$, $u$ is not a unit in its order $\Or$.  If it returns $1$, then
  $u$ is a unit in $\Or$.  If it returns $-1$, then $u$ is a unit in a overorder of $\Or$.  The
  function uses factor refinement, to determine its answer.  See
  \cite{Buchmann/Eisenbrand:1999}.  This method is rather slowly compared to the other unit
  tests.
\end{cfcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\IO

Let $p = (b,e)$ be of type \code{quadratic_number_power_product}.

\code{istream} operator \code{>>} and \code{ostream} operator \code{<<} are overloaded.  Input
and output of a \code{quadratic_number_power_product} are in the following format:
\begin{displaymath}
  (b, e)
\end{displaymath}
For example, to input the power product $(1 + \sqrt{5})/2$, you have to do the following.
Because elements of type \SEE{quadratic_number_standard} are entered only by their coefficients,
you first have to initialize a quadratic order $\Or$ with the discriminant $5$ and to set
\begin{verbatim}
  quadratic_order::qo_l().set_last(&O)
\end{verbatim}
Then you can call the operator \code{>>} and enter $( [(1,1,2)], [1] )$.

This behaviour may be improved in the future.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\SEEALSO

\SEE{bigfloat}, \SEE{quadratic_order}, \SEE{quadratic_unit}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\EXAMPLES

The following program generates a randomly chosen power product in the field of fractions of the
real quadratic order of discriminant $5$.  Then it squares the power product.

\begin{quote}
\begin{verbatim}
#include <LiDIA/quadratic_order.h>
#include <LiDIA/quadratic_number_standard.h>
#include <LiDIA/quadratic_number_power_product.h>
#include <LiDIA/quadratic_number_power_product_basis.h>
#include <LiDIA/base_vector.h>
#include <LiDIA/bigint.h>
#include <LiDIA/random_generator.h>

int main()
{
    // Generate order.
    //
    quadratic_order O;
    O.assign(5);

    // Generate
    // base_vector< quadratic_number > v and
    // base_vector< bigint > e.
    //
    base_vector< quadratic_number_standard > v;
    base_vector< bigint > e;
    lidia_size_t j, sizePPB;

    sizePPB = 5;
    v.set_capacity(sizePPB);
    e.set_capacity(sizePPB);

    for (j=0; j < sizePPB; j++) {
        v[j].assign_order(O);
        v[j].randomize();
        e[j].randomize(5);
    }

    // Generate power product basis b from v.
    //
    quadratic_number_power_product_basis b;
    b.set_basis(v);

    // Generate power product from b and e.
    //
    quadratic_number_power_product p;
    p.set_basis(b);
    p.set_exponents(e);

    cout << " p = " << p << endl;

    // Square the power product.
    //
    p.square(p);

    // Print result.
    //
    cout << " p^2 = " << p << endl;

    return 0;
}
\end{verbatim}
\end{quote}

For example, the program could produce the following output.
\begin{quote}
\begin{verbatim}
p = ([ (3,2,3) (4,1,3) (3,3,2) (3,3,1) (0,1,1) ],[ 3 0 0 4 2 ])
p^2 = ([ (3,2,3) (4,1,3) (3,3,2) (3,3,1) (0,1,1) ],[ 6 0 0 8 4 ])
\end{verbatim}
\end{quote}

An extensive example for the use of \code{quadratic_number_power_product} can be found in
\LiDIA's installation directory under
\path{LiDIA/src/packages/quadratic_order/quadratic_number_power_product_appl.cc}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\AUTHOR

Markus Maurer

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
