samcarter
> This is part of the Summer of Code 2022 series, see https://topanswers.xyz/tex?q=2059 for more information

Today's challenge is to print as many Fibonacci numbers as you like

(when I first suggested the SoC in chat, there were some cool solutions for this in chat - I hope to see them here as answers :) )

---

Short recap in case someone is not familiar with Fibonacci numbers:

Fibonacci numbers are a sequence in which each new term is generated by summing up the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

![SoC.png](/image?hash=58e00a964b985c5e270bc971b69654e0b19002aff162f3aff062b085c17c7743)
Phelype Oleinik
ooh spoilers

Sorry, I haven't been paying attention.  What is SoC again? Square of Code?  Like this?


^^5clet~^^5ccatcode~ 0~,1
~.2~:6~)13 def):1,~:113
gdef.~'10) --, count2.)*%
*, interactionmode.)'('(:1%
;:2, unless ifnum:1'='0':1'
expandafter( the numexpr:1
+:2;,:1. fi.-**0'(1;1*- bye


---

Serious version:

The above abuses TeX to produce the sequence with the smallest possible effort from my part.  The important part of the code boils down to:

\def\fib#1;#2{\unless\ifnum#1=0 #1
\expandafter\x\the\numexpr#1+#2;{#1}\fi}
\fib1;1

\fib prints #1 then does a recursive call of \fib #1+#2;{#1}, thus printing the next number in the sequence, rinse and repeat.  The stop condition abuses the fact that \numexpr returns zero on an ! Arithmetic overflow, so it doesn't have to worry about maths: just crunch numbers until something explodes, then stop.  The Square of Code version contains some fancy manipulation of \interactionmode to make TeX hide the Arithmetic overflow error and finish the run successfully¹.

¹ Terms and conditions may apply.
frougon
I consider the [Fibonacci sequence](https://en.wikipedia.org/wiki/Fibonacci_number) to start with terms 0 and 1 (the subsequent terms are therefore 1 and 2, so this doesn't change much as compared to a definition in which the first terms are 1 and 2—this only shifts the indices).

Following are four expandable ways to obtain the first 46 terms of the sequence (only 45 in the first implementation because it computes F_{n+2} *before* doing the termination test and, in case the test is negative, delivering F_{n+1}). The examples below use standard TeX arithmetic via \count registers; this is what limits the greatest term we can compute. The four implementations provided in this answer use tail recursion and are presented in increasing order of optimization.

# First implementation

In this implementation, we pass from step to step the remaining number of terms to deliver as an integer denotation (this is the first argument of \fibo_next:nnn).


\documentclass{article}
%\usepackage{l3benchmark}

\ExplSyntaxOn

% #1: number of values left to print
% #2: F_{n+1}
% #3: F_{n}.
\cs_new:Npn \fibo_next:nnn #1#2#3
{
\int_compare:nNnF {#1} = { 0 }
{
,~ #3
\fibo_next:ffn { \int_eval:n { #1-1 } } { \int_eval:n { #2 + #3 } } {#2}
}
}

\cs_generate_variant:Nn \fibo_next:nnn { ffn }

\cs_new:Npn \fibo_numbers:n #1
{
0 \fibo_next:ffn { \int_eval:n { #1-1 } } { 1 } { 1 }
}

% Number of values to print (at least 1)
\NewExpandableDocumentCommand \fibo { m }
{
\fibo_numbers:n {#1}
}

%\benchmark:n { \tl_set:Nx \l_tmpa_tl { \fibo_numbers:n { 45 } } }

\ExplSyntaxOff

\begin{document}

\fibo{45}

\end{document}


![image.png](/image?hash=2062bcdd701230cb7505a89743c2483a1795f3760a76d985fd6d282cdeb2dd1e)

# Second implementation

Instead of using integer arithmetic to update the remaining number of terms to deliver and to compare it to zero, the following code leaves the desired number of m character tokens ahead in the input stream and gobbles one at each step (one could use virtually anything instead of m). The recursion stops when \quark_if_recursion_tail_stop:N finds the \q_recursion_tail quark after the last m has been consumed; then it gobbles everything up to and including \q_recursion_stop, which immediately follows \q_recursion_tail in our code.


\documentclass{article}
%\usepackage{l3benchmark}

\ExplSyntaxOn

% Generate the first n Fibonacci numbers, separated by commas. n must be at
% least 2. This function is restricted-expandable (works inside \edef but not
% within f-expansion).
\cs_new:Npn \fibo_numbers:n #1
{
0
% Initiate the recursion and add the trailing markers. Each step will eat
% one 'm' until \__fibo_next:nnN reaches the \q_recursion_tail marker.
\__fibo_numbers:f { \prg_replicate:nn { #1-2 } { m } }
}

\cs_new:Npn \__fibo_numbers:n #1
{
\__fibo_next:nnN { 1 } { 1 }
#1                   % a number of 'm' character tokens (possibly none)
\q_recursion_tail \q_recursion_stop
}

\cs_generate_variant:Nn \__fibo_numbers:n { f }

% #1: F_{n+1}
% #2: F_{n}
% #3: sentinel token (either 'm' or \q_recursion_tail)
\cs_new:Npn \__fibo_next:nnN #1#2#3
{
,~ #2
\quark_if_recursion_tail_stop:N #3
\__fibo_next:fnN { \int_eval:n { #1 + #2 } } {#1}
}

\cs_generate_variant:Nn \__fibo_next:nnN { f }

% Number of values to print (must be at least 2)
\NewExpandableDocumentCommand \fibo { m }
{
\fibo_numbers:n {#1}
}

%\benchmark:n { \tl_set:Nx \l_tmpa_tl { \fibo_numbers:n { 46 } } }

\ExplSyntaxOff

\begin{document}

\fibo{46}

\end{document}


![image.png](/image?hash=663994d61d5f7f1179b356f78ccbaa655f1778dedf5949a8d4a97c8f2cb55cce)

# Third implementation

This is almost the same as an [optimization of the previous code by Skillmon](https://topanswers.xyz/transcript?room=347&id=141537&year=2022&month=7#c141537). The main idea is to avoid all the termination tests performed on the third argument of \__fibo_next:nnN in the previous implementation. Instead, we generate a suitable number of \__fibo_numbers_auxii:w tokens before the recursion starts. Each of these will trigger the computation and delivery of a new term of the sequence. After the last \__fibo_numbers_auxii:w has been consumed, \use_none_delimit_by_q_stop:w is grabbed as the third argument of \__fibo_numbers:wnN; when expanded, it removes everything left thereafter in the input stream by the last expansion of \__fibo_numbers:wnN, up to and including the \q_stop token left by \fibo_numbers:n.


\documentclass{article}
%\usepackage{l3benchmark}

\ExplSyntaxOn

% Generate the first n Fibonacci numbers, separated by commas. n must be at
% least 2. This function is restricted-expandable (works inside \edef but not
% within f-expansion).
\cs_new:Npn \fibo_numbers:n #1
{
0
\exp_after:wN \__fibo_numbers:w
\prg_replicate:nn { #1 - 2 } { \__fibo_numbers_auxii:w }
\use_none_delimit_by_q_stop:w \q_stop
}

\cs_new:Npn \__fibo_numbers:w { \exp_after:wN \__fibo_numbers_aux:w }

\cs_new:Npn \__fibo_numbers_aux:w { \__fibo_numbers:wnN 1; 1 }

% #1: F_{n+1}
% #2: F_{n}
% #3: either \__fibo_numbers_auxii:w or \use_none_delimit_by_q_stop:w
\cs_new:Npn \__fibo_numbers:wnN #1; #2#3
{
,~ #2
#3 #1 + #2 \scan_stop: ; {#1}
}

\cs_new:Npn \__fibo_numbers_auxii:w
{
\exp_after:wN \exp_after:wN \exp_after:wN
\__fibo_numbers:wnN \int_eval:w
}

% Number of values to print (must be at least 2)
\NewExpandableDocumentCommand \fibo { m }
{
\fibo_numbers:n {#1}
}

%\benchmark:n { \tl_set:Nx \l_tmpa_tl { \fibo_numbers:n { 46 } } }

\ExplSyntaxOff

\begin{document}

\fibo{46}

\end{document}


Same output as the previous code.

# Fourth implementation

This is basically what Skillmon proposed [here](https://topanswers.xyz/transcript?room=347&id=141538#c141538)—I only performed some minor renaming and reformatting. This implementation is the same as the previous one, except that it spares a few expansion steps by directly using \the\numexpr[^note-on-the-numexpr] instead of \int_eval:w (the latter expands to \tex_the:D \__int_eval:w in one step, which is equivalent via aliases to \the\numexpr).


\documentclass{article}
%\usepackage{l3benchmark}

\ExplSyntaxOn

% Generate the first n Fibonacci numbers, separated by commas. n must be at
% least 2. This function is restricted-expandable (works inside \edef but not
% within f-expansion).
\cs_new:Npn \fibo_numbers:n #1
{
0
\exp_after:wN \__fibo_numbers:w
\prg_replicate:nn { #1 - 2 } { \__fibo_numbers_auxii:wnN }
\use_none_delimit_by_q_stop:w \q_stop
}

\cs_new:Npn \__fibo_numbers:w { \exp_after:wN \__fibo_numbers_aux:w }

\cs_new:Npn \__fibo_numbers_aux:w { \__fibo_numbers:wnN 1; 1 }

\cs_new_eq:NN \__fibo_numexpr:w \tex_numexpr:D

% #1: F_{n+1}
% #2: F_{n}
% #3: either \__fibo_numbers_auxii:w or \use_none_delimit_by_q_stop:w
\cs_new:Npn \__fibo_numbers:wnN #1; #2#3
{
,~ #2
#3 \int_use:N \__fibo_numexpr:w #1 + #2 \scan_stop: ; {#1}
}

\cs_new:Npn \__fibo_numbers_auxii:wnN
{
\exp_after:wN \__fibo_numbers:wnN
}

% Number of values to print (must be at least 2)
\NewExpandableDocumentCommand \fibo { m }
{
\fibo_numbers:n {#1}
}

%\benchmark:n { \tl_set:Nx \l_tmpa_tl { \fibo_numbers:n { 46 } } }

\ExplSyntaxOff

\begin{document}

\fibo{46}

\end{document}


Same output as above.

[^note-on-the-numexpr]: Actually, \int_use:N \__fibo_numexpr:w where \int_use:N is an alias for \the and \__fibo_numexpr:w for \tex_numexpr:D, i.e. \numexpr.
samcarter
*no spoiler to be seen*

I'm sure we will see some of the ultra efficient algos here soon, so here the simple way ~~(using the \int_set_eq:NN I learnt about this morning :) )~~:


\documentclass{article}

\begin{document}

Today’s challenge is to print as many Fibonacci numbers as you like

Short recap in case someone is not familiar with Fibonacci numbers:

Fibonacci numbers are a sequence in which each new term is generated by summing up the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

\ExplSyntaxOn

\int_new:N \l_sam_old_int
\int_new:N \l_sam_new_int

\int_set:Nn \l_sam_old_int { 1 }
\int_set:Nn \l_sam_new_int { 2 }

\int_step_inline:nn {43}
{

\par \int_use:N \l_sam_old_int

\int_set:Nn \l_sam_new_int { \l_sam_new_int + \l_sam_old_int }
\int_set:Nn \l_sam_old_int { \l_sam_new_int - \l_sam_old_int }

}

\ExplSyntaxOff

\end{document}


Skillmon
No idea for a spoiler-less introduction.

This is an implementation that calculates the *n*-th Fibonacci number directly (but doesn't produce a sequence of them). It uses fast matrix exponentiation for the calculation. This is based on Python code I found [here](https://stackoverflow.com/a/23462371/6783373).

More than the first 45 Fibonacci numbers can't be produced by TeX integers. You can change \__fib_eval:n to use \fp_eval:n instead, but then you'll get problems with floating point precision for bigger Fibonacci numbers as well.


\documentclass{article}

\ExplSyntaxOn
\cs_new_eq:NN \__fib_eval:n \int_eval:n
\cs_new:Npn \__fib_to_bin:n
{ \exp_after:wN \use_none:n \exp:w \exp_end_continue_f:w \int_to_bin:n }
\NewExpandableDocumentCommand \fib { m }
{
\exp_last_unbraced:Ne \__fib:nnnN { 1 1 0 \__fib_to_bin:n {#1} }
\q_recursion_stop
}
\cs_new:Npn \__fib:nnnN #1#2#3#4
{
\use_none_delimit_by_q_recursion_stop:w #4 \__fib_done:w \q_recursion_stop
\exp_args:Nf \__fib:nnnnN { \__fib_eval:n { #2 * #2 } } {#1} {#2} {#3} #4
}
\cs_new:Npn \__fib:nnnnN #1#2#3#4
{
\exp_last_unbraced:Ne \__fib_aux:nnnnN
{
{ \__fib_eval:n { #2 * #2 + #1 } }
{ \__fib_eval:n { (#2 + #4) * #3 } }
}
{#1} {#4}
}
\cs_new:Npn \__fib_aux:nnnnN #1#2#3#4#5
{
\token_if_eq_charcode:NNTF #5 1
{
\exp_last_unbraced:Ne \__fib:nnnN
{
{ \__fib_eval:n {#1 + #2} }
}
{#1}
{#2}
}
{
\exp_last_unbraced:Ne \__fib:nnnN
{
{#1}
{#2}
{ \__fib_eval:n { #4 * #4 + #3 } }
}
}
}
\cs_new:Npn \__fib_done:w #1 \__fib:nnnnN #2#3#4#5 \q_recursion_stop {#4}
\ExplSyntaxOff

\begin{document}
\ExplSyntaxOn
\int_step_inline:nn { 45 } { \fib{#1}~ }
\ExplSyntaxOff
\end{document}


![soc5-fibonacci-1.png](/image?hash=6123a304e3c217890cba555e3a6690ad81a43d3ae02c7ed2e931f63b4ccad8d0)
CrazyHorse
With lualatex:


\documentclass{article}
\usepackage{luacode}
\begin{luacode}
function fibo(max)
tex.print("Fibonacci Numbers \\par")
local a = 0
local b = 1
tex.print("0, 1, ")
for n = 1, max do
sum = a + b
a = b
b = sum
tex.print(tostring(sum)..", ")
end
end
\end{luacode}
\def\fibonacci#1{\directlua{fibo(#1)}}

\begin{document}
\fibonacci{46}
\end{document}
`

Enter question or answer id or url (and optionally further answer ids/urls from the same question) from

Separate each id/url with a space. No need to list your own answers; they will be imported automatically.