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