# Fibonacci numbers

Hi I am trying to do Fibonacci below is the code but I am getting some error

\newcount\n \newcount\np \newcount\npp \newcount\m \newcount\f
\def\fibonacci#1{{\ifnum #1<3 1\else
\np=1\npp=1\m=3
\number\f\fi}}
\n=1
\printfibonacci{16}
\bye


error:

! LaTeX Error: Missing \begin{document}.

See the LaTeX manual or LaTeX Companion for explanation.
Type  H <return>  for immediate help.
...

l.11 \printfibonacci{16}

?

• compile it with tex or pdftex command. – Leo Liu Apr 10 '12 at 16:26
• You are using plain TeX code in LaTeX: is this intentional? The code itself will work, but you will need to use \printfibonacci after \begin{document} for LaTeX. Alternatively, use plain TeX. – Joseph Wright Apr 10 '12 at 16:27
• i am using miktex2.8 – Andy Apr 10 '12 at 16:30
• It has nothing to do with MiKTeX, which is one of several TeX distributions, what means, that they all provide amongst others the executables tex.exe and pdftex.exe (@all: Andy has obviously a computer with Windows on it), but you seem to have used latex.exe or pdflatex.exe. Did you use the included editor TeXworks? – Speravir Apr 10 '12 at 17:06
• @Andy: Could you try to find a more descriptive title for this question? It should say what you are trying to do with/about fibonacci numbers? – doncherry Apr 12 '12 at 8:37

You are using latex to process a plain TeX document and this, of course, triggers the error message. You have two options:

1. Process the document as it is using (pdf)tex.
2. Convert your document to a latex document.

Here's an illustration of the second option:

\documentclass{article}

\begin{document}

\newcount\n \newcount\np \newcount\npp \newcount\m \newcount\f
\def\fibonacci#1{{\ifnum #1<3 1\else
\np=1\npp=1\m=3
\number\f\fi}}
\n=1
\printfibonacci{16}

\end{document}

• +1 In my humble opinion, no matter how nice of efficient the other answers are, this is the only answer of all of them so far which really solves the problem of the original poster. – yo' Apr 12 '12 at 9:22
• @tohecz You are right, only this answer solves the question. Other answers gives only other ways to get Fibonacci numbers – Alain Matthes Apr 12 '12 at 11:57

An implementation in LaTeX3:

