Optimized FizzBuzz in brainfuck

Question

While looking for brainfuck related things, I came across Simon Forsberg's FizzBuzz in Brainfuck and cheekily commented a link to my own brainfuck FizzBuzz answer over on PPCG. He suggested I should post my own Code Review question with a detailed explanation.

First, the code (350 bytes):

+[-[>+<<]>-]>--[>+>++>++>++++++>+>>>++++++<<<[<]>- 
]<+++++[>+>+>->>->++>+>>--[<<]>-]>[>]<--<->>>[<<-[
<]<[>+++>+<<.<.<..[<]<]>>-[<<]>[<+++++>.>.>..[>>>]
<<+[<]]>[>>>]<<[[-]>>]>[>++++++++++[->++++++++++>+
<<]<[->+>-<<]>>++[>[>>>]<[>++++++++++>+>]<<-<-]+++
++++++>[-<->]<[->+<]>>[>]++++++++[-<++++++<++++++>
>]<<<[>[-]]>[>]<[.[-]<]<[-<+>]>]++++++++++.[-]<<-]

Try it online!

This can be split into three sections:

• Tape generation: Sets up the tape in the correct format
• While looping over 100 numbers:
  • Checking the number: Checks if the number is divisible by 3 or 5, and printing Fizz and/or Buzz if so.
  • Printing the number: Only if it isn't a FizzBuzz number

Tape Setup:

• Cell 3: The counter for the "Buzz" section
• Cell 4 through 8: These are the ascii values for "BuziF", a compact way of representing both "Fizz" and "Buzz".
• Cell 9: The counter for the "Fizz" section
• Cell 11: The overall counter to keep track of the 100 numbers

Brainfuck code:

Generates the number 61:
+[-[>+<<]>-]>--
This is taken from the Esolangs brainfuck constants page at https://esolangs.org/wiki/Brainfuck_constants

Sets all the cells to values very close to the needed ones
Basically multiplies 61 by various values (going over 255 wraps around to 0)
[>+>++>++>++++++>+>>>++++++<<<[<]>-]
Tape looks like:
    0 0' 61 122 122 110 61 0 0 110
It needs to be:
    0 5  66 117 122 105 70 3 0 100
Notice that (almost) all of these values are off by multiples of 5 so we increment a cell to 5
<+++++
And add/subtract 5s from each value
[>+>+>->>->++>+>>--[<<]>-]
Leaving the tape as:
    0' 5 66 117 122 105 71 5 0 100
We make some final changes to get the desired cells
>[>]<--<->>>
    Before leaving the memory pointer on the counter

---

Inside the Loop:

Checking if Fizz/Buzz

Both the Fizz and Buzz counters are initially set to 5 and 3 respectively. At each iteration of the loop, both counters are decremented. If either reach 0, their respective string is printed and resets the counter. It also sets a check for later to not print the number. Here's a python representation of this section of the code.

fizz = 3
buzz = 5
for i in range(1,101):
    check = False
    fizz -= 1
    buzz -= 1
    if fizz == 0:
        print("Fizz",end='')
        fizz = 3
        check = True
    if buzz == 0:
        print("Buzz",end='')
        buzz = 5
        check = True
    if not check:
        print(i,end='')
    print()

The relevant brainfuck section is:

Tape Format:
    0 BCounter "BuziF" FCounter Check 0 Counter

<<- Decrement Fizz counter
[<]<[ If Fizz counter == 0
    >+++   Reset counter
    >+<<   Increment check cell
    .<.<.. Print "Fizz"
[<]<]
>>- Decrement Buzz counter
[<<]>[ If Buzz counter == 0
    <+++++   Reset counter
    >.>.>..  Print "Buzz"
    [>>>]<<+ Increment check cell
[<]]

Printing the number

If the FizzBuzz check is empty, we need to print the number as an actual string. Since brainfuck doesn't have a way to convert a cell value to a printed number (surprise surprise), we need to convert the counter to two ASCII values (not three, since 100 is "Buzz") representing the number.

However, the counter is counting down from 100, we first need to subtract it from 100. Then we get the number modulo 10, which leaves us the tens and singles in different cells. Before printing though, we need to check whether the tens digit is 0, in which case we remove it. Then we add 48 to the numbers to convert it to the ASCII value of the number and print them. Here's some more python code:

def printNumber(n):
    #Only works for numbers between 0 and 100
    tens = n//10
    singles = n%10
    if tens != 0:
        print(chr(tens+48), end='')
    print(chr(singles+48), end='')

The relevant brainfuck code:

