3
\$\begingroup\$

Yesterday when I was showering I was thinking of branchless programming and a thought occurred to me, whether it's possible to write a branchless solution of the Fizbuzz problem. The constraints I put on myself were no if statements, no switches, no ternary operators and no loops. The code below seems to solve this problem as well as test the first 100 numbers:

#include <unistd.h>
#include <string.h>
#include <setjmp.h>
#include <stdlib.h>
#include <stdio.h>

jmp_buf buf;

int jump(jmp_buf buf)
{
  longjmp(buf, 1);
}

int wrapexit()
{
  exit(0);
}

void fizbuzz(int num)
{
  char str[5];
  sprintf(str, "%d\n", num);
  (num % 3 && num % 5) &&  write(0, str, 5);
  write(0, "fizbuzz\n", strlen("fizbuzz\n") * !(num % 15)) && jump(buf);
  write(0, "buzz\n", strlen("buzz\n") * !(num % 5)) && jump(buf);
  write(0, "fiz\n", strlen("fiz\n") * !(num % 3));
}

int test(int num)
{
  int throaway = (num == 101 && wrapexit());
  fizbuzz(num);
  int status = setjmp(buf);
  status && test(num + 2);
  !status && test(num + 1);
  return 0;
}

int main(void)
{
  test(1);
  return 0;
}

Also, I know I'm not doing any buffer length checks when I'm stringizing num at the beginning of fizbuzz. Anyway, code reviews most welcome.

\$\endgroup\$
1
  • \$\begingroup\$ "Branchless Fizbuzz"?? (num % 3 && num % 5) && write(0, str, 5); looks like branching code to me with its &&. \$\endgroup\$ Nov 8, 2021 at 18:42

2 Answers 2

2
\$\begingroup\$

Any time you do an && function(...), you have a conditional branch. One might even, with good reason, count function calls as branches as well. And setjmp() is usually implemented by changing the stack pointer and then calling a ret instruction or something similar, which in effect is also a branch.

The closest you can come to having a "branchless" fizbuzz in C is by unrolling the loop and writing 15 lines at a time:

void fizbuzz(int num) {
    printf("%d\n", num++);
    printf("%d\n", num++);
    printf("fiz\n"); num++;
    printf("%d\n", num++);
    printf("buzz\n"); num++;
    printf("fiz\n"); num++;
    printf("%d\n", num++);
    printf("%d\n", num++);
    printf("fiz\n"); num++;
    printf("buzz\n"); num++;
    printf("%d\n", num++);
    printf("fiz\n"); num++;
    printf("%d\n", num++);
    printf("%d\n", num++);
    printf("fizbuzz\n"); num++;
    fizbuzz(num); // tail recursion
}

It still calls functions, and at the end it will jump back to the beginning. But at least they are all unconditional branches.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Perhaps drop the 15x num++, use one long printf() and then fizbuzz(num+15);? \$\endgroup\$ Nov 8, 2021 at 18:39
  • \$\begingroup\$ You can also have 100 printf statements - no recursive loop needed. Or just hard code the results ;-) \$\endgroup\$
    – jdt
    Nov 10, 2021 at 13:37
2
\$\begingroup\$

You don't use it, but your restrictions don't seem to exclude it, so if you make use of the || operator things can be simplified.

void fizbuzz(int num)
{
    !(num % 15) && printf("fizbuzz\n") ||
    !(num % 5) && printf("buzz\n") ||
    !(num % 3) && printf("fiz\n") ||
    printf("%d\n", num);
}

Then you don't need to use setjmp and can get rid of the jump function.

test then becomes a smaller 4 line function:

int test(int num)
{
    num == 101 && wrapexit();
    fizbuzz(num);
    test(num + 1);
    return 0;
}
\$\endgroup\$
2
  • \$\begingroup\$ Damn, this is so much better, didn't even think of logical or. And also you're using printf which is unbuffered so that's another plus. \$\endgroup\$ Nov 5, 2021 at 19:02
  • \$\begingroup\$ *buffered, printf is buffered, write is unbuffered. \$\endgroup\$ Nov 6, 2021 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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