☰

尝试生成斐波那契数

tag-icon • tag-icon macros calculations
尝试生成斐波那契数

我正在尝试生成斐波那契数列。下面是代码，但我遇到了一些错误。

\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

错误：

! LaTeX Error: Missing \begin{document}.

See the LaTeX manual or LaTeX Companion for explanation.
Type  H <return>  for immediate help.
 ...                                              
                                                  
l.11 \printfibonacci{16}
                        
?

答案1

您正在使用 latex 处理纯 TeX 文档，这当然会触发错误消息。您有两个选择：

  1. 使用 (pdf)tex 处理文档。
  2. 将您的文档转换为乳胶文档。

以下是第二种选择的说明：

\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}

答案2

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}

请注意，这是完全可扩展的。这将打印

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

但\printfibonacci{46}我们得到了Arithmetic overflow。

可以使用以下bigintcalc软件包来克服这一限制：

\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}

将产生（并显示如何打印其他信息）

在此处输入图片描述

稍加改动，该宏就可以构建每个 2 度递归序列（具有整数系数），即形式

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

的论点\rec_recurrence:nnnnnn是

  1. 起点
  2. 第二任期
  3. 第一学期
  4. 要计算的最后一项
  5. p 系数
  6. q 系数

我们\periodic{10}得到

1 0 −1 0 1 0 −1 0 1 0 −1

这是复发

a n+2 = 0a n+1 + (-1)a n

答案3

这里尝试使用 lualatex。我尝试使用递归方法，因为它简洁而优雅，但我不确定其效率。

首先尝试使用lua递归方法

递归：

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

使用递归方法的编译时间：当 n <= 36 时相对较好，但 40 之后就很长了。

我使用 numprint 与 frenchb 和 babel 来格式化结果。

%!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}

在此处输入图片描述

使用 lua 更新迭代方法

另一种方法但是迭代并且非常有效!!：

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}

在此处输入图片描述

答案4

包提供了“加法”算法的可扩展实现纤维蛋白原Heiko Oberdiek（参见他的回答），它使用bigintcalc宏。

有一种方法可以定位一个特定的斐波那契数，而不必递归遍历所有具有较小索引的值。这一点已在这篇文章中指出评论通过Alain Matthes本页先前的回答。

这种“乘法”算法的可扩展实现可以在信特xint.pdf自发布以来的文档1.09j [2014/01/09]。

在这里，我实现了相同的“乘法”算法，但为了保持简单，它是不可扩展的。底层数学是相同的，在下面代码的注释部分中进行了解释。算术运算本身是可扩展的，当处理数百位数字时，会产生一些固有的成本。

第一个代码说明了数值表达式包；第二段代码直接使用新芯宏，由于跳过了表达式解析步骤，因此带来了一些（适度的）速度提升。

关于加法与乘法，当我第一次写这个答案时，我做了一些比较。首先N发现“35乘法\FastFibo”实现比类似实现的加法算法更快：

  • N=100：发现乘法3.5比加法快大约倍，
  • N=500：12快上几倍
  • N=1000：17快约 倍。

然而从长远来看，对于非常大的数字，FastFibo 乘法算法必须依靠快速乘法才能确保比加法实现更快。目前xintcore尚未实现 Karatsuba 类型的乘法，但将来会实现，适用于 500 位或更多位（大约）的操作数。

斐波那契数

带表达式的代码：

\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}

使用宏的代码（稍微快一点）：

\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}

相关内容