If the number check is 0 (reset the cell if not)
>[>>>]<<[[-]>>]>
[
    Tape looks like:
        BuziF c 0 100-N' 0  where 100-N is the counter and N is the number
    We won't use anything left of the 100-N

    Generate the number 100 and the number 10
    >(10++++++++++)[->(10++++++++++)>+<<]
    Tape: 0 100-N 0' 100 10
    Subtract 100-N from 100 while keeping a copy of the 100-N
    <[->+>-<<]
    And increment N by 2 to counter some modulo stuff
    >>++
    Tape: 0 0 100-N N+2' 10 0
    [ While N
        Tape: 0 0 100-N N' Modulo Quotient 0;
        >[>>>]< If the modulo is 0:
            [>++++++++++>+>] Reset the modulo to 10 and increment the Quotient
        <<-<- Decrement both N and the modulo
    ]
    Tape: 0 0 100-N 0' 9-single tens
    Subtract the singles cell from 10
    +++++++++>[-<->]<[->+<]>>[>]
    Tape:  0 0 100-N 0 single tens 0'
    If the tens cell is 0: 
     Tape: 0 0 100-N 0 single 0'

    Add 48 to both cells
    (8++++++++)[-<(6++++++)<(6++++++)>>]
    Tape: 0 0 100-N 0 single tens 0'
    OR
    Tape: 0 0 100-N 48 single 0'

    If the tens cell was 0 reset the 48 cell
    <<<[>[-]]
    Tape: 0 0 100-N 0 single tens 0'
    OR
    Tape: 0 0 100-N 0 single 0'

    Print the tens (if needed) and singles while resetting the cells
    >[>]<[.[-]<]<
    Move the 100-N cell back to the correct position
    [-<+>]>
    Tape: 0 100-N 0' 0 0
]

---

And Finally!

Printing a newline

++++++++++.[-]

And decrementing the counter

<<-]

Main Questions:

• Can I make this any more optimized? My biggest concerns are:
  • The number printing section, which is extremely inefficient with the modulo section
  • The tape setup, which can probably be shorter.
  • Should I setup the newline cell (10) in the tape generation section rather than generate it once per loop?

By just going through it in such detail in this question I've already thought of several ways to shorten the code, so there's that at least.

TAPE FORMAT:
0
5   : Buzz Counter (BC)
66  : ASCII "B"
117 : ASCII "u"
122 : ASCII "z"
105 : ASCII "i"
70  : ASCII "F"
3   : Fizz Counter (FC)
0   : FizzBuzz Check (Ch)
100 : Loop counter (C)
0

Some definitions:
' : Memory pointer is on this cell
_ : Substitute for dash
p : Substitute for plus
N : The current number

Generates the number 61:
+[-[>+<<]>-]>--
This is taken from the Esolangs brainfuck constants page at https://esolangs dot org/wiki/Brainfuck_constants

Sets all the cells to values very close to the needed ones
Basically multiplies 61 by various values (going over 255 wraps around to 0)
[>+>++>++>++++++>+>>>++++++<<<[<]>-]
Tape looks like:
    0 0' 61 122 122 110 61 0 0 110
It needs to be:
    0 5  66 117 122 105 70 3 0 100
Notice that (almost) all of these values are off by multiples of 5 so we increment a cell to 5
<+++++
And add/subtract 5s from each value
[>+>+>->>->++>+>>--[<<]>-]
Leaving the tape as:
    0' 5 66 117 122 105 71 5 0 100
We make some final changes to get the desired cells
>[>]<--<->>>
Finally leaving the memory pointer on the counter

TAPE: 0 5 66 117 122 105 71 5 0 100'

