![大算法造成大混乱](https://linux22.com/image/279934/%E5%A4%A7%E7%AE%97%E6%B3%95%E9%80%A0%E6%88%90%E5%A4%A7%E6%B7%B7%E4%B9%B1.png)
我正在写一篇文档,其中需要包含 Crandall 和 Pomerance 书中提到的数域筛选 (NFS) 算法的描述。该算法的伪代码很长,足以填满一张 A4 纸,我面临以下两个问题:
- 算法周围的空白似乎没有得到适当分布;导致算法被切断,而不是自然地继续下一页,同时覆盖页码!
前几页的内容排列以意想不到的方式发生了改变;留下了一张空白页,各节/小节看起来间距不当(分散)。
\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}
答案1
可选参数的
[Hhtbp]
作用类似于图形环境。该H
参数强制算法停留在原处。如果使用,算法将不再是浮动对象。注意:算法不能被剪切,因此如果H
在给定位置没有足够的空间放置带有选项的算法,LaTeX 将放置空白并将算法放在下一页。
为大型浮动环境提供更合理的放置选项:tbp
。
但是现在浮动对于页面来说仍然太大(这导致它在文档中被推得更靠后,正如您在评论中提到的那样)。您有三个选择:
- 重新措辞你的解释以使其更简短。
- 将其分成更小的块以便于展示。
- 将其设置为较小的字体大小以适合。
由于选项 1 和 2 取决于您的算法和领域,因此我在此展示了选项 3。但我认为对于真正的算法/文档来说,选项 1 或 2 更可取。
我所做的只是改变了你的台词
\begin{algorithm}[H]
到
\begin{algorithm}[tbp]\footnotesize
结果如下(此 MWE 的第 1 页,共 1 页,没有前导空白页,日志文件中也没有过满的框或浮动过大的警告):