16

I've heard that Latex is a Turing complete language. So I went on to write a Fibonacci program in Latex and I succeeded (without using packages). Now I want to write a factorial program in latex (without using packages). I wrote the following code:- (includes debug texts)

\documentclass{article}
\begin{document}
\typein[\n]{Enter the value of n :-}

\newcommand{\scaleup}[2]{
     \newcount\ofac
     \ofac #1\relax
     \newcount\ntemp
    \ntemp \the#2\relax
    {
        \loop
            \ifnum \ntemp>1
                \advance#1 \the\ofac\relax
                \advance\ntemp -1\relax
                nfac(m) = \the#1
                \nfac \the#1\relax


        \repeat
    }
}

\newcommand{\factorial}[1]{
    \newcount\num
    \newcount\nfac
    \newcommand{\nfacinloop}{1}
    \num #1\relax
    \nfac 1\relax
    \loop
        \ifnum \num>0
            % \huge{\the\num}
            % \scaleup{\nfac}{\num}
             \newcount\ofac
             \ofac \nfac\relax
             \newcount\ntemp
            \ntemp \the\num\relax
            {
                \loop
                    \ifnum \ntemp>1
                        \advance\nfac \the\ofac\relax
                        \advance\ntemp -1\relax
                        nfac(m) = \the\nfac
                        \nfac \the\nfac\relax
                        \renewcommand{\nfacinloop}{\the\nfac}
                        nfacinloop = \nfacinloop

                \repeat
            }           
            nfac = \the\nfac
            nfacinloop = \nfacinloop
            % \huge{\the\num}
            \advance\num -1\relax


            % \huge{\the\num}
    \repeat
}

\factorial{\n}
\end{document}

However this does not run, because each time the control exits the inner loop, the value of \nfac is reset to 1. I could not find any (without using packages) to retain the value of \nfac. Am I wrong somewhere? Please help.

Note: I used pdftex to compile.

6
  • Welcome to TeX.SX, and congratulations for daring to explore TeX beyond well-trodden paths!
    – gernot
    Sep 14, 2016 at 21:33
  • 1
    Changes to your variables are local to the group delimited by the braces {}. You have to prefix assignments with \global to make changes visible outside. E.g., try \global\nfac \the\nfac\relax in the loop.
    – gernot
    Sep 14, 2016 at 21:35
  • Do you want your command to produce spurious spaces? If not, you need to comment them!
    – cfr
    Sep 14, 2016 at 23:51
  • If you set LaTeX counters outside the loop i.e. \newcounter ..., changes within the loop should be global i.e. \setcounter, \addtocounter etc.
    – cfr
    Sep 14, 2016 at 23:52
  • 1
    you never want to have the register allocation such as \newcount inside the loop, registers are a finite resource (although there are a lot more in etex than classic tex) Sep 15, 2016 at 0:17

2 Answers 2

12

You can make assignments global using \global however you do not need any groups here so local assignments should be enough. The following for example uses a recursive macro rather than a loop

\documentclass{article}

\typein[\n]{Enter the value of n :-}

\def\factorial#1{\ffactorial{#1}1}

\def\ffactorial#1#2{%
\ifnum#1=0 \the\numexpr#2\relax
\else
\ffactorial{\the\numexpr#1-1\relax}{\the\numexpr#1*#2\relax}%
\fi}
\begin{document}

\factorial{\n}

\end{document}

however if you enter a number larger than 12, you get arithmetic overflow due to the size of the integers.

It is possible of course to not use \numexpr (which is equivalent to the \count register usage in your version) and just encode an integer as a token list of the decimal expansion and encode the arithmetic by hand. There are packages for big integer arithmetic on ctan.

2
  • Thanks for the answer, but I am new to Latex and can't understand your code. Can you add comments and explain? Sep 15, 2016 at 20:36
  • @MeetTaraviya it's the standard recursive definition of factorial written in tail recursive form for example it is algorithm B here cs.stackexchange.com/a/7822 Sep 15, 2016 at 20:39
7

There is a part of this answer (somewhere near the bottom half of it) which uses no package and computes binomial coefficients. The factorial 13! already exceeds TeX's bound hence requires extending TeX's arithmetic, the code goes around that in order for example for binomial(13,6) to be evaluated (and quite bigger coefficients too). But if the final result exceeds 2^31 arithmetic overflow will occur.