[
    CHECKING FOR FIZZBUZZ
    <<- Decrement Fizz counter
    [<]<[ If Fizz counter == 0
        >+++   Reset counter
        >+<<   Increment check cell
        .<.<.. Print "Fizz"
    [<]<]
    >>- Decrement Buzz counter
    [<<]>[ If Buzz counter == 0
        <+++++   Reset counter
        >.>.>..  Print "Buzz"
        [>>>]<<+ Increment check cell
    [<]]

    PRINTING NUMBER
    If the number check is 0 (reset the cell if not)
    >[>>>]<<[[-]>>]>
    [
        TAPE: BC BuziF FC 0 100_N' 0 
        We won't be using anything left of the 100_N so we can ignore it

        Generate the number 100 and the number 10
        >(10++++++++++)[->(10++++++++++)>+<<]
        Tape: 0 100_N 0' 100 10
        Subtract 100_N from 100 while keeping a copy of it
        <[->+>-<<]
        And increment N by 2 to counter some modulo stuff
        >>++
        Tape: 0 0 100_N Np2' 10 0
        [ While N
            Tape: 0 0 100_N N' Modulo Quotient 0;
            >[>>>]< If the modulo is 0:
                [>++++++++++>+>] Reset the modulo to 10 and increment the Quotient
            <<-<- Decrement both N and the modulo
        ]
        Tape: 0 0 100_N 0' 9_single tens
        Subtract the singles cell from 10
        +++++++++>[-<->]<[->+<]>>[>]
        Tape:  0 0 100_N 0 single tens 0'
        If the tens cell is 0: 
         Tape: 0 0 100_N 0 single 0'

        Add 48 to both cells
        (8++++++++)[-<(6++++++)<(6++++++)>>]
        Tape: 0 0 100_N 0 single tens 0'
        OR
        Tape: 0 0 100_N 48 single 0'

        If the tens cell was 0 reset the 48 cell
        <<<[>[-]]
        Tape: 0 0 100_N 0 single tens 0'
        OR
        Tape: 0 0 100_N 0 single 0'

        Print the tens (if needed) and singles while resetting the cells
        >[>]<[.[-]<]<
        Move the 100_N cell back to the correct position
        [-<+>]>
        Tape: 0 100_N 0 0' 0
    ]
    Print a newline
    ++++++++++.[-]
    And decrement counter
    <<-
]

Answer 1

Tape setup

Esolang constants are compact, but not efficient. You are using an esolang constant to get the number 61, but what you actually want is a series of numbers: 0 5 66 117 122 105 70 3 0 100. In this case Esolang constants doesn't really help. Instead, it helps to look at the series of numbers as a whole.

Let's use the same approach as I used in another answer and look at how we can generate these numbers:

0 5 66 117 122 105 70 3 0 100

Sorted by numeric value:

0 0 3 5 66 70 100 105 117 122

Grouping into different ranges:

0-5 66-70 100-105 117-122

Some code:

+++++ +++ [- 8 times
> 0
> +++++ +++ 8 = 64
> +++++ +++++ +++++ 15 = 120

> +++++ +++++ +++++ 15 = 120
> +++++ +++++ +++ 13 = 104
> +++++ ++++ 9 = 72

> 0
> 0
> +++++ +++++ ++ 12 = 96
<<< <<< <<<
]
> +++++ 0 to 5
> ++ 64 to 66
> --- 120 to 117
> ++ 120 to 122
> + 104 to 105
> -- 72 to 70
> +++ 0 to 3
>
> ++++ 94 to 100

Your current approach spends 2902 runtime actions to generate the numbers, using 96 code commands.

My approach is 623 runtime actions and 132 code commands.

My approach can probably be improved further by using a different multiplicator than 8, or by using nested multiplication.

FizzBuzz printing

Very efficient FizzBuzz printing. If any improvements could be made here it would only be very minor ones so I will not focus on this. Good job.

Number printing

I like that you are using your own modulo calculations instead of copying the classical Brainfuck code to print a number. To print the number 165 the linked Stack Overflow code has 3242 runtime instructions and 234 code instructions. Having 72 on the tape (meaning printing 29), you are using 1338 actions with 183 code instructions. So you are already more efficient than the Stack Overflow code.

Speaking of efficiency however, it's quite inefficient to copy/move/calculate with bigger numbers. The bigger the numbers are, the more inefficient it is. What you could do is to prepare the tape for a few digits where each digit has:

• Value
• 10 minus value (This is actually not needed for you, it's only required when counting upwards)
• Decimal representation of value (48 + value)

Then in each of your 100 iterations you would do the following:

• Go to the least significant digit
• Check for overflow by checking if the value is 0
  • In case of overflow:
  • reset digit value to 9
  • reset decimal representation
  • go to next digit and repeat overflow check
  • If no overflow, decrease the digit

If you would keep it separated into digits you would never have to run things in a loop more than 9-10 times to reset the values. This approach is similar to what I used in my Fibonnacci code.

Printing numbers by keeping digits separated is extremely efficient as you can simply navigate to the decimal representation and print it.

Newline

Having the newline constant 10 on the tape instead of generating it every time would indeed be faster, as long as it's less than ~10 steps away from your current position on the tape - as you use 10 commands to create it and then 10 (plus the loop) to decrease it again. Comparing this to moving left or right up to 10 times, moving would be faster.

Having reserved positions on the tape for the digits would also make it easier to have the newline as a constant on the tape instead of generating the number in every loop.