Factorial program in Latex without using any package

Question

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.

Answer 1

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.

Answer 2

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 @ ;-)