The code uses e-TeX's \numexpr (as in David's answer here). This gives opportunity to write expandable code which adds a further twist to your programming challenge.

For convenience here it is copy pasted from original location.

edit also copies over the comments which help understand the underlying maths

% Expandably computing  binomial(n,k)=n choose k

% after having replaced k by the smallest of k and n-k, and checked if
% k=0, either one of the following products produces integers at each
% mutiply/divide steps: 

% n * (n-1)/2 * (n-2)/3 * .... * (n-k+1)/k

% or

% (n-k+1) * (n-k+2)/2 * (n-k+3)/3 * ... * n/k

% eTeX \numexpr does multiply/divide in one "double-precision" step,
% thus arithmetic overflow should not happen, as long as the result is <
% 2^31 (and naturally the initial n, binomial (2147483648,0) will not
% work

% For no special reason I chose the second product. 
% (notice that as k<n-k+1 also the first product is increasing, no 
% intermediate thing can cause overflow if the final thing does not)

% Each (n-k+j)/j step could be seen as (n-k)/j + 1, thus only j would need 
% incrementing;  up to the price of an extra addition, and I preferred to 
% carry around both an u=n-k+j and a v=j

% ALGORITHM
% replace k by the smallest of k and n-k
% if k=0 return 1
% else set w=n-k+1
%          u=n-k+2
%          v=2
% endif
% if v>k return w
% else
%        w<-w*u/v
%        u<-u+1
%        v<-v+1
% repeatif

% Constraint: expandability. Adding +1 has a cost and fetching a list of
% tokens also has one. To use one macro less, or not do twice u->u+1, 
% u and v are shifted from the start by  1 to be usable directly in the 
% updating of w.

% no check on validity of inputs

%-----------------------------------------------------------
% expandable macro \binomialb. No package needed. 

\catcode`_ 11

\def\binomialb #1#2{\romannumeral0\expandafter
    \binomialb_a\the\numexpr #1\expandafter.\the\numexpr #2.}

\def\binomialb_a #1.#2.{\expandafter\binomialb_b\the\numexpr #1-#2.#2.}

\def\binomialb_b #1.#2.{\ifnum #1<#2 \expandafter\binomialb_ca
                            \else   \expandafter\binomialb_cb
                            \fi {#1}{#2}}

\def\binomialb_ca #1{\ifnum#1=0 \expandafter \binomialb_one\else 
                    \expandafter \binomialb_d\fi {#1}}

\def\binomialb_cb #1#2{\ifnum #2=0 \expandafter\binomialb_one\else
                      \expandafter\binomialb_d\fi {#2}{#1}}

\def\binomialb_one #1#2{ 1}

\def\binomialb_d #1#2{\expandafter\binomialb_e \the\numexpr #2+1.#1!}

% n-k+1.k! -> u=n-k+2.v=2.w=n-k+1.k!
\def\binomialb_e #1.{\expandafter\binomialb_f \the\numexpr #1+1.2.#1.}

% u.v.w.k!
\def\binomialb_f #1.#2.#3.#4!%
{\ifnum #2>#4 \binomialb_end\fi
 \expandafter\binomialb_f
 \the\numexpr #1+1\expandafter.%
 \the\numexpr #2+1\expandafter.%
 \the\numexpr #1*#3/#2.#4!}

\def\binomialb_end #1*#2/#3!{\fi\space #2}
\catcode`_ 8

note1: some slight TeX optimization would replace the +1 by +\@ne, the >0<space> by >\z@, etc...

note2: the use of _ as private letter may disconcert, but it is fashionable and much more readable than the @ ;-)

1
  • the 2^31-1 bound makes investing into sophisticated factorial algorithm a bit irrelevant as already 13!>2^21. But for the record: it makes good sense to approach the problem via a binary splitting N!=F(1,A) times F(A+1,N) where Ais about N/2 and F(u,v) is u(u+1)...v. For this to be really efficient one then needs sub-quadratic (Karatsuba) multiplication. But even without as in my package xint this approach allows very short recursive definition which is almost as efficient as the much longer (dozens of lines) optimized code (say N<= 2000 for N!.)
    – user4686
    Sep 15, 2016 at 16:52

You must log in to answer this question.

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