1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2%%
3%%  quadratic_number_power_product_basis.tex        LiDIA documentation
4%%
5%%  This file contains the documentation of the class
6%%  quadratic_number_power_product_basis.
7%%
8%%  Copyright (c) 1999 by the LiDIA Group
9%%
10%%  Author: Markus Maurer
11%%
12
13%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
14
15\NAME
16
17\CLASS{quadratic_number_power_product_basis} \dotfill
18basis for power products of quadratic numbers.
19
20
21%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
22
23\ABSTRACT
24
25\code{quadratic_number_power_product_basis} is a class that represents a basis for a power
26product of quadratic numbers.  Its main use is to reduce memory needed by power products by
27providing a basis that can be shared by several power products and to increase efficiency in
28power product computations by speeding up the computation of approximations to the logarithms of
29the elements of the basis.
30
31
32%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
33
34\DESCRIPTION
35
36A \code{quadratic_number_power_product_basis} is an array $b$ of elements of type
37\SEE{quadratic_number_standard}.  Let $n$ be the number of elements
38in $b$.  Then
39\begin{displaymath}
40  b = (b_{0}, \dots, b_{n-1}) \enspace,
41\end{displaymath}
42where $b_{i}$ ($0\leq i < n$) represents a quadratic number.  In principle, it is possible that
43the numbers in the basis belong to different quadratic number fields.
44
45
46%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
47
48\CONS
49
50\begin{fcode}{ct}{quadratic_number_power_product_basis}{}
51  creates a basis with no elements.
52\end{fcode}
53
54\begin{fcode}{dt}{~quadratic_number_power_product_basis}{}
55  deletes the object.
56\end{fcode}
57
58
59%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
60
61\ASGN
62
63Let $b$ be of type \code{quadratic_number_power_product_basis}.  The operator \code{=} is
64overloaded.  The following functions are also implemented:
65
66\begin{fcode}{void}{$b$.assign}{const quadratic_number_power_product_basis & $c$}
67  $c$ is copied to $b$.
68\end{fcode}
69
70\begin{fcode}{void}{$b$.set_basis}{const base_vector< quadratic_number_standard > & $c$}
71  $b \assign (c[0], \dots, c[s-1])$, where $s = \code{$c$.get_size()}$.
72\end{fcode}
73
74\begin{fcode}{void}{$b$.set_basis}{const quadratic_number_standard & $c$}
75  $b \assign (c)$.
76\end{fcode}
77
78\begin{fcode}{void}{$b$.concat}{const quadratic_number_power_product_basis & $c$,
79    const quadratic_number_standard & $q$}%
80  $b \assign (c_0, \dots, c_{n-1}, q)$, where $n$ is the number of elements in $c$.
81\end{fcode}
82
83\begin{fcode}{void}{$b$.concat}{const quadratic_number_power_product_basis & $c$,
84    const quadratic_number_power_product_basis & $d$}%
85  $b \assign (c_0, \dots, c_{m-1}, d_0, \dots, d_{n-1})$, where $m$ and $n$ are the number of elements
86  in $c$ and $d$, respectively.
87\end{fcode}
88
89
90%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
91
92\ACCS
93
94Let $b$ be of type \code{quadratic_number_power_product_basis}.
95
96\begin{cfcode}{const base_vector< quadratic_number_standard > &}{$b$.get_basis}{}
97  Returns a \code{const} reference to a vector $[b_0, \dots, b_{n-1}]$, where $n$ is the number
98  of elements in $b$.  As usual, the \code{const} reference should only be used to create a copy
99  of the vector or to immediately apply another operation on the vector, because after the next
100  operation applied to $b$ the obtained reference may be invalid.
101\end{cfcode}
102
103\begin{cfcode}{lidia_size_t}{$b$.get_size}{}
104  Returns the number of elements of $b$.
105\end{cfcode}
106
107\begin{cfcode}{const quadratic_number_standard &}{$b$.operator[]}{lidia_size_t $i$}
108  Returns a \code{const} reference to $b_i$, if $0 \leq i < n$, where $n$ is the number of
109  elements in $b$.  If $i$ is outside that range, the \LEH will be called.  As usual, the
110  \code{const} reference should only be used to create a copy or to immediately apply another
111  operation to it, because after the next operation applied to $b$ the obtained reference may be
112  invalid.
113\end{cfcode}
114
115\begin{cfcode}{const quadratic_order &}{$b$.get_order}{}
116  Returns a \code{const} reference to the quadratic order of $b_0$.  If the number of elements
117  of $b$ is zero, the \LEH will be called.  This function is for convenience in the case, where
118  all numbers are defined over the same order.  As usual, the \code{const} reference should only
119  be used to create a copy or to immediately apply another operation to it, because after the
120  next operation applied to $b$ the obtained reference may be invalid.
121\end{cfcode}
122
123
124%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
125
126\COMP
127
128\begin{fcode}{bool}{operator==}{const quadratic_number_power_product_basis & $c$,
129    const quadratic_number_power_product_basis & $d$}%
130  Returns \TRUE, if the address of $c$ is equal to the address of $d$.  Otherwise, it returns
131  \FALSE.
132\end{fcode}
133
134
135%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
136
137\BASIC
138
139Let $b$ be of type \code{quadratic_number_power_product_basis}.
140
141\begin{cfcode}{const xbigfloat &}{$b$.get_absolute_Ln_approximation}{long $k$, lidia_size_t $i$}
142  Returns a \code{const} reference to an absolute $k$-approximation to $\Ln(b_i)$, where $\Ln$
143  is the Lenstra logarithm (see \SEE{xbigfloat}, \SEE{quadratic_number_standard}).  If $i < 0$
144  or $n \leq i$, where $n$ is the number of elements in $b$, the \LEH will be called.
145  Approximations to the logarithm and their accuracies are internally stored.  Hence, if $k$ is
146  less than or equal to the currently stored accuracy, the previously computed approximation is
147  only truncated to create the absolute $k$ approximation.  Only if $k$ is larger, a new
148  approximation is computed.
149
150  As usual, the \code{const} reference should only be used to create a copy or to immediately
151  apply another operation to it, because after the next operation applied to $b$ the obtained
152  reference may be invalid.
153\end{cfcode}
154
155\begin{fcode}{void}{$b$.absolute_Ln_approximations}{const matrix< bigint > & $M$, long $k$}
156  This function computes approximations to the logarithms of the base elements, that are
157  internally stored.  More precisely, let $n$ be the number of elements of $b$.  $M$ must be a
158  matrix with $n$ rows; otherwise the \LEH is called.  Let $m$ be the number of columns of $M$.
159  For each $0\leq i < n$ the function computes and internally stores an absolute $k + 2 + b(n) +
160  t$ approximation $l_i$ to $\Ln(b_i)$, where $t = \max_{0\leq j < m} b(M_i,j)$, where $M_i,j$
161  is the element in row $i$ and column $j$ of $M$.  This implies that $\left|\sum_{i=0}^{n-1}
162    e_{i,j} l_i - \Ln(\prod_{i=0}^{n-1} b_i^{M_{i,j}})\right| < 2^{-k-2}$ for each $0\leq j <
163  m$.  Hence, when building power products where the basis is $b$ and the exponents are given by
164  the columns of $M$, no recomputations of logarithms is necessary, when asking for absolute
165  $k$-approximations to the logarithm of the power product.
166\end{fcode}
167
168\begin{cfcode}{bool}{$b$.check_Ln_correctness}{lidia_size_t $\mathit{trials}$ = 5}
169  Uses the function \code{check_Ln_correctness($\mathit{trials}$)} of the class
170  \SEE{quadratic_number_standard} to check the correctness of the
171  logarithm approximation for the base elements.  Returns \TRUE, if all the tests work correct
172  and \FALSE otherwise.
173\end{cfcode}
174
175\begin{fcode}{void}{$b$.conjugate}{}
176  Replaces $b_i$ by its conjugate for each $0 \leq i <n$, where $n$ is the number of elements of
177  $b$.
178\end{fcode}
179
180
181%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
182
183\IO
184
185\code{istream} operator \code{>>} and \code{ostream} operator \code{<<} are overloaded.  Input
186and output of a \code{quadratic_number_power_product_basis} are in the format of a
187\SEE{base_vector} of elements of type
188\SEE{quadratic_number_standard}.
189
190
191%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
192
193\SEEALSO
194
195\SEE{xbigfloat}, \SEE{base_vector},
196\SEE{quadratic_number_standard},
197\SEE{quadratic_number_power_product},
198\SEE{quadratic_order}.
199
200
201%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
202
203\AUTHOR
204
205Markus Maurer
206