AlgorithmForParallelAddition.tex

The necessary structures for computation in $\Zomega$ are constructed when an instance of this class is created. 
The set $\Zomega$ is represented by \emph{PolynomialQuotientRing} which is obtained by factorization of \emph{PolynomialRing} over integers by polynomial $m_\omega$. 
We remark that arithmetic operations in $\Zomega$ are independent on the choice of root of the  minimal polynomial $m_\omega$. Since comparison of absolute value of numbers in~$\Zomega$ is required, we specify $\omega$ by its approximate complex value to form a factor ring of rational polynomials by using class \emph{NumberField}. Elements of this class can be coerced to complex numbers and their absolute value is computed.

%Method \textbf{findWeightFunction()} links together both phases of the extending window method to find a weight function $q$ for given parametres. That is used in the methods for addition and digit set conversion to process them as local functions. There are also verification methods.
%
%Moreover, many methods for printing, plotting and saving outputs are implemented.

The constructor of class \emph{AlgorithmForParallelAddition} is 

\begin{method}{\_\_init\_\_}{minPol\_str, embd, alphabet, base, name='NumerationSystem', inputAlphabet='', printLog=True, printLogLatex=False, verbose=0}
The method takes \var{minPol\_str} which is a string of symbolic expression in the variable $x$ of an irreducible polynomial~$m_\omega$. The closest root of  \var{minPol\_str} to \var{embd} is used as the ring generator $\omega$ (see more in the documentation of \emph{NumberField} in SageMath \cite{sage}). The structures for $\Zomega$ are constructed as described above. 

A base $\beta$ is given by a symbolic expression \var{base} where \verb+omega+ is used for $\omega$.
Setter \fun{setBase}{base} checks if the base $\beta$ is expanding and inspects whether it has a real conjugate greater than one.

The parameter \var{alphabet} and \var{inputAlphabet} expect a string with a list of symbolic expressions (use \verb+omega+ for $\omega$) to define an alphabet $\A$ and input alphabet $\B$. If the string \var{alphabet} is empty, then an alphabet $\A\subset\Zomega$ is generated such that it contains all representatives modulo $\beta$ and $\beta-1$ in $\Zomega$, see the end of Section~\ref{sec:minimalAlphabet}. %If \var{alphabet} is \verb+oneMore+, then a bigger alphabet is generated.  
If \var{alphabet} is \verb+'integer'+, % \verb+integer2+ or \verb+integer3+,
 an algorithm attempts to find an integer alphabet. An exception is raised when alphabet generating fails. If  \var{inputAlphabet} is empty, then $\B$ is set to $\A+\A$.

Messages saved to logfile during existence of an instance are printed (using \LaTeX) on standard output depending on \var{printLog} and \var{printLogLatex}. The level of messages for a development is set by \var{verbose}.

Example:
\verb|alg= AlgorithmForParallelAddition('x^2+x+1',-0.5+0.8*I,|

\verb| '[0,1,-1,omega,-omega,-omega-1,omega+1]','omega-1','Eisenstein')|
\end{method}

Methods for the construction of a weight function for a digit set conversion from $\B$ to $\A$ are the following.

\newpage
\begin{method}{checkAlphabet}{}
It is verified that the alphabet $\A$ contains all representatives mod $\beta$ in  and that all elements of the input alphabet $\B$ have their representatives mod $\beta-1$ in the alphabet $\A$ according to Theorem~\ref{thm:lowerBoundAlphabet}, including the case when the base $\beta$ has a real conjugate greater than one.
\end{method}

\begin{method}{\_findWeightCoefSet}{max\_iterations, method\_number}
An instance of \emph{WeightCoefficientsSetSearch(self,method\_number)} is created and  its method \fun{findWeightCoefficientsSet}{max\_iterations} is called to obtain a weight coefficients set $\Q$.
\end{method}

\begin{method}{\_findWeightFunction}{max\_input\_length,method\_number}
An instance of \emph{WeightFunctionSearch(self, $\Q$, method\_number, maxInputs)} is created and its methods \fun{check\_one\_letter\_inputs}{max\_input\_length} and \\ \fun{findWeightFunction}{max\_input\_length} are called to obtain a weight function~$q$.
\end{method}


\begin{method}{findWeightFunction}{ max\_iterations=infinity, max\_input\_length=infinity, \\ method\_weightCoefSet=None, method\_weightFunSearch=None}
The method calls \fun{checkAlphabet}{} and returns the weight function $q$ obtained by calling \\ \fun{\_findWeightCoefSet}{max\_iterations, method\_weightCoefSet} and \\ \fun{\_findWeightFunction}{max\_input\_length, method\_weightFunSearch}.
\end{method}

%The important function for the searching for possible weight coefficients is
%
%\begin{method}{divideByBase}{divided\_number}
%Using Theorem \ref{thm:divisibility}, check if \var{divided\_number} is divisible by the base $\beta$. If it is so, return the result of division, else return \var{None}.
%\end{method}


Methods for the addition and the digit set conversion computable in parallel are the following:

\begin{method}{addParallel}{a,b}
Numbers represented by the lists of digits \var{a} and \var{b} are summed up digitwise and the result is converted by \fun{parallelConversion}{}. If $\B\neq\A+\A$ and a digitwise sum is not in $\B$, then an exception is raised.
\end{method}


\begin{method}{parallelConversion}{\_w}
The method returns $(\beta,\A)$-representation of the number represented by the list \var{\_w} of digits from the input alphabet $\B$. According to the equation \eqref{eq:conversionFormula}, it is computed locally by using the weight function $q$. An exception is raised when an outputted digit is not in the alphabet $\A$.
\end{method}


%\begin{method}{localConversion}{w}
%Return converted digit according to the equation \eqref{eq:conversionFormula} for the list of input digits \var{w}.
%\end{method}


The correctness of the implementation of the extending window for a given numeration system can be verified by
 
\begin{method}{sanityCheck\_conversion}{num\_digits}
It is checked whether the values of all possible numbers of the length \var{num\_digits} with digits in the input alphabet $\B$ are the same as their $(\beta, \A)$-representation obtained by \fun{parallelConversion}{}.   
\end{method}