Take the 2-minute tour ×
TeX - LaTeX Stack Exchange is a question and answer site for users of TeX, LaTeX, ConTeXt, and related typesetting systems. It's 100% free, no registration required.

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
\loop\ifnum\m<#1\f=\npp\npp=\np\advance\np by\f\advance\m by 1\repeat
\f=0\advance\f by\np\advance\f by\npp
\number\f\fi}}
\def\printfibonacci#1{\m=#1\advance\m by 1
\n=1
\loop\ifnum\n<\m\fibonacci{\n}, \advance\n by 1\repeat...}
\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}

? 
share|improve this question
2  
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
1  
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

9 Answers 9

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
\loop\ifnum\m<#1\f=\npp\npp=\np\advance\np by\f\advance\m by 1\repeat
\f=0\advance\f by\np\advance\f by\npp
\number\f\fi}}
\def\printfibonacci#1{\m=#1\advance\m by 1
\n=1
\loop\ifnum\n<\m\fibonacci{\n}, \advance\n by 1\repeat...}
\printfibonacci{16}

\end{document}
share|improve this answer
4  
+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
2  
@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} }
      { \bigintcalcAdd{#2}{#3} }
      { #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)

enter image description here

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

share|improve this answer
9  
Ooh, rivers !!! –  percusse Apr 12 '12 at 9:05
7  
@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} 

enter image description here

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} 

enter image description here

share|improve this answer
    
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
2  
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.

share|improve this answer
    
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. –  jfbu Jan 1 at 16:06

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]. Currently (release 1.1a of 2014/11/07) the code is in section 7.24 Some arithmetic with Fibonacci numbers.

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

Here, I implement this "multiplicative" algorithm non-expandably (using various \def's as well as a count register.), but ultimately relying on the expandable big integer arithmetic of package xintcore. The underlying mathematics is the same as the one used for the expandable code in xint.pdf. The mathematics is explained in the commented parts of the code below.

Use is made of the user-friendly expressions for big arithmetic operations as provided by the LaTeX package bnumexpr, a scaled-down version of the complete expression parser coming with package xintexpr (the latter also usable in Plain TeX.)

Update (jan 2, 2015): slight speed improvement for medium sized N's from using \bnumexpr and not \thebnumexpr in the intermediate computations. The former keeps tokens in an internal format. The latter needs only be used at the very end, for user printable output. Earlier code used \thebnumexpr everywhere, thus slowing up things.

Regarding additive vs multiplicative, when I first wrote this answer, I did some comparisons. Starting with N about 35 and larger the \FastFibo "multiplicative" implementation was found to be faster than a similarly implemented but additive algorithm (using F(N+2)=F(N+1)+F(N)). For N=100 about 3.5 times faster; for N=500 more than 12 times faster; for N=1000 about 17 times faster. Both implementations using the big arithmetic from xintcore.sty.

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. 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 compete with the multiplicative.

The underlying xint operations (all in xintcore.sty) 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.

I have tested the code below in the version modified by wipet in his answer which uses the apnum macros (which are non-expandable) in place of the \bnumexpr expandable expression parser.

Indeed for N=10000 I observed a six fold speed increase in favor of apnum.

For small N (up to a few hundreds), it is the \bnumexpr way which was found to be faster: for example close to twice faster for N=100.

With direct use of the xintcore macros, one obtains even more speed gains (computation time halved for N=100) but comparison with the code using apnum would not be fair, as it has the overhead of the \evaldef expression parsing.

Fibonacci numbers

The code below is for LaTeX. For use with Plain one needs to replace, among other things, \usepackage{bnumexpr} by \input xintexpr.sty, and \bnumexpr by \xintiiexpr.

\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: 
% start with M = Identity
%   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
% NOTE: \oodef, is like \def with two expansions of replacement text. Provided
% from loading xintcore itself 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
% INITIAL CODE HAD \thebnumexpr, BUT USING \bnumexpr IS LESS WASTEFUL:
      \ifodd\fibocount
       \oodef\h{\bnumexpr \b*\f+\d*\h\relax}% use the smaller ones
       \oodef\f{\bnumexpr \b*\g+\d*\f\relax}%
       \oodef\g{\bnumexpr \f+\h\relax }%
       \advance\fibocount\m@ne
      \fi
      \divide\fibocount\tw@
% better to use the small ones for the multiplication
      \let\oldd\d
      \oodef\d{\bnumexpr \b*\b+\d*\d\relax}%
      \oodef\b{\bnumexpr (\a+\oldd)*\b\relax}%
      \oodef\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
,
\advance\count255 1
\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}

Here is the code using directly macros, skipping the expressions. Twice faster compared to code above with \bnumexpr for N=100 but gain of only 10% for N=1000 (25% gain compared to the original code which was with \thebnumexpr and not \bnumexpr). For larger N's there is no gain, even there is a slight loss of speed for N=10000.

% \usepackage{xintcore} % in the preamble, or \input xintcore.sty in Plain
\newcommand\FastFibo@ {%
   \ifnum\fibocount=\@ne % we are done after one last computation:
         \let\next\relax
         \global\oodef\Result{\xintiiAdd{\xintiiMul\b\g}{\xintiiMul\d\f}}%
   \else
      \ifodd\fibocount
       \oodef\h{\xintiiAdd{\xintiiMul\b\f}{\xintiiMul\d\h}}%
       \oodef\f{\xintiiAdd{\xintiiMul\b\g}{\xintiiMul\d\f}}%
       \oodef\g{\xintiiAdd\f\h}%
       \advance\fibocount\m@ne
      \fi
      \divide\fibocount\tw@
      \let\oldd\d
      \oodef\d{\xintiiAdd{\xintiiSqr\b}{\xintiiSqr\d}}%
      \oodef\b{\xintiiMul{\xintiiAdd\a\oldd}\b}%
      \oodef\a{\xintiiAdd\b\d}%
   \fi
   \next
}
share|improve this answer

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}

Result

The package can also be used with plain TeX:

\input fibnum.sty

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

\bye

Result plain TeX

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, ...

share|improve this answer
    
I cann't compile when I copy your code. –  minthao_2011 Jan 1 at 9:03
    
@minthao_2011 Thanks, fixed. Two closing curly braces were missing because of a copy/paste problem. –  Heiko Oberdiek Jan 1 at 9:06
    
Thank you very much. –  minthao_2011 Jan 1 at 9:10

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

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

\begin{document}
\tikzmath{
  % Adapted from http://www.cs.northwestern.edu/academics/courses/110/html/fib_rec.html
  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.

enter image description here

share|improve this answer

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:

enter image description here

share|improve this answer

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
  \loop \ifnum\tmpnum<#1 \C=\A  \advance\A by\B  \B=\C  \advance\tmpnum by1 \repeat
  \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}% 
        \advance\tmpnum by1 \repeat
  \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
  \loop \ifnum\tmpnum<#1 \advance\tmpnum by1
        \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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.