Brainfuck question about negative characters

Johnaudi · February 18 2014

Hey I've been playing around brainfuck lately, then I found a type of Text2Brainfuck converter, well, the thing that was amazing there was that when I have inputted 's' as text, it gave me this:

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

It looks like it's going to a negative char, so I tried doing so myself ( -[-.] ) and I figured out that it's reading the characters in a descending kind-of way. Then I realized that it's going to 255 when passed under 0.

So the main question is, what's more preferable? Should I start using the shortcut to 255 or keep on using my way? Would it affect performance in any kind? (I printed s with

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

and that's quite big)

Last edited by Johnaudi (February 18 2014)

Joe · February 18 2014

Base hypothesis

Let me start by stating the obvious: this kind of nano-optimizations is ludicrous, cute and entertaining. But it's not something anyone will ever need to care about. (Not to mention the futility of optimizing a brainfuck program for performance). Now that being said, I think that this makes for an interesting exercise. For the sake of sanity, let's make some assumptions first:

We'll only consider in our measurments the cost of in/decreasing the value of a cell and translating the pointer. That means that we're only considering the operations + - > < and ignoring the rest. That means we're ignoring jumps, tests and io operations. Note that I have no idea how CPUs work so I don't know if these assumpstions are valid.
Again for the sake of sanity, we'll consider that each of the 4 operations are equivalent in performance. That means that given a pointer on int i, I'm considering that i++ and *i++ are equivalent in execution time.

Counting the operations

Here's the generated piece of code:

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

Each iteration of the loop has 13 operations, and it's not difficult to realize that this loop is going to be executed 57 times. Adding the 3 operations outside the loop, that's a total of:

57 * 13 + 3 = 744 operations.

In contrast your piece of code is:

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

Although it looks like it has more characters, it's actually doing a lot less operations. Your loop has 13 operations as well. It's executed 10 times, and it has 16 extra operations outside the loop, so:

10 * 13 + 16 = 146 operations.

By most measurements, your code should execute faster.

Conclusion

It should execute faster, but it's not going to. Because the way CPUs work internally, and because of the assumptions we made, and most importantly, because any modern CPU will execute this instantly. Something as simple as printing "hello world" in a language like python needs several orders of magnitude more operations and is executed instantly. It is virtually impossible to measure any difference in execution time between the 2 pieces of code you're trying to compare.

Moreover, even considering you manage to create something remotely usable in brainfuck, this kind of optimization is almost never relevant. Most programs will be stuck waiting for some sort of IO operation, (and in 2014 this IO will be done in a network-distributed fashion), so caring about shaving off microseconds of CPU time is often refferred to as "premature optimization" (a.k.a "the root of all evil")

Going further

That being said the exercise is not completely irrelevant. Brainfuck never was (and never will be) a language with any real world value, but it's great for exerising. Here are some ideas you can explore:

The biggest mistake your program makes is assuming that you need to output only one character and exit. That will never happen. Instead you'll be asked to print several characters to form a sentence. It would be smart to start by pre-populating a fixed number of cells with values that should cover a good range of the ascii alphabet so you avoid raising these values each time. We have already explored something similar on this forum.
As I mentioned before, it doesn't make sense to optimize for performance, but it would make sense to optimize for readability. Try to write a program that takes a string as an input and outputs the shortest brainfuck program that will output this script to the screen once executed.

Johnaudi · February 18 2014

Thanks!

Well, I've been trying to play up with it all afternoon. It's quite fun. Feel free to correct any mistakes...

// John
+++++ ++ [ > +++++ +++++ < -] >++++. [-] +++++ +++++ + [ > +++++ +++++ < - ] > + . --- --- - . > [-] +++ [< ++ > -] < .

// My Email
+++++ +++++ + [ > +++++ +++++ < -] > +++++. // s (115)
++. // u (117)
-----.. // p (112)
-. // o (111)
+++. // r (114)
++. // t (116)
> +++++ +++ [ > +++++ +++ < -] >. // @ (64)
< [-] +++ [< --- > -] < -. // j (106)
+++++. // o (111)
-------. // h (104)
++++++. // n (110)
> +++ [ < ---- > -] < -. // a (97)
> +++++ [ < ++++ > -] <. // u (117)
> +++ [ < ----- > -] < --. // d (110)
+++++. // i (105)
> +++++ >[-]< [ > +++++ ++++ < -] > +. // dot (46)
<< --- ---. // c (99)
> ++++ [ < +++ > -] <. // o (111)
--. // m (109)

Joe · February 20 2014

John, the main advice I can give you is to start exploring multiple cell solutions.
You kinda did it in your email address print program, but it's awkward and far from optimal. For example:

< [-] +++ [< --- > -] < -. // j (106)
///
> +++++ >[-]< [ > +++++ ++++ < -] > +. // dot (46)

Is it even necessary to start by zeroing these cells?

Take a look at this code:

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

Notice how it is more compact, and more importantly how it doesn't use nearly as many loops as your code.

Explanation

You start by preallocating 4 values in 4 cells. To ease debugging, I'm printing inside parenthesis the values of cells 1 to 4 after the execution of each command.

++++++++++[>+++++++>++++++++++>+++>+<<<<-]> (70; 100; 30; 10)

From here, every time you need to print a character, you locate the cell whose current value is closest to your target value and modify only it:

s >+++++++++++++++. (70; 115; 30; 10)
u ++. (70; 117; 30; 10)
p -----. (70; 112; 30; 10)
p . (70; 112; 30; 10)
o -. (70; 111; 30; 10)
r +++. (70; 114; 30; 10)
t ++. (70; 116; 30; 10)
@ <------. (64; 116; 30; 10)
j >----------. (64; 106; 30; 10)
o +++++. (64; 111; 30; 10)
h -------. (64; 104; 30; 10)
n ++++++. (64; 110; 30; 10)
a -------------. (64; 97; 30; 10)
u ++++++++++++++++++++. (64; 117; 30; 10)
d -----------------. (64; 100; 30; 10)
i +++++. (64; 105; 30; 10)
. >++++++++++++++++. (64; 105; 46; 10)
c <------. (64; 99; 46; 10)
o ++++++++++++. (64; 111; 46; 10)
m --. (64; 109; 46; 10)

This approach is even more effective if you need to mix upper/lower case characters, with digits and punctuations.

Try to improve it

This approach is far from optimal and will hit a lot of pain points in a real world program (not to mention that "real world" in 2014 means Unicode... Ouch). If you want to take this further:

I took the initial values of the cells from The Wikipedia example, but I have no idea if it's optimal. You could experiment with different values run against real world texts and try to determine which are the most effective initial values (whatever your definition of "most effective" is).
Some big value changes can really benefit from looping (for instance u ++++++++++++++++++++. (64; 117; 30; 10)). However, as you notice, it is hard to keep track of multiplier cells. When you do it manually, it becomes messy. So you need a program that manages cell bookkeeping for you. You could write a script that reserves a few cells at the beginning of the memory for that purpose.

These are random ideas off the top of my head. Let me know if you're interested in pursuing this further.

Johnaudi · February 20 2014

Yeah I've realized that, though I'd liked the language to be more challenging, so I've seen how far I would've taken to without having too many plus and minus signs.

I find it a bit too easy to form words by allocating it your way, no offense intended of course, but it ruins the complexity of the language in-front of my eyes.

Well, I guess everyone has a way to do it, but thanks for teaching me the new way, yours is way easier to understand and use.

So yup, that'd sum it up, will be using yours when I feel like doing some sentences, so thanks!

LebGeeks

#1 February 18 2014