18

I want to use recursion to calculate n! in LaTeX3, but found that the result is not correct, mwe is as follows

\documentclass{article}                          
\ExplSyntaxOn
\cs_set:Nn \froac:n {
\int_compare:nNnTF{#1}={0}{1}
{
     \int_eval:n{#1*\froac:n{#1-1}}
}
}
\ExplSyntaxOff
\begin{document}
\ExplSyntaxOn
\froac:n{4}
\ExplSyntaxOff
\end{document}

thank you!

6
  • Welcome to tex.sx. Dec 8, 2021 at 0:42
  • 3
    As things break after you pass single digits, you need include paranethisis around the #1 things work: \int_eval:n{(#1)*\froac:n{#1-1}}. Dec 8, 2021 at 0:59
  • I understand, thanks for your answer!
    – ljguo
    Dec 8, 2021 at 1:01
  • 1
    l3fp supports a factorial function fact: \fp_eval:n { fact( ⟨fpexpr⟩ ) }. It works for integers between 0 and 3248. Dec 8, 2021 at 4:58
  • 1
    @Mico "Normal floating point numbers are stored in base 10, with up to 16 significant figures." according to texdoc interface3 (2021-11-22), sec. 28.9.1 "Input of floating point numbers" Dec 8, 2021 at 16:17

5 Answers 5

23

Remember that TeX is a macro language. Let's manually expand two steps of your recursion to see what's going on:

You started with

\froac:n{4}

Since 4 is not 0, this becomes

\int_eval:n{4*\froac:n{4-1}}

Now 4-1 is still not 0, so the next iteration step results in

\int_eval:n{4*\int_eval:n{4-1*\froac:n{4-1-1}}}

Of course 4-1*\froac:n{4-1-1} is not actually what you want. You can fix this by adding parentheses:

\documentclass{article}                          
\ExplSyntaxOn
\cs_set:Nn \froac:n {
\int_compare:nNnTF{#1}={0}{1}
{
     \int_eval:n{(#1)*\froac:n{(#1)-1}}
}
}
\ExplSyntaxOff
\begin{document}
\ExplSyntaxOn
\froac:n{4}
\ExplSyntaxOff
\end{document}

1
  • I understand, thanks for your answer!
    – ljguo
    Dec 8, 2021 at 1:12
14

Just for the sake of variety, here's a LuaLaTeX-based solution.

enter image description here

The froac function produces an overflow for n>20. While n>20 may seem to be a rather poor overflow threshold, do observe that the \froac:n macros in (a) @MarcelKrüger's answer and (b) @UlrichDiez's answer both have a far more stringent overflow threshold: n>12.

\documentclass{article}
\directlua{ 
   %% Define a Lua function called 'froac'
   function froac ( n )
      if n==0 or n==1 then return 1 
      else return n * froac ( n-1 )
      end
   end 
}
%% Define a LaTeX wrapper macro called '\froac'
\newcommand\froac[1]{\directlua{tex.sprint(froac(#1))}}

\begin{document}

$\begin{array}{rr}
\directlua { for i = 0 , 20 do 
                tex.sprint ( i .. "&" .. froac ( i ) .. "\\\\" )  
             end }
\end{array}$

\end{document}

Addendum/Remark: Even though the usual, i.e., recursive, definition of the factorial function counts down from n to 0 (or 1), it is actually more efficient, computationally speaking, to count up to n. Doing so allows us to evaluate the if n==0 condition just once at the start of the routine, and then to perform a deterministic for loop over a range of integers. In Lua, this idea might be implemented as follows:

-- Define 'froac' by counting _up_ rather than down
function froac(n)
   if n==0 or n==1 then return 1 
   else f=2; for i=3,n do f=f*i end; return f 
   end
end
6

\bigintcalcFac of the package bigintcalc can calcuclate factorials of numbers larger than 12, but that is not expl3. ;-)

expl3's \fp_eval:n { fact( <number> ) } is preferable because it is considerably faster and the handling of arithmetic overflow is much better.

Accumulating nested calls to \int_eval and tokens belonging to these calls by recursively calling \froac might trigger a TeX-capacity exceeded error. This is not of real importance here because one also faces the problem of arithmetic overflow.

Nonetheless for the sake of having fun playing with expansion in expl3 the following variant does not accumulate nested calls to \int_eval.
But it requires \exp_args:Nff which was introduced in 2018-05-15.
And you get an arithmetic-overflow when attempting to calculate the factorial of a number larger than 12. (Same as with \number\numexpr 1*2*3*4*5*6*7*8*9*10*11*12\relax versus \number\numexpr 1*2*3*4*5*6*7*8*9*10*11*12*13\relax.)

\documentclass{article}                          
\ExplSyntaxOn
\cs_set:Nn \froac:n {
  \exp:w \int_compare:nNnTF{#1}>{1}{\exp_args:Nf\froacstep:nn{\int_eval:n{#1}}{#1}}{\exp_end: 1}
}
\cs_set:Nn\froacstep:nn{
   % #1 result calculated so far
   % #2 factor in the previous iteration
   \int_compare:nNnTF{#2}>{2}{
     \exp_args:Nff\froacstep:nn
                  {\int_eval:n{(#1)*((#2)-1)}}
                  {\int_eval:n{(#2)-1}}
   }{ \exp_end: #1 }
}
\ExplSyntaxOff
\begin{document}
\ExplSyntaxOn
\froac:n{12}\par
\froac:n{5}\par
\froac:n{4}\par
\froac:n{3}\par
\froac:n{2}\par
\froac:n{1}\par
\froac:n{0}
\ExplSyntaxOff
\end{document}

enter image description here

5
  • +1. If I interpret this solution correctly, your variant of the \froac macro produces an overflow for n>12 -- same as in @MarcelKrüger's solution. Is this interpretation/conclusion correct?
    – Mico
    Dec 8, 2021 at 14:59
  • @Mico Yes. Same as with \number\numexpr1*2*3*4*5*6*7*8*9*10*11*12\relax versus \number\numexpr1*2*3*4*5*6*7*8*9*10*11*12*13\relax. Dec 8, 2021 at 15:07
  • We do have some bigint code but to-date it's not in the release version
    – Joseph Wright
    Dec 8, 2021 at 15:25
  • @JosephWright To what extent is the feature of doing big number arithmetic directly in TeX needed at all? I think a task like calculating factorials of large numbers in TeX at best is a nice "academic exercise". But in everyday practice one should use the tools appropriate to the task. For more complicated calculations there are computer algebra systems which can be called via \write18/\shellescape` on the console and which can deliver output to text-files that can be read by TeX... Dec 8, 2021 at 15:39
  • 1
    @UlrichDiez The obvious ones are (1) bitset operations beyond 32 bits (2) handling arbitrary user input manipulation. I have to worry about the latter for siunitx, but do that manually. Thus-far we think we can get away without a full setup for the first case, but Hekio did write his biginitcalc code largely to support bitset, so we may be wrong.
    – Joseph Wright
    Dec 8, 2021 at 15:45
5

A different approach, going up with the multiplications:

\documentclass{article}

\ExplSyntaxOn

\NewExpandableDocumentCommand{\factorial}{m}
 {
  \lijunguo_factorial:n { #1 }
 }

\cs_new:Nn \lijunguo_factorial:n
 {
  \fp_eval:n { 1 \int_step_function:nnN { 2 } { #1 } \__lijunguo_multiply:n }
 }

\cs_new:Nn \__lijunguo_multiply:n { *#1 }

% to print long factorials we add tiny breakable space between digits
\NewDocumentCommand{\longfactorial}{m}
 {
  \tl_map_inline:en { \lijunguo_factorial:n { #1 } } { ##1\hspace{0pt plus 0.1pt} }
 }
\cs_generate_variant:Nn \tl_map_inline:nn { e }

\ExplSyntaxOff

\begin{document}

\factorial{0}

\factorial{1}

\factorial{4}

\factorial{32}

\longfactorial{100}

\end{document}

The \int_step_function:nnN function will produce *2*3*… in “one swoop” so \fp_eval:n will compute the whole product (in quite an efficient way). I also add a way to print long results that wouldn't fit a line (this cannot be expandable, though.

enter image description here

You might also be interested in a shorter version: large factorials will end with many zeros, so we can group them. If you add

\NewDocumentCommand{\shortenlongfactorial}{m}
 {
  \tl_set:Nx \l_tmpa_tl { \lijunguo_factorial:n { #1 } }
  \tl_set_eq:NN \l_tmpb_tl \l_tmpa_tl
  \regex_replace_once:nnN { 0* \Z } { } \l_tmpa_tl
  $
   \tl_use:N \l_tmpa_tl
   \times
   10^{\int_eval:n { \tl_count:N \l_tmpb_tl - \tl_count:N \l_tmpa_tl } }
  $
 }

that will strip off a sequence of zeros delimited by the end of the token list and then print 10 with the exponent computed by comparing the length of the factorial and the stripped off version.

The document body

\begin{document}

\factorial{0}

\factorial{1}

\factorial{4}

\factorial{32}

\longfactorial{100}

\shortenlongfactorial{32}

\shortenlongfactorial{100}

\shortenlongfactorial{200}

\end{document}

will output

enter image description here

0

Here is a factorial function written with functional package. It is not the shortest answer, but it is very intuitive since this package emulates functional programming in Lua language. The evaluation of functions is from inside to outside.

-- lua code for comparison --
-- define a function --
function Fact (n)
  if n == 0 then
    return 1
  else
    return n * Fact(n-1)
  end
end
-- use the function --
print(Fact(4))
\documentclass{article}
\usepackage{functional}
\Functional{scoping=true} % make every function become a group
\begin{document}

\IgnoreSpacesOn
\PrgNewFunction \Fact { m } {
  \IntCompareTF {#1} = {0} {
    \Result {1}
  }{
    \Result {\IntMathMult{#1}{\Fact{\IntEval{#1-1}}}}
  }
}
\IgnoreSpacesOff
\Fact{4}

\end{document}

Note that with this package, you need to pass return values of functions with \Result command.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.