Tips for golfing a fibonacci sequence generator

Question

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

Answer 1

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.