[Tex/LaTex] Big algorithm causing big mess

algorithm2espacing

I am writing a document in which I needed to include the description of the Number Field Sieve (NFS) algorithm as mentioned in the book by Crandall and Pomerance. The algorithm's pseudo code is lengthy enough to fill an A4 page, and I am facing the following two problems:

The white spaces around the algorithm do not seem to be properly distributed; causing the algorithm to get chopped, instead of naturally proceeding on the next page, meanwhile covering the page number!

The arrangement of the contents in previous pages is altered in such an unexpected way; a blank page is left, the sections/subsections look improperly spaced (scattered).

\documentclass{article}
\usepackage{fullpage}
\usepackage{amssymb}        % for some mathematical symbols
\usepackage[format=hang, font=small, labelfont=bf]{caption} % makes the table caption in bold
\usepackage{mathtools}      % for cieling function paranthesis
\usepackage{float}          % for fixing the position of the tables and figures

\usepackage[ruled, vlined, algosection, norelsize]{algorithm2e} % The algorithms writing 
\SetAlFnt{\sf} % Set the algorithms font style to sans serif
\begin{document}

\begin{algorithm}[H]
\caption{Number Field Sieve \label{alg:NFS}}
%\DontPrintSemicolon
\SetKwBlock{Setup}{Setup}{}
\SetKwBlock{TheSieve}{The Sieve}{}
\SetKwBlock{TheMatrix}{The Matrix}{}
\SetKwBlock{LinearAlgebra}{Linear Algebra}{}
\SetKwBlock{SquareRoots}{Square Roots}{}
\SetKwBlock{Factorization}{Factorization}{}
\SetAlFnt{\small \sf}
\KwIn{An odd composite number $N$ that is not a power.}
\KwOut{A nontrivial factorization of $N$}
{
\BlankLine
\nl \Setup
{
        $d = \left \lfloor 3 \left(\frac{\ln N}{\ln \ln N} \right)^{\frac{1}{3}} \right \rfloor$ \tcp*[r]{This $d$ has $d^{2d^2} < N$.}
        $B = \left \lfloor \exp((\frac{8}{9})^{1/3} (\ln N)^{1/3} (\ln \ln N)^{2/3}) \right \rfloor$ \tcp*[r]{Note that both $d$ and $B$ can be tuned to taste.}
        $m = \lfloor N^{1/d} \rfloor$\;
        Write $N$ in base $m$: $N = m^d + c_{d-1}m^{d-1} + \ldots + c_0$\;
        $f(x) = x^d + c_{d-1}x^{d-1} + \ldots + c_0$ \tcp*[r]{Establish the polynomial $f$.}
        Attempt to factor $f(x)$ into irreducible polynomials in $\mathbb{Z}[x]$ using the factoring algorithm in \cite{Lenstra et al. 1982} or a variant such as \cite{Cohen 2000}(p. 139)\;
        If $f(x)$ has the nontrivial factorization $g(x)h(x)$, return the (also nontrivial) factorization $N = g(m)h(m)$\;
        $F(x,y) = x^d + c_{d-1}x^{d-1}y + \ldots + c_0y^d$ \tcp*[r]{Establish the polynomial $F$.}
        $G(x, y) = x - my$\;
        \For {$(\text{prime } p \leq B)$}
        {
                compute the set $R(p) = \{ r \in [0, p-1]: f(r) \equiv 0 \pmod p \}$\;
        }
        $k =\lfloor 3\lg N \rfloor$\;
        Compute the first $k$ primes $q_1, \ldots, q_k > B$ such that $R(q_j)$ contains some element $s_j$ with
        $f'(x_j) \not \equiv 0 \pmod {q_j}$ storing the $k$ pairs $(q_j, s_j)$\;
        $B' = \sum_{p \leq B}\#R(p)$\;
        $V = 1 + \pi(B) + B' + k$\;
        $M = B$\;
        }
        \BlankLine
\nl \TheSieve
{
        Use a sieve to find a set $\mathcal{S}'$ of coprime integer pairs $(a, b)$ with $0 < |a|, b \leq M$, and $F(a, b)G(a, b)$ being $B$-smooth, until $\#\mathcal{S}' > V$, or failing this, increase $M$ and try again, or goto      \textrm{\bf Setup} and increase $B$\;
}
        \BlankLine
\nl \TheMatrix
{
        \tcp*[f]{We shall build a $\#\mathcal{S}' \times V$ binary matrix, one row per $(a, b)$ pair.}
        \tcp*[f]{We shall compute $\vec{v}(a - b\alpha)$, the binary exponent vector for $a - b\alpha$ having $V$ bits (coordinates) as follows:}\\
        Set the first bit of $\vec{v}$ to $1$ if $G(a, b) < 0$, else set this bit to 0\;
        \tcp*[f]{The next $\pi(B)$ bits depend on the primes $p \leq B$: Define $p^\gamma$ as the power of $p$ in the prime factorization of $|G(a, b)|$.}\\
        Set the bit for $p$ to $1$ if $\gamma$ is odd, else set this bit to 0\;
        \tcp*[f]{The next $B'$ bits are to correspond to the pairs $p, r$ where $p$ is a prime not exceeding $B$ and $r \in R(p)$.}\\
        Set the bit for $p, r$ to $1$ if $v_{p, r}(a - b\alpha)$ is odd, else set it to 0\;
        \tcp*[f]{Next, the last $k$ bits correspond to the pairs $q_j, s_j$.}\\
        Set the bit for $q_j, s_j$ to $1$ if $\left( \frac{a - bs_j}{q_j} \right)$ is $-1$, else set it to 0\;
        Install the exponent vector $\vec{v}(a - b\alpha)$ as the next row of the matrix\;
}
\BlankLine
\nl \LinearAlgebra
{
        By some method of linear algebra, find a nonempty subset $\mathcal{S}$ of $\mathcal{S}'$ such that
        $\sum_{(a, b) \in \mathcal{S}} \vec{v}(a - b\alpha)$ is the $0$-vector $(\bmod{2})$\;
}
\BlankLine
\nl \SquareRoots
{
        Use the known prime factorization of the integer square $\prod_{(a, b) \in \mathcal{S}}(a - bm)$ to find a residue $v \mod n$ with $\prod_{(a, b) \in \mathcal{S}}(a - bm) \equiv v^2 \pmod{N}$\;
        By the suitable method to find the square root $\gamma$ in $\mathbb{Z}[\alpha]$ of
        $f'(\alpha)^2 \prod_{(a, b) \in \mathcal{S}}(a - b\alpha)$, and, via a simple replacement $\alpha \to m$, compute
        $u = \phi(\gamma)\pmod{N}$\;
}
\BlankLine
\nl \Factorization
{
        return $\gcd((u - f'(m)v), n)$\;
}
}
\end{algorithm}
\end{document}

Best Answer

From the algorithm2e documentation:

The optional arguments [Hhtbp] works like those of figure environment. The H argument forces the algorithm to stay in place. If used, an algorithm is no more a floating object. Caution: algorithms cannot be cut, so if there is not enough place to put an algorithm with H option at a given spot, LaTeX will place a blank and put the algorithm on the following page.

Give more sensible placement options for a large floating environment: tbp.

But now the float is still too big for the page (which causes it to be pushed far later in the document as you mentioned in a comment). You have three options:

Reword your explanations to shorten it.
Split it into smaller pieces for presentation.
Set it in a smaller font size to fit.

Because options 1 and 2 are dependent on your algorithm and field, I've shown option 3 here. But I think option 1 or 2 would be preferable for a real algorithm/document.

All I did was change your line

\begin{algorithm}[H]

\begin{algorithm}[tbp]\footnotesize

and here is the result (page 1 of 1 for this MWE, no leading blank page and no overfull boxes or float too large warnings in the log file):

enter image description here

Related Solutions

[Tex/LaTex] Export algorithm as pdf

You can use the standalone document class; a little example:

\documentclass{standalone}
\usepackage{algorithm2e}

\begin{document}

\begin{algorithm}[H]
\SetAlgoLined
\KwData{this text}
\KwResult{how to write algorithm with \LaTeX2e }
initialization\;
\While{not at end of this document}{
read current\;
\eIf{understand}{
go to next section\;
current section becomes this one\;
}{
go back to the beginning of current section\;
}
}
\caption{How to write algorithms}
\end{algorithm}

\end{document}

[Tex/LaTex] Squeezing space around algorithm construct

@kkp: The algorithm environment provided by the algorithm2e package is a "floating" environment, just like table and figure floating environments are. Hence, it can't be wrapped inside another floating group. What you are encountering -- the fact that you can't get LaTeX to place the floats anywhere close to where you want them to go -- is a commonly shared frustration of many LaTeX users. My main suggestion is to check if the algorithm floats in question occupy well more than half a page. If that's the case, you may want to change some or all of the parameters \topfraction, \bottomfraction, \textfraction, and \floatpagefraction. In many of my documents, I have the following commands in the preamble:

\renewcommand\topfraction{0.85}
\renewcommand\bottomfraction{0.85}
\renewcommand\textfraction{0.1}
\renewcommand\floatpagefraction{0.85}

With these commands, you would instruct LaTeX to allow a float -- really, a group of floats -- to occupy up to 85% of a page that also contains some text. (If a float is larger than that, it'll end up on a page by itself.)

Another suggestion I'd make is not to specify the placement options [t!] and [h!], for if LaTeX cannot satisfy this demand immediately, somewhat perversely (and counter-intuitively) the float, and all subsequent floats of the same type (figure, table, or algorithm, will be pushed back all the way to the end of the document rather than just to the next suitable page.

Addendum: Discussion of how to reduce the space between text and floats:

To change these amounts of space, you could add the following instructions (or something similar) to your document's preamble:

\setlength\floatsep{1.25\baselineskip plus 3pt minus 2pt}
\setlength\textfloatsep{1.25\baselineskip plus 3pt minus 2pt}
\setlength\intextsep{1.25\baselineskip plus 3pt minus 2 pt}

The first length governs the separation of two adjacent floats, the second sets the separation between a float that's at the top (or bottom) of a page and the text below (above) it, and the third sets the separation between a float that's in the middle of a page and the text above and below it. As you can see from this example, I've set all three lengths to the same ("rubber") value. Unless you're really really pressed for space, I wouldn't reduce the lengths even further.

Best Answer

Related Solutions

[Tex/LaTex] Export algorithm as pdf

[Tex/LaTex] Squeezing space around algorithm construct

Related Question