# Tips for golfing a fibonacci sequence generator

One day in July 2020, I made the following C program:

#define A m]
a[9999],*m=a;main(){for(2[A=4[A=1;;){for(;4[A;putchar(6[m-=3]+48));
for(puts(a);7[A;2[A=4[A,4[A=1)if(4[A+=3[m+=3]-1,9<(3[A=2[A+=3[A))++
5[A,7[A=1,3[A-=10;}}


with three superfluous newlines removed, it's 167 bytes and it prints the fibonacci sequence (as decimal numbers, separated with newline) potentially infinitely (it will crash when exceeding the buffer size after printing many terms of the sequence). Try it online (gcc)! Try it online (clang)!.

As I had trouble golfing it myself, I decided to ask the C golfers of CGCC for help. The challenge is to golf it, or more formally, to produce the same output as this program (and of course you can derive your own solution based on it). The code should stay reasonably portable (i.e. not perform out-of-bounds accesses before program termination is desired, use compiler extensions, etc...).

Your program is expected to print at least 15939 consecutive fibonacci numbers, starting from the smallest, separated with newlines, printed as decimal numbers, starting with 0 1 1 2 3 5 ....

Your answer might also provide improvements to the original version as an extra (printing more sequence terms with minimally more bytes, etc... - just make sure to post the golfed version with your answer, because it's the main goal of this question).

• :O I like the [A trick May 31, 2021 at 16:45
• @Wzl i'm also a fan of the puts trick - puts appends a newline after the text it prints. assume int v[] = {0, blablabla}; - the 0 will always be the first element of an array: putchar('\n') => putchar(10); => puts(""); => puts(v); May 31, 2021 at 16:46
• Can you post an ungolfed (easier to read) version of the code, so we may more easily see your algorithmic approach? May 31, 2021 at 19:10
• I assume the a[] array stores every term of the sequence. Is this storage necessary, or do you just need to print the terms as they are generated? May 31, 2021 at 19:11
• no, any external libraries are not allowed. that makes the challenge trivial. May 31, 2021 at 20:18

# 142 bytes (-25)

3 more bytes saved by @ceilingcat.

a[9999]={0,1},i=2,k,s;main(c){for(;i--;c&&putchar(i?k+48:10))c|=k=a[i]>>4;for(;c=s>9,++i<9999;a[i]=k<<4|s%10)s=a[i]/16+c+(k=a[i]&15);main(c);}


Try it online! (GCC)

Try it online! (clang)

# 145 bytes (-22)

This is a complete rewrite which can probably be golfed some more.

a[9999]={0,1},i,k,s;main(c){for(i=2;;){while(i--)(c|=k=a[i]>>4)&&putchar(i?k+48:10);for(;c=s>9,++i<9999;a[i]=k<<4|s%10)s=a[i]/16+c+(k=a[i]&15);}}


Try it online! (GCC)

Try it online! (clang)

## How?

### Encoding

For each entry a[i] with i > 0, we store the i-th decimal digit of the last Fibonacci term into the bits 0 to 3 and the i-th decimal digit of the penultimate term into the bits 4 to 7. (The convention used here is that the 1st decimal digit is the least significant one.)

We start with all entries set to 0 except a[1] which is set to 1:

a[1] = 00000001
\__/\__/
|   |
|   +--> first and only digit of Fib(2) = 1
+------> first and only digit of Fib(1) = 0


It is then updated as follows:

00000001 -> 00010001 -> 00010010 -> 00100011 -> 00110101 -> ...
\__/\__/    \__/\__/    \__/\__/    \__/\__/    \__/\__/
0   1       1   1       1   2       2   3       3   5


### Printing

Each number is printed by iterating from the most significant digit to the least significant one, ignoring leading zeros and ending with a line-feed.

while(i--)
(c |= k = a[i] >> 4)
&& putchar(i ? k + 48 : 10);


We start with i = 2 and c = argc (which is guaranteed to be greater than 0) in order to make sure that the initial 0 is printed.

### Updating

In order to compute the next term Fib(n+1), we iterate through all values stored in a[], this time from least significant to most significant. We add the last digit to the penultimate one, update each entry accordingly and keep track of the carry into c.

for(; c = s > 9, ++i < 9999; a[i] = k << 4 | s % 10;)
s = a[i] / 16 + c + (k = a[i] & 15);


We have i = 9999 and c = 0 at the end of this loop, which are the expected values to print the next number, starting from the 2nd iteration.

We also end up with s = 0, which means that c will be re-initialized to 0 as expected before the next update.

• @ceilingcat Is it the correct link? This one core-dumps. Jun 3, 2021 at 14:53