Skip to main content
Code Review

Return to Answer

replaced http://codereview.stackexchange.com/ with https://codereview.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1

200_success mentioned200_success mentioned that your code supported 8-bit Brainfuck interpreters as well, thanks to your if (x == 256) check. As I removed that check here, the above code doesn't work for 8-bit wrapping BF interpreters. However, that can be solved by instead of having one 256 value, you have 2 of value 128.

200_success mentioned that your code supported 8-bit Brainfuck interpreters as well, thanks to your if (x == 256) check. As I removed that check here, the above code doesn't work for 8-bit wrapping BF interpreters. However, that can be solved by instead of having one 256 value, you have 2 of value 128.

200_success mentioned that your code supported 8-bit Brainfuck interpreters as well, thanks to your if (x == 256) check. As I removed that check here, the above code doesn't work for 8-bit wrapping BF interpreters. However, that can be solved by instead of having one 256 value, you have 2 of value 128.

added 1499 characters in body
Source Link
Simon Forsberg
Simon Forsberg
  • 59.4k
  • 9
  • 156
  • 309

For 8-bit Brainfuck interpreters

200_success mentioned that your code supported 8-bit Brainfuck interpreters as well, thanks to your if (x == 256) check. As I removed that check here, the above code doesn't work for 8-bit wrapping BF interpreters. However, that can be solved by instead of having one 256 value, you have 2 of value 128.

Replace in the memory initialization:

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

with

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

This will initialize 2 cells with value 128 instead of one cell with value 256. Luckily, the cell after the 256 value was unused by my code, so this is an easy change.

Loop check:

Replace the start of the 256 loop:

[
    ->

with

[[
    ->

and replace the ] on the last line with ]>[-<+>]<].

This will, once the innermost loop has been finished, check for a value on the next cell and if there is a non-zero value there it will move it to the cell before and then it will use that value for the loop and continue decreasing until it hits zero. This will make your loop be performed x + y times, where in this case both x and y is 128, making it a total of 256. Of course these values could be adjusted to be 255 + 1 so that the moving of y to the position of x is performed faster.

Resulting performance

Analysis says that this code, with the support for 8-bit interpreters applied, only performs 30 220934 operations at runtime, which is about 2% of your 1.47 million. So this program will be 50 times faster than your original.

Analysis says that this code only performs 30 220 operations at runtime, which is about 2% of your 1.47 million. So this program will be 50 times faster than your original.

For 8-bit Brainfuck interpreters

200_success mentioned that your code supported 8-bit Brainfuck interpreters as well, thanks to your if (x == 256) check. As I removed that check here, the above code doesn't work for 8-bit wrapping BF interpreters. However, that can be solved by instead of having one 256 value, you have 2 of value 128.

Replace in the memory initialization:

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

with

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

This will initialize 2 cells with value 128 instead of one cell with value 256. Luckily, the cell after the 256 value was unused by my code, so this is an easy change.

Loop check:

Replace the start of the 256 loop:

[
    ->

with

[[
    ->

and replace the ] on the last line with ]>[-<+>]<].

This will, once the innermost loop has been finished, check for a value on the next cell and if there is a non-zero value there it will move it to the cell before and then it will use that value for the loop and continue decreasing until it hits zero. This will make your loop be performed x + y times, where in this case both x and y is 128, making it a total of 256. Of course these values could be adjusted to be 255 + 1 so that the moving of y to the position of x is performed faster.

Resulting performance

Analysis says that this code, with the support for 8-bit interpreters applied, only performs 30 934 operations at runtime, which is about 2% of your 1.47 million. So this program will be 50 times faster than your original.

Source Link
Simon Forsberg
Simon Forsberg
  • 59.4k
  • 9
  • 156
  • 309

Analysis

I analyzed your code with my Brainduck and I found a couple of improvements. First up, let's see what Brainduck says. I will not post the full output here, just the parts that I found the most interesting.

First of all, at runtime your program performs approximately 1.47 MILLION commands. This is quite much.