\documentclass{article}
\usepackage{xparse}
\ExplSyntaxOn
\cs_new:Npn \fibo #1 { \fibo_recurrence:nnnn{0}{1}{0}{#1} }
\cs_new:Npn \fibo_recurrence:nnnn #1 #2 #3 #4
{
\int_compare:nTF { #1 = #4 }
{ #3 }
{
#3 ~ \fibo_recurrence:ffnn
{ \int_eval:n {#1+1} }
{ \int_eval:n {#2+#3} }
{ #2 }
{ #4 }
}
}
\cs_generate_variant:Nn \fibo_recurrence:nnnn { ffnn }
\ExplSyntaxOff
\begin{document}
\fibo{0}

\fibo{1}

\fibo{2}

\fibo{3}

\fibo{7}

\fibo{45}

\end{document}


Notice that this is completely expandable. This prints

0
0 1
0 1 1
0 1 1 2
0 1 1 2 3 5 8 13
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170

but with \printfibonacci{46} we get Arithmetic overflow.

One can overcome the limitation with the bigintcalc package:

\documentclass{article}
\usepackage{xparse,bigintcalc}
\ExplSyntaxOn
\cs_new:Npn \fibo #1 { \fibo_recurrence:nnnn{0}{1}{0}{#1} }
\cs_new:Npn \fibo_recurrence:nnnn #1 #2 #3 #4
{
\int_compare:nTF { #1 = #4 }
{ $f\sb{#1}=#3$ }
{
$f\sb{#1}=#3$, ~ \fibo_recurrence:ffnn
{ \int_eval:n {#1+1} }
{ #2 }
{ #4 }
}
}
\cs_generate_variant:Nn \fibo_recurrence:nnnn { ffnn }
\ExplSyntaxOff
\begin{document}
\raggedright

\fibo{100}

\end{document}


will produce (and shows also how to print other information)

With a little twist the macro can build every degree 2 recurrent sequence (with integer coefficients), that is, of the form

an+2 = pan+1 + qan

\usepackage{xparse}
\ExplSyntaxOn
\cs_new:Npn \fibo #1 { \rec_recurrence:nnnnnn  {0}{1}{0}{#1}{1}{1} }
\cs_new:Npn \periodic #1 { \rec_recurrence:nnnnnn {0}{0}{1}{#1}{0}{-1} }
\cs_new:Npn \rec_recurrence:nnnnnn #1 #2 #3 #4 #5 #6
{
\int_compare:nTF { #1 = #4 }
{ $#3$ }
{
$#3$ ~ \rec_recurrence:ffnnnn
{ \int_eval:n {#1+1} }
{ \int_eval:n {#5*#2+#6*#3} }
{ #2 }
{ #4 }
{ #5 }
{ #6 }
}
}
\cs_generate_variant:Nn \rec_recurrence:nnnnnn { ff }

\cs_new:Npn \fibo #1 { \rec_recurrence:nnnnnn  {0}{1}{0}{#1}{1}{1} }
\cs_new:Npn \periodic #1 { \rec_recurrence:nnnnnn {0}{0}{1}{#1}{0}{-1} }

\ExplSyntaxOff


The arguments to \rec_recurrence:nnnnnn are

1. the starting point
2. the second term
3. the first term
4. the last term to compute
5. the p coefficient
6. the q coefficient

With \periodic{10} we get

1 0 −1 0 1 0 −1 0 1 0 −1

which is the recurrence

an+2 = 0an+1 + (-1)an

• Ooh, rivers !!! – percusse Apr 12 '12 at 9:05
• @percusse Werner called it a "Fibonacci fountain" :) – egreg Apr 12 '12 at 9:09

Here a try with lualatex. I try with a recursive method because it's concise and elegant but I'm not sure of the efficiency.

First try with lua Recursive method

Recursive :

function fib(n)
if (n < 1) then return(0) end
if (n < 3) then return(1) end
return( fib(n-2) + fib(n-1) )
end


Compilation time with recursive method : Relatively good for n <=36 but after 40 it's very long.

I use numprint with frenchb and babel to format the result.

%!TEX TS-program =  lualatex
\documentclass{scrartcl}
\usepackage{fontspec}
\usepackage{luatextra}
\usepackage{pgffor,numprint}
\usepackage[frenchb]{babel}
\usepackage{multicol}

\def\luafibo#1{
\directlua{
N=#1
function fib(n)
if (n < 1) then return(0) end
if (n < 3) then return(1) end
return( fib(n-2) + fib(n-1) )
end
tex.print(fib(N))
}}

\begin{document}
\parindent=0pt

\setlength{\columnseprule}{.5pt}
\setlength{\columnsep}{3cm}
\begin{multicols}{2}[Nombres de Fibonacci.]
\foreach \n in {0,...,36}
{\n \hfill\nombre{\luafibo{\n}} \\}%
\end{multicols}

\end{document}


Update Iterative method with lua

Another method but iterative and it's very efficient !!:

function fib(n)
if (n < 1) then return(0) end
if (n < 3) then return(1) end
a=0
b=1
for i =2, n do
f= a+b
a=b
b=f
end
return(b)
end

%!TEX TS-program =  lualatex
\documentclass{scrartcl}
\usepackage{fontspec}
\usepackage{luatextra}
\usepackage{pgffor,numprint}
\usepackage[frenchb]{babel}
\usepackage{multicol}

\def\luafibo#1{
\directlua{
N=#1
function fib(n)
if (n < 1) then return(0) end
if (n < 3) then return(1) end
a=0
b=1
for i =2, n do
f= a+b
a=b
b=f
end
return(b)
end
tex.print(fib(N))
}}

\begin{document}
\parindent=0pt
\small
\setlength{\columnseprule}{.5pt}
\setlength{\columnsep}{3cm}
\begin{multicols}{2}[Nombres de Fibonacci.]
\foreach \n in {0,...,90}
{\n \hfill\nombre{\luafibo{\n}} \\}%
\end{multicols}

\end{document}


• It would be interesting to use a module like bc or decnumber but I don't know how to install and load a module ! – Alain Matthes Apr 12 '12 at 7:37
• No wonder that the second method is more efficient; with the first one you compute again each value using the same function, so this grows exponentially. – egreg Apr 12 '12 at 8:53
• Yes you are right and I know that but I did not know how to get the code of Patrick. With Maple I just use the option remember to avoid to compute the same values. – Alain Matthes Apr 12 '12 at 9:02

A solution based on @Altermundus' great LuaTeX solution. Compile time less than 1 second. To calculate the fibonacci numbers, the unknown numbers are calculated with the index function of the metatable (__index). Once they are calculated, the numbers are stored in the table fib and don't need to be computed again. So for fib(50), only the sum of 4807526976 and 7778742049 must be calculated.

\documentclass{article}
\usepackage{luacode,multicol,numprint}
\begin{luacode*}
fib = {}

setmetatable(fib,
{ __index = function ( tbl,i )
local f
if i < 1 then
f = 0
elseif i==1 then
f = 1
else
f = tbl[i - 1] + tbl[i - 2]
end
tbl[i] = f
return f
end })
\end{luacode*}

\begin{document}
\setlength{\columnseprule}{.5pt}
\setlength{\columnsep}{3cm}
\begin{multicols}{2}[Fibonacci numbers]

\begin{luacode*}
for i=0,50 do
tex.sprint(0,i,"\\hfill","\\numprint{" .. fib[i] .. "}","\\par")
end
\end{luacode*}
\end{multicols}

\end{document}


The output is the same as in @Altermundus' first solution.

• great ! I'm a beginner with lua and It's very interesting to see how to improve a code. There is another method very efficient with big numbers with a matrix a=1 b=1 c=1 d=0 power (n) but I don't know how to use a matrix with lua :( Interesting link pages.cs.wisc.edu/~mhock/SSL/fibcalc.pdf – Alain Matthes Apr 12 '12 at 7:58
• @AlainMatthes in my answer I gave an implementation of the method going via nth power of the 2 by 2 matrix, as you mention. – user4686 Jan 1 '15 at 16:06

An expandable implementation of the "additive" algorithm is provided by package fibnum by Heiko Oberdiek (see his answer), which uses the bigintcalc macros.

There is a way to target one specific Fibonacci number without having to recurse through all values with a lesser index. This has been pointed out in this comment by Alain Matthes to an earlier answer on this page.

An expandable implementation of this "multiplicative" algorithm is to be found in the xint documentation xint.pdf since release 1.09j [2014/01/09].

Here, I implement the same "multiplicative" algorithm, but non-expandably for keeping simple. The underlying mathematics is the same, it is explained in the commented parts of the code below. The arithmetic operations themselves are carried out expandably, which when handling hundreds of digits, has some inherent cost.

The first code illustrates usage of the bnumexpr package; the second code uses directly the xintcore macros, bringing some (modest) speed gain as the expression parsing step is skipped.

Regarding additive vs multiplicative, when I first wrote this answer, I did some comparisons. Starting with N about 35 the \FastFibo "multiplicative" implementation was found to be faster than a similarly implemented but additive algorithm:

• N=100: multiplicative was found about 3.5 times faster than additive,
• N=500: more than 12 times faster
• N=1000: about 17 times faster.

However in the long run, for extremely big numbers, the FastFibo multiplicative algorithm would have to rely on Fast Multiplication to be certain to be faster than an additive implementation. Currently xintcore does not implement Karatsuba type multiplication but it will do in future, for operands of 500 digits or more (circa).

Code with expressions:

\documentclass{article}

\usepackage{bnumexpr}% expressions with big integers,
% scaled down from the full xintexpr expressions.

% as bnumexpr is only provided for LaTeX, if you want to do this in Plain,
% do \input xintexpr.sty and then use \xintiiexpr rather than \bnumexpr
% and \xinttheiiexpr rather than \thebnumexpr.

% F_{-1}=1, F_0 = 0, F_1=1, F_2=1, F_3=2

% A = [[1,1],[1,0]]
% A^n = [[F_{n+1},F_{n}], [F_{n},F_{n-1}]]

% Proof: true if n=0, A^0 = I
% if true for n, true for n+1 by simple computation

% Hence to compute efficiently F_n, **without computing the others for m<n**,
% it is a matter of raising A to the power n.

% algorithm:
%   if n even, replace n by n/2, leave M unchanged, A <- A^2
%   if n is odd, replace n by (n-1)/2, M <- AM,  A <- A^2
% repeat until n=1, then multiply the last M by the last A.
% Extract F_n.

% This can be done expandably, but for the sake of simplicity let's do it in a
% less far-fetched way.

\makeatletter
\newcount\fibocount

\newcommand\FastFibo[1]{% #1=N, computes F(N) the way above
\begingroup
% A = [[a,b],[b,d]], is initially [[1,1],[1,0]] and then to some power 2^k
% M = [[g,f],[f,h]], is initially Identity and then [[1,1],[1,0]] to some power
% both A and M always are symmetric, and a=b+d, g=f+h always.
% The reason for using \Result is in case the result is very long, we need to
% work on it afterwards to print it.
\fibocount #1\relax
\def\a{1}\def\b{1}\def\d{0}%
\def\g{1}\def\f{0}\def\h{1}%
\let\next\FastFibo@ % plus efficace ici
\ifcase\fibocount
\gdef\Result{0}\or\gdef\Result{1}\else\expandafter\next
\fi
\endgroup
}
\newcommand\FastFibo@{%
\ifnum\fibocount=\@ne % we are done after one last computation:
\let\next\relax
\xdef\Result{\thebnumexpr \b*\g+\d*\f\relax}%
\else
\ifodd\fibocount
\edef\h{\bnumexpr \b*\f+\d*\h\relax}% use the smaller ones
\edef\f{\bnumexpr \b*\g+\d*\f\relax}%
\edef\g{\bnumexpr \f+\h\relax}%
\fi
\divide\fibocount\tw@
% better to use the small ones for the multiplication
\let\oldd\d
\edef\d{\bnumexpr \b*\b+\d*\d\relax}%
\edef\b{\bnumexpr (\a+\oldd)*\b\relax}%
\edef\a{\bnumexpr \b+\d\relax}%
\fi
\next
}
\newcommand\printBigOne@[1]
{\ifx #1\relax \else #1\hskip 0pt plus 1pt\relax\expandafter\printBigOne@\fi}%
\newcommand\printBigOne [1]{\expandafter\printBigOne@ #1\relax }%

\makeatother

\begin{document}

checking that we can trust the macro:

\count255 0
\loop
\FastFibo{\count255}\Result
\ifnum\count255<20
,
\repeat.

Fibonacci(100)=\FastFibo{100}\Result % 354224848179261915075

Fibonacci(1000)=\FastFibo{1000}\printBigOne\Result

% still fast for N=2000, but for N=10000 does take some seconds:
Fibonacci(10000)=\FastFibo {10000}\printBigOne\Result
\end{document}


Code with macros (slightly faster):

\documentclass{article}

\usepackage{xintcore}

% This can be done expandably, but for the sake of simplicity let's do it in a
% less far-fetched way.

\makeatletter
\newcount\fibocount

\newcommand\FastFibo [1]{% #1=N, computes F(N) the way above
\begingroup
\fibocount #1\relax
\def\a{1}\def\b{1}\def\d{0}%
\def\g{1}\def\f{0}\def\h{1}%
\let\next\FastFibo@ % plus efficace ici
\ifcase\fibocount
\gdef\Result{0}\or\gdef\Result{1}\else\expandafter\next
\fi
\endgroup
}
\newcommand\FastFibo@ {%
\ifnum\fibocount=\@ne % we are done after one last computation:
\let\next\relax
\else
\ifodd\fibocount
\fi
\divide\fibocount\tw@
\let\oldd\d
\fi
\next
}
\newcommand\printBigOne@[1]
{\ifx #1\relax \else #1\hskip 0pt plus 1pt\relax\expandafter\printBigOne@\fi}%
\newcommand\printBigOne [1]{\expandafter\printBigOne@ #1\relax }%

\makeatother

\begin{document}

checking that we can trust the macro:

\count255 0
\loop
\FastFibo{\count255}\Result
\ifnum\count255<20
,
\repeat.

Fibonacci(100)=\FastFibo{100}\Result % 354224848179261915075

Fibonacci(1000)=\FastFibo{1000}\printBigOne\Result

% still fast for N=2000, but for N=10000 does take some seconds:
Fibonacci(10000)=\FastFibo {10000}\printBigOne\Result
\end{document}


An expandable method for calculating the number of Fibonacci numbers is provided by the package fibnum. Example for LaTeX:

\documentclass{article}
\usepackage{array, url}
\DeclareUrlCommand\UrlNum{%
\urlstyle{rm}%
\def\UrlBreaks{\do\0\do\1\do\2\do\3\do\4\do\5\do\6\do\7\do\8\do\9}%
}
\renewcommand*{\arraystretch}{1.2}

\usepackage{fibnum}

\begin{document}
\begin{tabular}{l@{\quad$\rightarrow$\quad}>{\raggedright\arraybackslash}p{75mm}}
\verb|\fibnum{0}| & \fibnum{0} \\
\verb|\fibnum{1}| & \fibnum{1} \\
\verb|\fibnum{2}| & \fibnum{2} \\
\verb|\fibnum{3}| & \fibnum{3} \\
\verb|\fibnum{4}| & \fibnum{4} \\
\verb|\fibnum{5}| & \fibnum{5} \\
\verb|\fibnum{6}| & \fibnum{6} \\
\verb|\fibnum{10}| & \fibnum{10} \\
\verb|\fibnum{46}| & \fibnum{46} \\
\verb|\fibnum{100}| & \fibnum{100} \\
\verb|\fibnum{200}| & \fibnum{200} \\
\verb|\fibnum{1000}| & \expandafter\expandafter\expandafter
\UrlNum\expandafter\expandafter\expandafter{\fibnum{1000}} \\
\end{tabular}
\end{document}


The package can also be used with plain TeX:

\input fibnum.sty

$$f_{10} = \fibnum{10}$$
$$f_{200} = \fibnum{200}$$

\bye


Because of the use of package bigintcalc, the Fibonacci number values are not restricted by TeX's size limitations for numbers. But very large numbers will of course take a lot of time for the calculation.

Having an expandable version has the advantage that \fibnum can be used for counter values, or used in bookmarks, label names, ...

• I cann't compile when I copy your code. – minthao_2011 Jan 1 '15 at 9:03
• @minthao_2011 Thanks, fixed. Two closing curly braces were missing because of a copy/paste problem. – Heiko Oberdiek Jan 1 '15 at 9:06

Here is an example from the TikZ/PGF 3.0.0 manual :

\documentclass[varwidth,border=5]{standalone}
\usepackage{tikz}
\usetikzlibrary{math}

\begin{document}
\tikzmath{
function fibonacci(\n) {
if \n == 0 then {
return 0;
} else {
return fibonacci2(\n, 0, 1);
};
};
function fibonacci2(\n, \p, \q) {
if \n == 1 then {
return \q;
} else {
return fibonacci2(\n-1, \q, \p+\q);
};
};
int \f, \i;
for \i in {0,1,...,20}{
\f = fibonacci(\i);
print {\f, };
};
}
\end{document}


0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,

You can replace 20 by 21, but for 22 we get the error:

! Dimension too large.

UPDATE We can use fp package with the tikz library fixedpointarithmetic to calculate with numbers smaller that 1e18. In this way we can compute up to 88.

\documentclass[varwidth,border=5]{standalone}
\usepackage{tikz}
\usepackage{fp}
\usetikzlibrary{fixedpointarithmetic}
\usetikzlibrary{math}

\begin{document}
\tikzset{fixed point arithmetic}
\tikzmath{
function printfib(\i,\f){print {$f_{\i} = \f$\newline};};
function fibonacci(\n) {
int \a, \b, \res;
\a = 0; \b = 1;
if \n == 0 then { \res = \a; };
if \n == 1 then { \res = \b; };
if \n > 1 then {
for \i in {2,...,\n}{
\res = \a + \b;
\a = \b;
\b = \res;
};
};
return \res;
};
int \f, \i;
for \i in {0,1,...,10}{
printfib(\i,fibonacci(\i));
};
printfib(87,fibonacci(87));
printfib(88,fibonacci(88));
printfib(89,fibonacci(89));
}
\end{document}


It compiles without error until 87. The result of fibonacci(88) is correct, but there is overflow error. And fibonacci(89) is wrong.

Just for the sake of fun, here is my own try, also based on Alain Matthes' answer. It uses LuaLaTeX too, but I chose to revert to some MetaPost code instead of Lua code via the luamplib package. I've also used another (quite fast) way to compute the Fibonacci numbers, a tail-recursive algorithm retrieved from the French page of Wikipedia about Fibonacci.

\documentclass[12pt, parskip]{scrartcl}
\typearea{16}
\usepackage{unicode-math, multicol, pgffor}
\usepackage{numprint}
\usepackage[frenchb]{babel}

\usepackage{luamplib}
\mplibsetformat{metafun}
\mplibnumbersystem{double}
\mplibtextextlabel{enable}
\everymplib{% Tail-recursive algorithm
vardef fib(expr n, fn_one, fn) =
if (n=0): fn
else: fib(n-1, fn, fn+fn_one)
fi
enddef;}
\newcommand{\mplibfib}[1]{%
\begin{mplibcode}
beginfig(0);
label("\nombre{" & decimal(fib(#1, 1, 0)) & "}", origin);
endfig;
\end{mplibcode}}

\begin{document}
\setlength{\columnseprule}{.5pt}
\setlength{\columnsep}{3cm}
\begin{multicols}{2}[Nombres de Fibonacci.]
\foreach \n in {0,...,90}
{\n \hfill \mplibfib{\n} \\}%
\end{multicols}
\thispagestyle{empty}
\end{document}


The output is naturally very similar:

The first impulse of the question was the mistake: the plain TeX code was misinterpreted as LaTeX code. But the problem how to calculate Fibonacci numbers by TeX is interesting. I have several remarks.

Remark 1 The plain TeX code mentioned in the question is strange. The code isn't formatted (indented lines, spaces between commands). Why (for example) the fragment \f=\npp\npp=\np\advance\np by\f is without the space between first and second \npp? If we need to do this more mysterious then we can write \f\npp\npp\np\advance\np\f but normal programmer write spaces (or newlines) between commands:

\f=\npp  \npp=\np  \advance\np by\f


Why there is the fragment \f=0\advance\f by\np? This is equivalent to \f=\np. Why the \f register is allocated? It is redundant.

So, normal plain TeX code for calculating Fibonacci numbers can look like:

\newcount\tmpnum  \newcount\A \newcount\B \newcount\C
\def\fib#1{\A=1 \B=1 \tmpnum=2
\ifnum#1=0 0\else \the\A\fi
}

$f(1)=\fib1, f(42)=\fib{42}$
\bye


Remark 2 Each calculation of one Fibonacci number needs to calculate all previous numbers (in this type of implementation). So, it is curious to print the begin of the Fibonacci's sequence (16 numbers in the example code in the question) by calculating all numbers again and again. It is more reasonable to modify the \fib macro to \fibseq macro, for example:

\def\fibseq#1{\A=1 \B=1 \printfib{0}{0}\printfib{1}{1}\tmpnum=2
\loop \ifnum\tmpnum<#1 \C=\A \advance\A by\B \B=\C
\printfib{\the\tmpnum}{\the\A}%
\printfib{\the\tmpnum}{\the\A}%
}
\def\printfib#1#2{$f(#1)=#2$, }

\fibseq {42}
\bye


Remark 3 Maximal number calculated by code above can be f(46) due to the limit of maximal number stored in integer register in TeX. To overcome this the xint package was used in the answers here. I use the apnum package because this package is mine. The implementation using apnum.tex can look like:

\input apnum
\newcount\tmpnum

\def\fib#1{\def\OUT{1}\def\B{1}\tmpnum=2
\let\C=\OUT \PLUS\C\B \let\B=\C \repeat
\ifnum#1=0 \def\OUT{0}\fi
}
\def\longprint#1{\expandafter\longprintA#1\end}
\def\longprintA#1{\ifx\end#1\else #1\hskip 0pt plus 1pt\relax \expandafter\longprintA\fi}

Fibonacci(1000)=\fib{1000}\longprint\OUT
\bye


Note that this implementation is bout 7times faster than the implementation using bigintcalc package when calculating f(1000) (compare the answer by @egreg here). Of course, the code above spends many time when calculating very big Fibonacci number because all previous Fibonacci numbers have to be calculated. So, the implementation using matrix M (mentioned in the answer by @jfbu) can be done. The same algorithm but using apnum.tex follows:

\input apnum
\newcount\tmpnum

\def\ffibo#1{%
\begingroup
\tmpnum=#1\relax
\def\a{1}\def\b{1}\def\d{0}\def\g{1}\def\f{0}\def\h{1}%
\ifcase\tmpnum
\gdef\OUT{0}\or \gdef\OUT{1}\else\expandafter\ffiboX
\fi
\endgroup
}
\def\ffiboX {%
\ifnum\tmpnum=1 % we are done after one last computation:
\evaldef\OUT{\b*\g+\d*\f}\global\let\OUT=\OUT
\else
\ifodd\tmpnum
\evaldef\h{\b*\f+\d*\h}% use the smaller ones
\evaldef\f{\b*\g+\d*\f}%
\evaldef\g{\f+\h}%
\fi
\divide\tmpnum by2
\let\oldd=\d
\evaldef\d{\b^2+\d^2}%
\evaldef\b{(\a+\oldd)*\b}%
\evaldef\a{\b+\d}%
\expandafter\ffiboX
\fi
}
\def\longprint#1{\expandafter\longprintA#1\end}
\def\longprintA#1{\ifx\end#1\else #1\hskip 0pt plus 1pt\relax \expandafter\longprintA\fi}

Fibonacci(100)=\ffibo{100}\longprint\OUT

Fibonacci(1000)=\ffibo{1000}\longprint\OUT

Fibonacci(10000)=\ffibo {10000}\longprint\OUT

\bye


The code above is about 5times faster than the same algorithm implemented by xint when calculating f(10000).