# Outer loop terminating early

I'm trying to implement the Euclidean Algorithm in LaTeX. Yes, I know I could do it more easily in python, but that's not the point. I have an inner loop (extracted to a macro) to compute the remainder of one counter divided by another counter. The outer loop should perform the inner loop, swap the values of the counters, and then repeat until one of the counters is 0.

\documentclass{article}
\usepackage{calc}
\setlength{\parskip}{\baselineskip}
\setlength{\parindent}{0pt}

\newcommand{\computeRemainder}[2]{%
\loop
\relax
\ifnum \value{#1} > \value{#2}
\repeat
\loop
\relax
\ifnum \value{#1} < 0
\repeat}

\newcommand{\swapCounters}[2]{%
\addtocounter{#1}{\value{#2}} % cA = A + B
\addtocounter{#2}{\value{#1}} % cB = A + 2B
\setcounter{#2}{2*\value{#1}+\value{#2}} % cB = A
\setcounter{#1}{-\value{#1}} % cA = B
}

\begin{document}

\newcounter{counterA}
\setcounter{counterA}{45}
\newcounter{counterB}
\setcounter{counterB}{27}

Before: $$A = \thecounterA, \; B = \thecounterB$$ \\
\loop
\computeRemainder{counterA}{counterB}
\swapCounters{counterA}{counterB}
\ifnum \value{counterB} > 0
Since this is true, shouldn't the loop continue? \\
\repeat
End: $$A = \thecounterA, \; B = \thecounterB$$

\end{document}


The above code produces the following output:

My understanding of loops would suggest that, if it prints the text between \ifnum \value{counterB} > 0 and \repeat, it should repeat the loop. However, after this executes, both counterA and counterB are greater than 0. Any idea why the outer loop won't continue?

• you can't nest \loop at the same grouping level tex.stackexchange.com/questions/22877/tex-nested-loops Oct 4, 2018 at 21:57
• Thanks! That fixed it, and it pointed out another bug I had. (The first part of \computeRemainder should be >= instead of >, but I think LaTeX doesn't have >=, so I added an \ifnum \value{#1} = \value{#2} clause to subtract once more if needed.) Oct 4, 2018 at 22:30
• as it's integer arithmetic if a >=b then x else y is same as if a<b then y else x Oct 4, 2018 at 22:44
• \unless\ifnum a<b is the same as \ifnum a>=b also in the context of \loop. Oct 4, 2018 at 22:54
• I didn't use a<b because I think \loop ignores the false case. Thanks @egreg for pointing out the \unless macro works. Oct 5, 2018 at 13:36

You can't nest \loop at the same level of grouping, see Tex Nested Loops

For the problem of >= you can use

\loop\unless\ifnum \value{#1} < \value{#2}


You may also be interested in a fully expandable version.

\documentclass{article}
\usepackage{xparse}

\ExplSyntaxOn
\NewExpandableDocumentCommand{\euclid}{mm}
{
\int_compare:nTF { \int_abs:n { #1 } < \int_abs:n { #2 } }
{
\egreg_euclid:ff { \int_abs:n { #2 } } { \int_abs:n { #1 } }
}
{
\egreg_euclid:ff { \int_abs:n { #1 } } { \int_abs:n { #2 } }
}
}

\cs_new:Nn \egreg_euclid:nn
{
\int_compare:nTF { #2 = 0 }
{ #1 } % end
{ \egreg_euclid:nf { #2 } { \int_mod:nn { #1 } { #2 } } }
}
\cs_generate_variant:Nn \egreg_euclid:nn { nf , ff }
\ExplSyntaxOff

\begin{document}

\euclid{45}{27}

\euclid{45}{-27}

\euclid{27}{45}

\euclid{10}{0}

\euclid{0}{0}

\edef\temp{\euclid{2345}{356}}

\texttt{\meaning\temp}

\end{document}


The \egreg_euclid:nn macro calls itself recursively (using a variant in the subsequent calls in order to use “explicit” values for efficiency).

Also negative values are accepted and normalized at startup, so the gcd is always nonnegative.

Here's it accompanied by a \fulleuclid macro that shows the steps (only nonnegative numbers).

\documentclass{article}
\usepackage{xparse,amsmath}

\ExplSyntaxOn
\NewExpandableDocumentCommand{\euclid}{mm}
{
\int_compare:nTF { \int_abs:n { #1 } < \int_abs:n { #2 } }
{
\egreg_euclid:ff { \int_abs:n { #2 } } { \int_abs:n { #1 } }
}
{
\egreg_euclid:ff { \int_abs:n { #1 } } { \int_abs:n { #2 } }
}
}

\cs_new:Nn \egreg_euclid:nn
{
\int_compare:nTF { #2 = 0 }
{ #1 } % end
{ \egreg_euclid:nf { #2 } { \int_mod:nn { #1 } { #2 } } }
}
\cs_generate_variant:Nn \egreg_euclid:nn { nf , ff }

\NewDocumentCommand{\fulleuclid}{mm}
{
\tl_clear:N \l_egreg_fulleuclid_swap_tl
\seq_clear:N \l_egreg_fulleuclid_steps_seq
\int_compare:nTF { #1 < #2 }
{
\tl_set:Nn \l_egreg_fulleuclid_swap_tl { #1 &\leftrightarrow #2 \\ }
\egreg_fulleuclid:nn { #2 } { #1 }
}
{
\egreg_fulleuclid:nn { #1 } { #2 }
}
\begin{align}
\tl_use:N \l_egreg_fulleuclid_swap_tl
\seq_use:Nn \l_egreg_fulleuclid_steps_seq { \\ }
\end{align}
}

\tl_new:N \l_egreg_fulleuclid_swap_tl
\seq_new:N \l_egreg_fulleuclid_steps_seq

\cs_new_protected:Nn \egreg_fulleuclid:nn
{
\int_compare:nF { #2 = 0 }
{
\seq_put_right:Nx \l_egreg_fulleuclid_steps_seq
{
#1 &= #2 \exp_not:N \cdot
\int_div_truncate:nn { #1 } { #2 } +
\int_mod:nn { #1 } { #2 }
}
\egreg_fulleuclid:nf { #2 } { \int_mod:nn { #1 } { #2 } }
}
}
\cs_generate_variant:Nn \egreg_fulleuclid:nn { nf }
\ExplSyntaxOff

\begin{document}

\euclid{45}{27}

\euclid{45}{-27}

\euclid{27}{45}

\euclid{10}{0}

\euclid{0}{0}

\edef\temp{\euclid{2345}{356}}

\texttt{\meaning\temp}

\fulleuclid{356}{2345}

\end{document}