10
\$\begingroup\$

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

\$\endgroup\$
6
  • 2
    \$\begingroup\$ :O I like the [A trick \$\endgroup\$ – Wzl May 31 at 16:45
  • 1
    \$\begingroup\$ @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); \$\endgroup\$ – Kamila Szewczyk May 31 at 16:46
  • \$\begingroup\$ Can you post an ungolfed (easier to read) version of the code, so we may more easily see your algorithmic approach? \$\endgroup\$ – Digital Trauma May 31 at 19:10
  • \$\begingroup\$ 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? \$\endgroup\$ – Digital Trauma May 31 at 19:11
  • 1
    \$\begingroup\$ no, any external libraries are not allowed. that makes the challenge trivial. \$\endgroup\$ – Kamila Szewczyk May 31 at 20:18
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ @ceilingcat Is it the correct link? This one core-dumps. \$\endgroup\$ – Arnauld Jun 3 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.