> 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)

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.

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`.

*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} ```

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)

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