Cfrgtkky

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}



newcountn newcountnp newcountnpp newcountm newcountf

deffibonacci#1{{ifnum #1<3 1else

np=1npp=1m=3

loopifnumm<#1f=nppnpp=npadvancenp byfadvancem by 1repeat

f=0advancef bynpadvancef bynpp

numberffi}}

defprintfibonacci#1{m=#1advancem by 1

n=1

loopifnumn<mfibonacci{n}, advancen by 1repeat...}

printfibonacci{16}



end{document}

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 }

  { $fsb{#1}=#3$ }

  {

   $fsb{#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)

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

a_n+2 = pa_n+1 + qa_n

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

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

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}   



defluafibo#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 hfillnombre{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}   



defluafibo#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 hfillnombre{luafibo{n}} \}%   

end{multicols}   



end{document} 

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.

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: 

% 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

newcountfibocount



newcommandFastFibo[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 #1relax

      defa{1}defb{1}defd{0}%

      defg{1}deff{0}defh{1}%

      letnextFastFibo@ % plus efficace ici

      ifcasefibocount

          gdefResult{0}orgdefResult{1}elseexpandafternext

      fi

  endgroup

}

newcommandFastFibo@{%

   ifnumfibocount=@ne % we are done after one last computation:

         letnextrelax

         xdefResult{thebnumexpr b*g+d*frelax}%

   else

      ifoddfibocount

       edefh{bnumexpr b*f+d*hrelax}% use the smaller ones

       edeff{bnumexpr b*g+d*frelax}%

       edefg{bnumexpr f+hrelax}%

       advancefibocountm@ne

      fi

      dividefibocounttw@

% better to use the small ones for the multiplication

      letolddd

      edefd{bnumexpr b*b+d*drelax}%

      edefb{bnumexpr (a+oldd)*brelax}%

      edefa{bnumexpr b+drelax}%

   fi

   next

}

newcommandprintBigOne@[1]

   {ifx #1relax else #1hskip 0pt plus 1ptrelaxexpandafterprintBigOne@fi}%

newcommandprintBigOne [1]{expandafterprintBigOne@ #1relax }%



makeatother



begin{document}



checking that we can trust the macro:



count255 0

loop

FastFibo{count255}Result

ifnumcount255<20

,

advancecount255 1

repeat.



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



Fibonacci(1000)=FastFibo{1000}printBigOneResult



% still fast for N=2000, but for N=10000 does take some seconds:

Fibonacci(10000)=FastFibo {10000}printBigOneResult

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

newcountfibocount



newcommandFastFibo [1]{% #1=N, computes F(N) the way above

  begingroup 

      fibocount #1relax

      defa{1}defb{1}defd{0}%

      defg{1}deff{0}defh{1}%

      letnextFastFibo@ % plus efficace ici

      ifcasefibocount

          gdefResult{0}orgdefResult{1}elseexpandafternext

      fi

  endgroup

}

newcommandFastFibo@ {%

   ifnumfibocount=@ne % we are done after one last computation:

         letnextrelax

         xdefResult{xintiiAdd{xintiiMulbg}{xintiiMuldf}}%

   else

      ifoddfibocount

       edefh{xintiiAdd{xintiiMulbf}{xintiiMuldh}}%

       edeff{xintiiAdd{xintiiMulbg}{xintiiMuldf}}%

       edefg{xintiiAddfh}%

       advancefibocountm@ne

      fi

      dividefibocounttw@

      letolddd

      edefd{xintiiAdd{xintiiSqrb}{xintiiSqrd}}%

      edefb{xintiiMul{xintiiAddaoldd}b}%

      edefa{xintiiAddbd}%

   fi

   next

}

newcommandprintBigOne@[1]

   {ifx #1relax else #1hskip 0pt plus 1ptrelaxexpandafterprintBigOne@fi}%

newcommandprintBigOne [1]{expandafterprintBigOne@ #1relax }%



makeatother



begin{document}



checking that we can trust the macro:



count255 0

loop

FastFibo{count255}Result

ifnumcount255<20

,

advancecount255 1

repeat.



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



Fibonacci(1000)=FastFibo{1000}printBigOneResult



% still fast for N=2000, but for N=10000 does take some seconds:

Fibonacci(10000)=FastFibo {10000}printBigOneResult

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}

DeclareUrlCommandUrlNum{%

  urlstyle{rm}%

  defUrlBreaks{dodo1do2do3do4do5do6do7do8do9}%

}

renewcommand*{arraystretch}{1.2}



usepackage{fibnum}



begin{document}

begin{tabular}{l@{quad$rightarrow$quad}>{raggedrightarraybackslash}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}| & expandafterexpandafterexpandafter

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

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.

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=nppnpp=npadvancenp byf is without the space between first and second npp? If we need to do this more mysterious then we can write fnppnppnpadvancenpf but normal programmer write spaces (or newlines) between commands:

f=npp  npp=np  advancenp byf

Why there is the fragment f=0advancef bynp? 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:

newcounttmpnum  newcountA newcountB newcountC

deffib#1{A=1 B=1 tmpnum=2

  loop ifnumtmpnum<#1 C=A  advanceA byB  B=C  advancetmpnum by1 repeat

  ifnum#1=0 0else theAfi

}



$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:

deffibseq#1{A=1 B=1 printfib{0}{0}printfib{1}{1}tmpnum=2

  loop ifnumtmpnum<#1 C=A advanceA byB B=C

        printfib{thetmpnum}{theA}% 

        advancetmpnum by1 repeat

  printfib{thetmpnum}{theA}%

}

defprintfib#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

newcounttmpnum



deffib#1{defOUT{1}defB{1}tmpnum=2

  loop ifnumtmpnum<#1 advancetmpnum by1

        letC=OUT PLUSCB letB=C repeat

  ifnum#1=0 defOUT{0}fi

}

deflongprint#1{expandafterlongprintA#1end}

deflongprintA#1{ifxend#1else #1hskip 0pt plus 1ptrelax expandafterlongprintAfi}



Fibonacci(1000)=fib{1000}longprintOUT

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

newcounttmpnum



defffibo#1{%

   begingroup

      tmpnum=#1relax

      defa{1}defb{1}defd{0}defg{1}deff{0}defh{1}%

      ifcasetmpnum

          gdefOUT{0}or gdefOUT{1}elseexpandafterffiboX

      fi

  endgroup

}

defffiboX {%

   ifnumtmpnum=1 % we are done after one last computation:

         evaldefOUT{b*g+d*f}globalletOUT=OUT

   else

      ifoddtmpnum

         evaldefh{b*f+d*h}% use the smaller ones

         evaldeff{b*g+d*f}%

         evaldefg{f+h}%

      fi

      dividetmpnum by2

      letoldd=d

      evaldefd{b^2+d^2}%

      evaldefb{(a+oldd)*b}%

      evaldefa{b+d}%

      expandafterffiboX

   fi

}

deflongprint#1{expandafterlongprintA#1end}

deflongprintA#1{ifxend#1else #1hskip 0pt plus 1ptrelax expandafterlongprintAfi}



Fibonacci(100)=ffibo{100}longprintOUT



Fibonacci(1000)=ffibo{1000}longprintOUT



Fibonacci(10000)=ffibo {10000}longprintOUT



bye

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