2

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}
    \addtocounter{#1}{-\value{#2}}
  \repeat
  \loop
    \relax
  \ifnum \value{#1} < 0
    \addtocounter{#1}{\value{#2}}
  \repeat}

\newcommand{\swapCounters}[2]{%
  \addtocounter{#1}{\value{#2}} % cA = A + B
  \addtocounter{#2}{\value{#1}} % cB = A + 2B
  \addtocounter{#1}{-\value{#2}} % cA = -B
  \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:

Output of code

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?

5
  • 3
    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.)
    – Pi Fisher
    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
  • 1
    \unless\ifnum a<b is the same as \ifnum a>=b also in the context of \loop.
    – egreg
    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.
    – Pi Fisher
    Oct 5, 2018 at 13:36

1 Answer 1

3

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).

enter image description here

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}

enter image description here

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .