我正在用 LaTeX 编写 GCD 计算器。
这里我写了欧几里得的递归算法，它应该以对数时间运行。这里的代码计算了 377 和 233（即 1）的 GCD。代码运行良好，但在我的计算机上需要近 9 秒（使用 编译latexmk）。
\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{etoolbox}
\newcommand*{\programmerdiv}[2]{%
\ifnum #1 = 0\relax%
0%
\else%
\the\numexpr (2*#1 - #2) / (2 * #2) \relax%
\fi%
}
\newcommand*{\modab}[2]{%
\the\numexpr #1 - \programmerdiv{#1}{#2} * #2 \relax%
}
\newcommand*{\gcdab}[2]{%
\ifnum #2 = 0\relax%
#1%
\else%
\gcdab{#2}{\modab{#1}{#2}}%
\fi%
}
\begin{document}
\gcdab{377}{233}
\end{document}
接下来输入的斐波那契数对需要更多时间：GCD(610, 377) 需要 32 秒才能编译；GCD(987, 610) 需要 240 秒。编译时间的增长并不在我的预期之内，因为在我的示例中，从一对到另一对只需要一个欧几里得算法步骤。
我认为问题出在递归中：编译十二个\ifnum相应\modab数字来计算 GCD(377, 233) 仅需 640 毫秒。（没有任何计算的文件的编译时间约为 610 毫秒）。
\begin{document}
\ifnum 233 = 0\relax
\else
\modab{377}{233}
\ifnum 144 = 0\relax
\else
\modab{233}{144}
\ifnum 89 = 0\relax
\else
\modab{144}{89}
\ifnum 55 = 0\relax
\else
\modab{89}{55}
\ifnum 34 = 0\relax
\else
\modab{55}{34}
\ifnum 21 = 0\relax
\else
\modab{34}{21}
\ifnum 13 = 0\relax
\else
\modab{21}{13}
\ifnum 8 = 0\relax
\else
\modab{13}{8}
\ifnum 5 = 0\relax
\else
\modab{8}{5}
\ifnum 3 = 0\relax
\else
\modab{5}{3}
\ifnum 2 = 0\relax
\else
\modab{3}{2}
\ifnum 1 = 0\relax
\else
\modab{2}{1}
\ifnum 0 = 0\relax
1
\else
\fi
\fi
\fi
\fi
\fi
\fi
\fi
\fi
\fi
\fi
\fi
\fi
\fi
\end{document}
这个实现有什么问题？为什么我的递归需要这么长时间？是否可以在 LaTeX 中编写正确的递归？
答案1
让我们看看当你这样做时会发生什么\gcdab{377}{233}。第一个扩展变为
\ifnum233=0 \else\gcdab{233}{\modab{#1}{#2}}\fi
条件为假，所以你得到
\gcdab{233}{\modab{377}{233}}\fi
即成为
\ifnum\modab{377}{233}=0 0 \else\gcdab{\modab{377}{233}}{\modab{233}{\modab{377}{233}}}\fi\fi
等等，总是延续仍未计算数字。
仅作为示例，我尝试\gcdab{13}{8}使用\tracingmacros=1；我在此仅报告有关扩展的行\gcdab，这证实了我上面的说法。（注意：我删除了行中的\relaxafter ：只要在之后留一个空格或结束行，就不需要它；添加它实际上是一种不好的编程风格，因为它会在输入流中留下一堆不需要的标记）。0\ifnum0\relax
\gcdab #1#2->\ifnum #2 = 0 #1\else \gcdab {#2}{\modab {#1}{#2}}\fi
#1<-13
#2<-8
\gcdab #1#2->\ifnum #2 = 0 #1\else \gcdab {#2}{\modab {#1}{#2}}\fi
#1<-8
#2<-\modab {13}{8}
\gcdab #1#2->\ifnum #2 = 0 #1\else \gcdab {#2}{\modab {#1}{#2}}\fi
#1<-\modab {13}{8}
#2<-\modab {8}{\modab {13}{8}}
\gcdab #1#2->\ifnum #2 = 0 #1\else \gcdab {#2}{\modab {#1}{#2}}\fi
#1<-\modab {8}{\modab {13}{8}}
#2<-\modab {\modab {13}{8}}{\modab {8}{\modab {13}{8}}}
\gcdab #1#2->\ifnum #2 = 0 #1\else \gcdab {#2}{\modab {#1}{#2}}\fi
#1<-\modab {\modab {13}{8}}{\modab {8}{\modab {13}{8}}}
#2<-\modab {\modab {8}{\modab {13}{8}}}{\modab {\modab {13}{8}}{\modab {8}{\modab {13}{8}}}}
\gcdab #1#2->\ifnum #2 = 0 #1\else \gcdab {#2}{\modab {#1}{#2}}\fi
#1<-\modab {\modab {8}{\modab {13}{8}}}{\modab {\modab {13}{8}}{\modab {8}{\modab {13}{8}}}}
#2<-\modab {\modab {\modab {13}{8}}{\modab {8}{\modab {13}{8}}}}{\modab {\modab {8}{\modab {13}{8}}}{\modab {\modab {13}{8}}{\modab {8}{\modab {13}{8}}}}}
这是一个始终扩展直至获得明确数字的版本。并且与 David 的版本相反，它是完全可扩展的。
\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{etoolbox}
\makeatletter
\newcommand*{\programmerdiv}[2]{%
\ifnum #1 = 0
\expandafter\@secondoftwo
\else
\expandafter\expandafter\expandafter\@firstoftwo
\fi
{\the\numexpr (2*#1 - #2) / (2 * #2) \relax}%
{0}%
}
\newcommand*{\modab}[2]{%
\the\numexpr #1 - \programmerdiv{#1}{#2} * #2 \relax
}
\newcommand*{\gcdab}[2]{%
\ifnum #2 = 0
\expandafter\@secondoftwo
\else
\expandafter\expandafter\expandafter\@firstoftwo
\fi
{\expanded{\noexpand\gcdab{#2}{\modab{#1}{#2}}}}%
{#1}%
}
\makeatother
\begin{document}
\gcdab{37745585}{55555555}
\end{document}
我尝试进行了 10000 次计算，程序在我的计算机上运行了 1 秒。
\gcdab{13}{8}以下是日志文件中的类似报告\tracingmacros=1
\gcdab #1#2->\ifnum #2 = 0 \expandafter \@secondoftwo \else \expandafter \expandafter \expandafter \@firstoftwo \fi {\expanded {\noexpand \gcdab {#2}{\modab {#1}{#2}}}}{#1}
#1<-13
#2<-8
\gcdab #1#2->\ifnum #2 = 0 \expandafter \@secondoftwo \else \expandafter \expandafter \expandafter \@firstoftwo \fi {\expanded {\noexpand \gcdab {#2}{\modab {#1}{#2}}}}{#1}
#1<-8
#2<-5
\gcdab #1#2->\ifnum #2 = 0 \expandafter \@secondoftwo \else \expandafter \expandafter \expandafter \@firstoftwo \fi {\expanded {\noexpand \gcdab {#2}{\modab {#1}{#2}}}}{#1}
#1<-5
#2<-3
\gcdab #1#2->\ifnum #2 = 0 \expandafter \@secondoftwo \else \expandafter \expandafter \expandafter \@firstoftwo \fi {\expanded {\noexpand \gcdab {#2}{\modab {#1}{#2}}}}{#1}
#1<-3
#2<-2
\gcdab #1#2->\ifnum #2 = 0 \expandafter \@secondoftwo \else \expandafter \expandafter \expandafter \@firstoftwo \fi {\expanded {\noexpand \gcdab {#2}{\modab {#1}{#2}}}}{#1}
#1<-2
#2<-1
\gcdab #1#2->\ifnum #2 = 0 \expandafter \@secondoftwo \else \expandafter \expandafter \expandafter \@firstoftwo \fi {\expanded {\noexpand \gcdab {#2}{\modab {#1}{#2}}}}{#1}
#1<-1
#2<-0
强制expl3实施：
\documentclass{article}
\ExplSyntaxOn
\NewExpandableDocumentCommand{\gcdab}{mm}
{
\dkozl_gcdab:nn { #1 } { #2 }
}
\cs_new:Nn \dkozl_gcdab:nn
{
\int_compare:nTF { #2 = 0 }
{ #1 }
{ \dkozl_gcdab:ne { #2 } { \int_mod:nn { #1 } { #2 } } }
}
\cs_generate_variant:Nn \dkozl_gcdab:nn { ne }
\ExplSyntaxOff
\begin{document}
\gcdab{37745585}{55555555}
\end{document}
答案2
在第一个版本中，你想\modab尽早评估
\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{etoolbox}
\makeatletter
\newcommand*{\programmerdiv}[2]{%
\ifnum #1 = \z@
0%
\else
\the\numexpr (2*(#1) - (#2)) / (2 * (#2)) \expandafter\relax
\fi
}
\newcommand*{\modab}[2]{%
\the\numexpr #1 - \programmerdiv{#1}{#2} * (#2) \relax
}
\newcommand*{\gcdab}[2]{%
\ifnum #2 = \z@
#1%
\else
\edef\z{\noexpand\gcdab{#2}{\modab{#1}{#2}}}\z
\fi
}
\def\afterfi#1\fi{\fi#1}
\begin{document}
\gcdab{377}{233}
\end{document}