# 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: Perhaps you could consider marking some of your questions as answered. See How do you accept an answer? - you currently have a "0% accept rate". –  Werner Apr 16 '12 at 19:32

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. –  tohecz 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

Update shows the code which uses directly the macros of xint, by-passing the overhead of handling expressions via bnumexpr.

As some answers have concentrated on computing Fibonacci numbers, and that there are some links to this Question, I provide here one more method. It is especially designed to target one Fibonacci number without computing the previous ones, or at least not all of them. (actually this method is the one from a comment to an earlier answer on this page.)

Testing against a similar style of implementation based on the additive algorithm confirms that for N about 35 and higher \FastFibo is computed faster: for N=100 about 3.5 times faster, for N=500 more than 12 times faster, for N=1000 about 17 times faster.

However in the long run, for extremely big numbers, the Fibo multiplicative algorithm must rely on Fast Multiplication to be certain to be faster than the Fibo additive implementation.

However, one can not test the effect here as with N=10000 the computation time is already of the order of some seconds on my laptop, and one would need presumably quite bigger N to see the additive Fibo compete with the multiplicative one.

The underlying xint operations are expandable and when managing thousands of tokens as for N=10000 this has an important time penalty. It is possible to implement much faster, but non expandable, big arithmetic in TeX.

\documentclass{article}

\usepackage{bnumexpr}% for big integers computation, new on CTAN as of
% 2014/09/22

% 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, A by A^2, leave M unchanged
%   if n is odd, replace n by (n-1)/2, A by A^2 and M by AM (with initial A)
% recurse until n=1, thus 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
% NOTE: \oodef, is like \def with two expansions of replacement text. Provided
% by xint which is loaded by bnumexpr.

\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
\global\oodef\Result{\thebnumexpr \b*\g+\d*\f\relax }%
\else
\ifodd\fibocount
\oodef\h{\thebnumexpr \b*\f+\d*\h\relax}% use the smaller ones
\oodef\f{\thebnumexpr \b*\g+\d*\f\relax}%
\oodef\g{\thebnumexpr \f+\h\relax }%
\fi
\divide\fibocount\tw@
% better to use the small ones for the multiplication
\let\oldd\d
\oodef\d{\thebnumexpr \b*\b+\d*\d\relax}%
\oodef\b{\thebnumexpr (\a+\oldd)*\b\relax}%
\oodef\a{\thebnumexpr \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}


And the code not using expressions. It is indeed faster (and does not impact the hash table like \bnumexpr may do). No need for bnumexpr then, xint (and in the future that part going into xintcore) suffices.

% \usepackage{xint}
\newcommand\FastFibo@ {%
\ifnum\fibocount=\@ne % we are done after one last computation:
\let\next\relax
\else
\ifodd\fibocount