While loop - 49 to 58

My analysis showed interesting patterns in the number of times that your while loops are being performed. I found that some of your while loops have a clear sequence of:

[49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, (repeat 49 - 58 a couple of times...), 49, 50, 51, 52, 53, 54]

This means that the first time it is started it is performed 49 times, then 50, then 51, and so on up until 58, then it goes down to 49 times again, then 50, then 51, etc... this while-loop is your comparison of if (a == b).

What you are doing is comparing if (a == b), this is however a very long operation in Brainfuck, as you need to move the memory back and forth, it has a runtime complexity of \$O(n)\$ where \$n\$ is the value of a.

Modulo 10

There is also this interesting while loop:

[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, (1 x 9 times), 0, (1 x 9 times), 0, (1 x 9 times), 0, (1 x 6 times)]

This is you deciding whether or not to increase the next number in the tape, for example when the last digit changes from 9 to 0 it is time to increase the second to last digit from x to x + 1.

It is much more effective in Brainfuck to count down to zero rather than count up to \$x\$.

Instead of counting from 49 to 58 and comparing x to 58 all the time, initialize a memory cell nearby to 10 and count down to zero, when it has reached zero, it is time to reset it to 10 and increase the next number (going from 09 to 10).

The same principle can be applied to your ending condition, you initialize the value 256, and then you compare with 256 all the time. Instead initialize 256 and decrease it by 1 until it reaches zero, then it is time to end your loop.

Other small changes

Your code contains some sequences of >><< that leads to no change, which leads to it being possible to simplify. I would recommend that you simplify these and instead improve the comments about where the current tape position is located.

Resulting code

max   == 255
LF    == 10
space == 32
'0'   == 48
'9'   == 57
':'   == 58
Memory: counter
        ':' space LF
        char max&1 cmp1 0 0
        num1 '9'&1 cmp2 0 0
        num2 '9'&1 cmp3 0 0
        num3 '9'&1 cmp4 0 0

+++++ +++
[
    > +++++ ++
    > ++++
    > +

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

    >>>>
    > +++++ +
    > +
    >>>
    > +++++ +
    > +
    >>>
    > +++++ +
    > +

    <<<<< <<<<< <<<<< <<<<< -
]
> ++
>> ++
>>
>>>>> ++
>>>>> ++
>>>>> ++

<<<<< <<<<< <<<<<

Memory: 0
        58 32  10
        0 (Current Ascii) 256 (Countdown) 0 0 0
        48 10  0 0 0
        48 10  0 0 0
        48 10  0 0 0
positioned at 256 countdown
[
    ->

    >>> .
    >>>>> .
    >>>>> .
    <<<<< <<<<< <<<<< <<<
    .
    > .
    >> .+
    < .

    Number increasing logic
        >>>>> >>>>> >>>>> >
        +
            >-
            >+ set equal flag
            <   if num1 != 0
            [
                >-  clear equal flag
            ]
            >  if num1 == 0
            [
                Reset this counter to 10 and decrease digit to 0 again
                <+++++ +++++
                <----- -----
                Increase the next number by one
                <<<<< +
                > -
                Reset the equal flag
                >>>> >> - >
            ]
            <<[<] positioned at the digit

        <<<< goto next

            >>+ set equal flag
            <   if num1 != 0
            [
                >-  clear equal flag
            ]
            >  if num1 == 0
            [
                Reset this counter to 10 and decrease digit to 0 again
                <+++++ +++++
                <----- -----
                Increase the next number by one
                <<<<< +
                > -
                Reset the equal flag
                >>>> >> - >
            ]
            <<[<] positioned at the digit

    <<<<< <<<
]

The only changes here are that I never do if (a == b) comparison and instead always decrease some value down to 0 instead. This applies to both your if (x == 58) checks and your if (x == 256) check.

Analysis says that this code only performs 30 220 operations at runtime, which is about 2% of your 1.47 million. So this program will be 50 times faster than your original.