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.

  • Welcome to TeX.SX, and congratulations for daring to explore TeX beyond well-trodden paths! – gernot Sep 14 '16 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 '16 at 21:35
  • Do you want your command to produce spurious spaces? If not, you need to comment them! – cfr Sep 14 '16 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 '16 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) – David Carlisle Sep 15 '16 at 0:17
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.

  • Thanks for the answer, but I am new to Latex and can't understand your code. Can you add comments and explain? – Meet Taraviya Sep 15 '16 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 – David Carlisle Sep 15 '16 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 @ ;-)

  • 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 '16 at 16:52

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.