# 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
show 1 more comment

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