LaTeX \newcommand recursion gets very slow

Question

I am writing a GCD calculator in LaTeX.

Here I wrote Euclid's recursive algorithm, which should work with logarithmic time. The code here counts GCD of 377 and 233 (which is 1). The code works fine, but takes almost nine seconds on my machine (compiled with 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}

The next pairs of fibonacci sequence numbers as input take much more time: GCD(610, 377) takes 32 seconds to compile; GCD(987, 610) takes 240 seconds. Such growth in compile time is not what I expect, as getting from one pair to another in my examples takes just one Euclid's algorithm step.

I believe the problem is in the recursion: compiling twelve \ifnum and \modab of respective numbers for calculating GCD(377, 233) takes just 640 ms. (the compilation time of the file without any computations is around 610ms).

\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}

What is the problem with this implementation? Why does my recursion take so long and is it possible to write a proper recursion in LaTeX?

Answer 1

Let's see what happens when you do \gcdab{377}{233}. The first expansion becomes

\ifnum233=0 \else\gcdab{233}{\modab{#1}{#2}}\fi

The conditional is false, so you get

\gcdab{233}{\modab{377}{233}}\fi

that becomes

\ifnum\modab{377}{233}=0 0 \else\gcdab{\modab{377}{233}}{\modab{233}{\modab{377}{233}}}\fi\fi

and so on, always carrying over the still uncomputed numbers.

Just by way of example, I tried \gcdab{13}{8} with \tracingmacros=1; I report here just the lines about expansions of \gcdab, which confirm what I claimed above. (Note: I removed the \relax after 0 in the \ifnum lines: it's not needed so long as you leave a blank space, or endline, after 0; it's actually bad programming style to add it, because it leaves a bunch of unwanted \relax tokens in the input stream).

\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}}}}}

Here's a version that always expands until getting an explicit number. And is fully expandable, contrary to David's.

\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}

I tried doing the computation 10000 times and the program ran for 1 second on my machine.

Here's the analogous report in the log file for \gcdab{13}{8} with \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

---

The mandatory expl3 implementation:

\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}

Answer 2

In the first version you want to evaluate \modab earlier

\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}