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 fasterN=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
\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}%
\advance\fibocount\m@ne
\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
,
\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}
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
\xdef\Result{\xintiiAdd{\xintiiMul\b\g}{\xintiiMul\d\f}}%
\else
\ifodd\fibocount
\edef\h{\xintiiAdd{\xintiiMul\b\f}{\xintiiMul\d\h}}%
\edef\f{\xintiiAdd{\xintiiMul\b\g}{\xintiiMul\d\f}}%
\edef\g{\xintiiAdd\f\h}%
\advance\fibocount\m@ne
\fi
\divide\fibocount\tw@
\let\oldd\d
\edef\d{\xintiiAdd{\xintiiSqr\b}{\xintiiSqr\d}}%
\edef\b{\xintiiMul{\xintiiAdd\a\oldd}\b}%
\edef\a{\xintiiAdd\b\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
,
\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}
texorpdftexcommand.\printfibonacciafter\begin{document}for LaTeX. Alternatively, use plain TeX.tex.exeandpdftex.exe(@all: Andy has obviously a computer with Windows on it), but you seem to have usedlatex.exeorpdflatex.exe. Did you use the included editorTeXworks?