Talk:Brainfuck algorithms
Alternate If-Else (by Ben-Arba)
An alternate if-else, which I was unsure of how to express with the variable name notation. I don't know whether it's essentially a duplicate of the current if-else, but they looked different enough.
The pointer will always be at x when either code1 or code2 is executed. It should be returned there once the code is done, and temporaries must not be interefered with. The temps both end up zero once the conditional has evaluated, and the pointer ends at x.
The tape: x y z Pointer begins at x. y and z are temporaries. >[-]+ >[-]<< [ code1 >-]> [<code2>->]<<
Let me know what you think.
-- Ben-Arba -- 06:45, 11 Oct 2005 (GMT)
Very cool.. This should be equivalent:
temp0[-] temp1[-]+ temp2[-] temp0[ code1 >-] temp1[ temp0 code2 temp1- temp2] temp0
--Calamari 12:59, 12 Oct 2005 (GMT)
- Trying to work out the rules here for the notation and unbalanced loops. You example seems to use two different sets of rules. The first loop appears to be done on the assumption that the loop will not be taken with the literal '>' showing that the loop is in fact unbalanced. The "temp1" prefix to the second loop is only correct if the first loop is not taken; in the event it's taken this is in fact "temp2". On the other hand the second loop seems to be labelled based on the assumption that the loop is taken with it's unbalanced nature being confused by the "temp1" and "temp2" labels at the start and end of the loop. This leads to an ambiguity in how the notation should be interpreted; ie: is the last temp0 one or two '<' instructions.
- My opinion? As a loop can be skipped I think the labelling outside the loop should be done on the assumption that this does in fact happen. If the loop is unbalanced it should be treated as if it's balanced until the matching ']' at which point the total shift should be placed before it ie: '>]'
- Of course this leads to another problem; for this example the total shift within the loop is always one '>' this means by my rule the last '<' appears to move the pointer to the cell before "temp0"
- Is there a better solution ? Rdebath (talk) 12:08, 16 December 2013 (UTC)
Bitwise XOR OR AND
Is there a known way to get bitwise 'xor', 'or' and 'and' in brainfuck? -Acyd
Algorithms for interactive gopher
These are good algorithms. Probably on weekend I might add some more words to the core definition file for BrainClub so that I may write better program for interactive gopher client, including some online games, and a few other things also, such as security features, special types of data needed to be entered that normal form fields of ASK forms cannot support very easily, and any other uses you can think of for interactive gopher. --Zzo38 20:51, 10 February 2009 (UTC)
FRAK
Please take a look at FRAK brainfuck assembler. It has logical and bitwise operators and conditional structures (OK, IF/THEN/ELSE is not usually part of an assembly language, but see them as macros). It is a toy assembler I made for fun (as well as a proof of concept), but it could be improved to be more efficient and serve to develop larger « production » programs.
An idea I'd like to try is to manipulate cells in group of 8 to simulate chunks of 8 bits. I think this approach would allow the implementation of fast arithmetic routines. It would be the only efficient way to manipulate larger numbers I see. The memory trade off could be partially offset by supporting 2 subset of load/storage instructions. I don't have much time, but if someone is interested by this endeavor, I'd like to contribute.
Improved x and y (logical)
Less operations, less temp variables
In the notation I use..
0 : 0-x 1-y 2-0 //before 0 : 0-(x && y) 1-0 2-0 //after
temp0[-] x[temp0+x[-]] y[x+y[-]] x[-temp0[-y+temp0]x] y[-x+y] temp0[-] x
Written by James Ferrier, if it makes it to the article.
- It's different in effect from the one in the article though, it does not preserve y. And I think it can be shortened further:
temp0[-] x[y[temp0+y[-]]x[-]] temp0[-x+temp0] y[-] x
- --Ørjan 06:19, 11 April 2010 (UTC)
Compare issue
19th algo is wrong, current implementation works as "x = x <= y".
Make sense.
Update: 20th algo is wrong too. Heh. Any one ?
Update2: fix in wiki.
Divmod algorithm
When running the divmod algorithm with 1 as divisor, it behaves differently then stated.
For example running it in this state
0, 0, 0, >5, 0, 1, 0, 0
Results in this state
>0, 0, 0, 4, 1, 0, 0, 0
Instead of the expected state
0, 0, 0, >0, 5, 1, 0, 5
Running it with other divisors works fine so far. For example running it in this state
0, 0, 0, >5, 0, 2, 0, 0
Correctly results in this state
0, 0, 0, >0, 5, 1, 1, 2
--Somelauw (talk) 00:33, 4 May 2015 (UTC)
Print value of cell x as number (8-bit)
This quotes stack overflow as the source, and stack overflow says this is the source. Circular reference loops are amusing, but not the most useful.
IF-snippet wrong?
The first snippet in the section if(x) {code} doesn't work for me. My implementation:
+++
> (comment block)
Starting situation:
[x,t1,t2, y]
[3, 0, 0, 0]
^
trying to achieve: if (x != 0) {y=5} // should result in y=5
<
[>+>+<<-]>[<+>-]>[>+++++<-]
Result: y=15
Is it a mistake of the page or of my implementation? To me that code seems to be a simple non-destructive for(x) loop.
~Sinthoniel 14:27, 19 October 2015 (UTC)
If x else with only one temporary cell
Recently - while looking for a more efficient way of checking, if(x==0), and having deployed one of my two empty cells to another task - I stumbled upon a, as I believe, more efficient way of checking, whether x is TRUE (i.e. has any value except 0) or not. I wanted to submit it to scrutinization by the community.
temp0[-]+ x[ code1 temp0 -] temp0 [code2 temp0-]
Basically it comes down to this:
SET temp0 = 1
IF(x==TRUE)
code1
SET temp0 = 0
IF(temp0==TRUE) //Which it wouldn't be, if x was true
code2
SET temp0 = 0
Since temp0 is set to zero at the end of every loop, the loops are left after being executed once - which is just the way it's supposed to be. Would love some feedback.
Kind regards,
Arduvast Gundar
14:38, 9 January 2016 (UTC)~
- I think what you want as the movement to "temp0" between the loops isn't resolvable, my understanding of the notation is that it makes the assumption that a movement after a `]` should be calculated as if the loop is skipped. I that case if the first loop is entered the pointer will not be pointing at either "x" or "temp0" at the start of the second loop. Though, to be sure I'd need you to converted into actual BF code, not the shorthand notation. (PS: The standard wiki signature uses ~~~~) Rdebath (talk) 15:55, 10 January 2016 (UTC)
Calculating the integer square root of x
There are several ways to calculate the integer square root; The first step is to find the first value of y for which y*y>x. However, 2*2<=6, while sqrt(6) == 2. So we can just return the last value of y for which y*y<=x, right? No, because now 3*3>8, while sqrt(8) == 3. Let's take y to be the first value for which y*y>x again. y is now equal to ceil(sqrt(x)) We want to remove one from it whenever floor(x/y) != y, because it doesn't make sense to return a square root y for which (y*y)/y != y. This seems to work:
assert(sqrt(9) == 3) assert(sqrt(8) == 3) assert(sqrt(6) == 2) assert(sqrt(2) == 1)
Great! Let's represent our algorithm in C (I'll add the other algorithms aswell, for comparison purposes):
#include <stdio.h>
#define assert(x)\
if(!(x)) {\
printf("%s:%d: Assertion failed!\n",__FILE__,__LINE__);\
exit(1);\
}
int sqrt_floor(int x) {
int y = 0; // The last value for which (y)*(y)<=x
if (x <= 0) return 0; // Edge case
while (y*y <= x) y++; // Find y
return y-1; // We are done!
}
int sqrt_ceil(int x) {
int y = 0; // The first value for which y*y>x
if (x <= 0) return 0; // Edge case
while (y*y < x) y++; // Find y
return y; // We are done!
}
int sqrt_real(int x) {
int s = 0; // The square root
int y = 0; // The first value for which y*y>x (sqrt_ceil)
int t; // Temporary value for integer division
if (x <= 0) return 0; // Edge case
while (y*y < x) y++; // Find y
// What we need is y - (floor(x/y) != y) instead of y.
// This because y = sqrt_ceil(x).
// ceil(x/y) cleverly returns y - (floor(x/y) != y)
// This next algorithm returns ceil(x/y) for x and y > 0:
t = x + y - 1; // Clever trick ((x+y-1)/y == ceil(x/y))
while (t > y) { // Integer division comes down to this.
t-=y;
s++;
}
return s; // We are done!
}
int main(void) {
assert(sqrt_floor(9) == 3); // Correct
assert(sqrt_floor(8) == 2); // Incorrect
assert(sqrt_floor(6) == 2); // Correct
assert(sqrt_floor(2) == 1); // Correct
assert(sqrt_ceil(9) == 3); // Correct
assert(sqrt_ceil(8) == 3); // Correct
assert(sqrt_ceil(6) == 3); // Incorrect
assert(sqrt_ceil(2) == 2); // Correct
assert(sqrt_real(9) == 3); // Correct
assert(sqrt_real(8) == 3); // Correct
assert(sqrt_real(6) == 2); // Correct
assert(sqrt_real(2) == 1); // Correct
return 0;
}
You can see that sqrt_real isn't actually such a big function. However, note that comparing integers is expensive.
YoYoYonnY (talk) 08:47, 4 February 2016 (UTC)
x < y more like x <= y
I am implementing these algorithms and I am pretty sure that
Ian Kelly's
x = x <= y temp0[-] temp1[-] >[-]+ >[-] << y[temp0+ temp1+ y-] temp0[y+ temp0-] x[temp0+ x-]+ temp1[>-]> [< x- temp0[-] temp1>->]<+< temp0[temp1- [>-]> [< x- temp0[-]+ temp1>->]<+< temp0-]
and
Ian Kelly's
x = x < y temp0[-] temp1[-] >[-]+ >[-] << y[temp0+ temp1+ y-] temp1[y+ temp1-] x[temp1+ x-] temp1[>-]> [< x+ temp0[-] temp1>->]<+< temp0[temp1- [>-]> [< x+ temp0[-]+ temp1>->]<+< temp0-]
Are both the same algorithm: x = x <= y.
My tests indicate they both perform x receives x less than or equal y
Please someone correct me if I am wrong
--LucasMW (talk) 19:24, 23 January 2018 (UTC)
Böhm's algorithms
Böhm (who invented P′′) also wrote some brainfuck programs (more than twenty years before brainfuck was invented), such as one to decrement a number represented using bijective numeration (given in Wikipedia). Do you have the other ones? --Zzo38 (talk) 06:57, 14 January 2020 (UTC)
New method of summing 1~x
This is a very simple script that only uses one temp variable and sums 1~x into a:
x[[temp0+a+x-]temp0[x+temp0-]x-]
--Softengy (talk) 04:32, 7 April 2020 (UTC)
Improved algorithm for x = x == y
This is a small improvement to the first algorithm to use one less temp variable:
y[x-temp0+y-] temp0[y+temp0-] x[[-]-temp0]x+
--Softengy (talk) 18:15, 7 April 2020 (UTC)
Improved algorithm for x = x != y
Similar to above, this just removes a temp variable:
y[x-temp0+y-] temp0[y+temp0-] x[[-]+temp0]
--Softengy (talk) 18:21, 7 April 2020 (UTC)
Shorter comparisons?
x' = x < y
For the non-overwriting one:
x y t0 0 0 0 --- t0[-]>[-]>[-]>[-]<<<< [>+>+<<-]>[-<+>]<<[->>+<<]+>>[>>+<<->-[>-]>[<<<<->>>>->]<<<]<< --- x<y y 0 y-x 0 0 ^
z = x < y
For the overwriting one:
z x y 0 0 --- z[-]>>>[-]>[-]<<< <+>[>>+<-<->[>-]>[<<<->>>->]<<<]< --- x<y 0 y-x 0 0 ^
SuperPizza (talk) 17:52, 3 December 2022 (UTC)
Why does
x[-]
require wrapping? --None1 (talk) 23:02, 8 August 2023 (UTC)
- In a signed, wrapping implementation,
[-]would loop infinitely for negative values. --Rosenthal (talk) 13:15, 15 September 2024 (UTC)
Add x´ = x mod y
Can you please add x´ = x mod y? I don't see it (it doesn't exist). Thanks! MihaiEso (talk) 16:54, 26 May 2024 (UTC)
- Isn't this what you are looking for? https://esolangs.org/wiki/Brainfuck_algorithms#Modulus_algorithm (
n´ = n mod d) Also, there's the various divmods Salpynx (talk) 20:28, 26 May 2024 (UTC)
Placeholder notation for bitwise not x
The second version of x´ = not x (bitwise), x-[[-]+y](y-1) is written with a notation for shifts that is different from all the others, and the comments don't make sense. What is this supposed to mean? --Rosenthal (talk) 13:15, 15 September 2024 (UTC)