Take the 2-minute tour ×
TeX - LaTeX Stack Exchange is a question and answer site for users of TeX, LaTeX, ConTeXt, and related typesetting systems. It's 100% free, no registration required.

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:

  1. 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!
  2. 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}
    
share|improve this question
    
All of what you're describing is as a result of using the [H] float specifier. Unfortunately, all of this cannot be fixed by merely removing it... –  Werner Nov 28 '13 at 21:20
1  
However, not forcing position (by removing the [H] float specifier), introduces further issues, like putting the algorithm at the end of the chapter (completely dropping the value of the section containing it)! –  Abdullah Heyari Nov 28 '13 at 21:29
1  
You can set a \FloatBarrier to change this (or other features of the placeins package) –  masu Nov 29 '13 at 7:44

1 Answer 1

up vote 2 down vote accepted

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:

  1. Reword your explanations to shorten it.
  2. Split it into smaller pieces for presentation.
  3. 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]

to

\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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.