I discovered Brainfuck around December 2002: I didn't participate in the Golf context 1 in August 2002, but wrote two entries in Golf contest 2 (December 2002).
By far the most complex pieces of brainfuck codes that I wrote are the entries for the two brainfuck component competitions.
I participated in rounds 1 and 2 of this competition. Unlike traditional golfing contests, in this competition the execution time was considered when computing the scores.
This took place in september 2004. The goal was to reverse a string of bytes. I got a little carried on and submitted several entries, each time discovering a way to speed-up the execution a little bit more, and thus to improve the score (if the input data was lenghty enough).
Results are stored on Daniel Cristofani's page, here.
After a number of 52-byte and 70-bytes entries had been posted, the 630-bytes entry by Bertram Felgenhauer, with the comment "Yes, I am serious" was a clear signal that there were ways to speed up more than 10 times the execution time. I then tried binary encoding, which was the obvious way of speeding things up. The first binary version would take one bit, update the number at other end, then go back taking the other bit. It was quite slow because the return journey was not used to copy bits back to the other side.
Then, I tried a shuttle (handling a bit back on the return journey).
It was faster, but quite lengthy (because it involved four copies of code like
[>]>[>]>[>]>[>] to move bits).
Refining this, I used at some time four [>]>[>]>[>], then
finally the secret weapon was discovered: using [[>>]<] to
move bits. This bit-moving part was so small it was possible to consider
putting it 8 times in code instead of 4: the final 476-byte entry
swaps bits two by two.
Here is the the promised "award", a GIF picture that Keymaker
specifically made for the competition.
See the commented source code for the final entry.
Daniel Cristofani wrote:
I also say "Congratulations, Laurent", though what impresses me most is the concision and cleverness of the code on the brainfuck level. The details of the algorithm are no surprise, but getting them into 476 bytes is a stunning accomplishment.
-Daniel Cristofani.
My entry was the only one submitted, and was declared winner.
Commented source code is here.
Keymaker wrote:
Whoaaah! That's awesome piece of programming Laurent!
Congratulations!
Although you're winner already, I'll do the official testing later today and post the info in this topic. Very droolish techniques there.
111111110a
^
[<<-[<-]++[>]>-]
hxxxxxxl00 (h = high-order bit; l = low-order bit)
^
a000000000 ^ [>>[>]+<[-<]<-]+ 00lxxxxxxh ^
[[>>]<]
General ideas:
[>>] or [>>>]; decrement at end of loop.Example:
a0011111111110bc
^
[[<<]>[-]<<+[>>>]>-]<+>>
ab0011111111110c
^
If the rail is very long, numbers can be decremented two by two, see the epilogue of my BCC1 entry.
I wanted to try writing a fast brainfuck interpreter, and I was interested in trying GNU lightning, which is is a library that generates assembly language code at run-time. The result is a very fast interpreter.
Comparing to bff4, and bffsree, which are both reported to be "fastest in its class" according to the Brainfuck page on esolangs, my interpreter is sensibly faster for lengthy programs:
| program | mandel.b | hanoi.b | sisihi.b | long.b |
|---|---|---|---|---|
| bff4 | 9.2s | 0.6s | 6.4s | 3.9s |
| bffsree | 4.8s | 0.2s | 1.3s | 0.2s |
| bf-li | 1.3s | 0.2s | 0.9s | 0.4s |
(bff4 and bf-li being compiled with gcc 4.5.3 running on cygwin. All timings done with output redirected to /dev/null to avoid the slow windows console performance.)
Comparing to another class of "optimizers", and referring to the excellent comparison between esotope-bfc and various Brainfuck compilers and optimizers, my quick and dirty implementation reaches the "pointer propagation" stage but does not achieve "advanced loop optimization".
As a joke, I also implemented a brainfuck interpreter in sed.