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)
Top Answer
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.
Answer #2
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`.
Answer #3
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}
```
Answer #4
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)
Answer #5
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}
```