Talk:Brainfuck constants
Maybe the solutions with '>' before only a row of '+' or '-' should be removed? I mean, I don't see much use for the one instruction longer solutions where only the pointer is moved right in the beginning. User:Keymaker
- The idea behind those was that, for example, if I had a 2-cell that calculated 56, but that I wanted to easily change my program to use 13 instead, I could just drop in the 2-cell version of 13. If this is not a concern, then it seems logical to only include the very best wrapping and non-wrapping, regardless of cell size.Calamari 21:17, 19 Jul 2005 (GMT)
- If we go this route, may I also suggest that we remove "duplicate" listings (there really only needs to be one entry per best wrapping and nonwrapping)? This would cut down the size of the list quite a bit! IMO, The version to keep would be the one executing the least instructions. Calamari 21:29, 19 Jul 2005 (GMT)
- I'm going to go ahead and make the change.. this page is way too large. Calamari 22:22, 19 Jul 2005 (GMT)
- I've started the work, but it will take time. If anyone wants to help, the non-wrapping 3 cell w[>x[>y<-]<-]>>z takes w+w(x+x(y+5)+5)+2+z => w(x(y+6)+6)+z+2 instructions, and the 2 cell x[>y<-]>z takes x+x(y+5)+1+z => x(y+6)+z+1 instructions. I haven't determined instruction count formulas for the wrapping versions yet. They are more complicated because the number of cycles for w[>x<y]>z depends not only on the inc/decrement size y, but also the starting value w. Calamari 05:26, 20 Jul 2005 (GMT)
In my opinion there should be a constant list for the 'non-wrapping cell' implementations as well.. Should I add non-wrapping versions to this same list and just distinguish them by writing "Wrapping:" and "Non-wrapping:" or something like that? A new page might be better though, it would look more tidy.. User:Keymaker
- I can generate the non-wrapping versions with my program so you don't have to do them by hand. I think it will look fine on the same page because there will only be one entry per section.Calamari 07:16, 18 Jul 2005 (GMT)
- That's cool, thanks. I made them to about 30 and got tired and haven't made more. Good thing if your program can do the work.. And yeah, now when I think about it, it probably looks best if the both versions are on the same page.. User:Keymaker
I feel that there should be some indication of how many processor cycles each computation takes, so that the methods using the fewest processor cycles can be determined. User:Ravenswolf
- The fewest processer cycles would use the computations that would be just many '+' or '-' in a row.. (I think.) And generally brainfuck programs are made as small as possible, thus probably only the shortest, "many" processor cycles requiring computations would be used anyways. User:Keymaker
Why is it that starting from value 94, a series of 94 + symbols is posted, while for constants below 94 this isn't done? (e.g. constant 93 has no series of 93 + symbols). This seems so weird and inconsistent to me, unless I missed something.--Aardwolf 10:54, 6 Sep 2005 (GMT)
- I agree. I really don't see why they are included at all. --Rune 12:10, 6 Sep 2005 (GMT)
Cleanup mistake
Looks like you made an editing error of some sort under 52. I'm not sure what the intent was, so I'm leaving that as is. --Graue 05:37, 20 Jul 2005 (GMT)
- Didn't see anything under 57, but removed the cycle count I'd accidentally left in 52.Calamari 18:58, 20 Jul 2005 (GMT)
- Graue: You could have just said "oops", rather than editing your original from 57 to 52... ;) Calamari 17:42, 21 Jul 2005 (GMT)
- This is a wiki, isn't it? --Graue 20:03, 21 Jul 2005 (GMT)
alternatives to wrapping
Since many BF interpreters/compilers use 16 or 32 bits per cell, maybe it would be more useful to distinguish the solutions by cell size rather than only by "(non-)wrapping". That would leave room to include wrapping solutions for 16 bit cells (presumably only ever useful for larger numbers), and reduce the need to refer to the intro paragraph when trying to understand examples later in the page.
I'm imagining something like (for 34):
+++++[>+++++++<-]>- (19, 2) --[>--<+++++++]>-- (18, 2, 8 bit only) --[>++<-------]>-- (18, 2, 8 bit only) ++[>--<-------]>-- (18, 2, 8 bit only) ++[>++<+++++++]>-- (18, 2, 8 bit only)
Is it also worth adding some generic calculation? Ie:
- To construct a constant by multiplying n numbers whose absolute values sum to S requires S+6(n-1) instructions, or S+7(n-1) if the constant must end up at the starting memory location.
Hv 10:42, 28 Mar 2006 (GMT)
Is the TOC working for you? I used Opera and Internet Explorer and clicking on link in TOC got me nowhere.. It's doing since this edit: 12:27, 21 Jul 2005 Tokigun m (simplify table of contents) Maybe error occured somewhere... Since i'm not a HTML wizard, I'm not perfectly sure, but I want to point this out: In each entry there this following anchor code: <a name="20_20"></a> (for 20). In the simplified TOC there is link to #200. It should be 200_200... 195.28.142.198 07:48, 7 Jun 2006 (UTC)
OK, I edited it, but I can't upload edited TOC back. If somebody wants to do it him/herself, I have uploaded the edited page here.
Mistakes?
The entry for 255,
+>+>+>+>+>+>+>+>+[[[-<++>]<<]>]> (32, 10)
does not work. Here's a fixed version:
+>+>+>+>+>+>+>+[>[-<++>]<<]> (28, 10)
It requires a zero cell to the left of the number, so remember to precede the code with ">" if starting it at cell 0. --pgimeno 21:51, 26 Jul 2006 (UTC)
- Man, that's a clever piece of brainfuck code -- never thought of that! :) --Keymaker 09:17, 27 Jul 2006 (UTC)
Cleanup
I hope it will be easier to edit the article page now. By the way, as I discovered a bit late, if there is no introduction section, you can edit just the beginning with the following link: http:/wiki/Brainfuck_constants&action=edit§ion=0. --Ørjan 04:37, 11 Oct 2006 (UTC)
Pathfinder
I wrote a little ditty called pathfinder to find the shortest brainfuck command to a certain number. It works currently with non-wrapping 1, 2, 3 and 4 cell output. It only knows one format though (which is sad).
Output for 46145, in my interpreter it produces 65, which is correct.
+++[>+++++++[>+++++++++++++[>+++++++++++++[>+++++++++++++<-]<-]<-]<-]>>>>++++++++ (81,4) non-wrapping
If anyone can come up with a recursive or nested loop method of determining a wrapping value, that would be cool.
-Acyd
121, 156 & 255
On 29 June 2006, User W added code for 121, 156 and 255. They all begin with +>+>+> and they sure don't work for me. Am I missing something, or can they be removed? --Nthern 17:15, 20 August 2010 (UTC)
- The idea is interesting but the code is broken? I see you found (even shorter) repairs for 121 and 156, so I just removed the old ones. I added initial > because the codes need that cell. --Ørjan 06:32, 21 August 2010 (UTC)
- Well, the main page just says to list the code sequence along with the number of instructions and the number of cells taken. I guess I assumed that the instruction pointer should start and end on the cell with the final result. Are you saying that the instruction pointer should start at the leftmost cell of all the cells used, regardless of where the result ends up? If so, maybe that should be stated on the main page. --Nthern 13:56, 23 August 2010 (UTC)
- After thinking about this for a while, I propose the following: the canonical form is a sequence in which the instruction pointer (IP) starts and ends in the leftmost cell of all the cells used and the result ends up in that same cell with all other cells being 0. Other sequences may also be included. Sequences classes are
- Canonical form
- IP starts and ends on the result & all other cells are 0
- IP does not start and/or end on the result, but 0's are in all cells other than the result
- Some non-result cells are non-zero
- Sequences are ordered by non-wrapping vs. wrapping, then class, then sequence length, then number of cells used, then steps to complete the sequence. Each sequence is followed by
class (sequence length, cells used, steps to complete) { S ER 0 }
- Letters in the {} brackets stand for Start, End, and Result and other cells get a 0. If Start, End and Result are all on the same cell, replace SER with an X. So, the entry for 255 looks like:
+++++++[>++++++<-]>[<++++++>-]<+++ non-wrapping canonical (34, 2, 504) { X 0 }
>>++++++[<++++++[<+++++++>-]>-]<<+++ non-wrapping canonical (36, 3, 476) { X 0 0 }
>>+++++++[<++++++[<++++++>-]>-]<<+++ non-wrapping canonical (36, 3, 512) { X 0 0 }
>++++++++++++++++[<+++++++++++++++>-]<+++++++++++++++ non-wrapping canonical (53, 2, 338) { X 0 }
>++++++++[->[->++<]>+[-<+>]<<] non-wrapping class 2 (30, 3, 4074) { 0 X 0 }
+>+>++>+<[>[-<++++++>]<-<]>+++ non-wrapping class 2 (30, 5, 529) { 0 X 0 0 0 }
++++++++[->[->++<]>+[-<+>]<<] non-wrapping class 3 (29, 3, 4073) { S ER 0 }
- (1, 1) wrapping canonical (1, 1, 1) { X }
>- (2, 2) wrapping class 3 (2, 2, 2) { S ER }
- --Nthern 18:03, 23 August 2010 (UTC)
- Erm. I added the initial > on the intuition that otherwise the sequence is not a (non-crashing) standalone bf program. Also as I recall I've been assuming sequences to end on the result, but not necessarily to start there. For your notation I am not sure that putting the "class" designation in there is necessary, it follows from what's inside the {} brackets. I assume for class 4 you'd have some non-0 numbers there, potentially combined with S and/or E.
- I'll be reasonably happy as long as the format remains machine parsable (I've been extracting it before) and it isn't too hard to understand how to add new entries. Also I don't consider >- a useful entry because it is strictly "worse" than - in the combined partial order of all metrics. (I expect the current dataset has probably not been purged of all such redundancies.) --Ørjan 22:48, 23 August 2010 (UTC)
Quite a few of these don't work
These ones specifically:
67 +>+>+>++<[>[-<+++>]<<]> (23, 5) non-wrapping 76 +>+>++>++<[>[-<+++>]<<]> (24, 5) non-wrapping 79 +>+>++<[>[-<++++++>]<<]> (24, 4) non-wrapping 81 +>+>+++<[>[-<+++++>]<<]> (24, 4) non-wrapping 82 ++>+>+++<[>[-<+++++>]<<]> (25, 4) non-wrapping 83 +>+>+>+<[>[-<++++>]<<]>-- (25, 5) non-wrapping 84 +>+>+>+<[>[-<++++>]<<]>- (24, 5) non-wrapping 85 +>+>+>+<[>[-<++++>]<<]> (23, 5) non-wrapping 86 ++>+>+>+<[>[-<++++>]<<]> (24, 5) non-wrapping 87 +++>+>+>+<[>[-<++++>]<<]> (25, 5) non-wrapping 88 +>++>+>+<[>[-<++++>]<<]>- (25, 5) non-wrapping 89 +>++>+>+<[>[-<++++>]<<]> (24, 5) non-wrapping 90 ++>++>+>+<[>[-<++++>]<<]> (25, 5) non-wrapping 91 +++>++>+>+<[>[-<++++>]<<]> (26, 5) non-wrapping 92 ++++>++>+>+<[>[-<++++>]<<]> (27, 5) non-wrapping 93 +++++>++>+>+<[>[-<++++>]<<]> (28, 5) non-wrapping 93 +>+>+>+<[>[-<+++++>]<--<]>- (27, 5) non-wrapping 93 +>+++>+>+<[>[-<++++>]<<]> (25, 5) non-wrapping 94 +>+>+>+<[>[-<+++++>]<--<]> (26, 5) non-wrapping 94 +>+>+>+++<[>[-<+++>]<<]> (24, 5) non-wrapping 95 ++>+>+>+<[>[-<+++++>]<--<]> (27, 5) non-wrapping 95 ++>+>+>+++<[>[-<+++>]<<]> (25, 5) non-wrapping 97 +>++>+>+++<[>[-<+++>]<<]> (25, 5) non-wrapping 98 +>+>++>+<[>[-<++++>]<<]>--- (27, 5) non-wrapping 98 ++>++>+>+++<[>[-<+++>]<<]> (26, 5) non-wrapping 99 +>++>+>+<[>[-<+++++>]<--<]> (27, 5) non-wrapping 99 +>+>++>+<[>[-<++++>]<<]>-- (26, 5) non-wrapping 100 +>+>++>+<[>[-<++++>]<<]>- (25, 5) non-wrapping 101 +>+>++>+<[>[-<++++>]<<]> (24, 5) non-wrapping 102 ++>+>++>+<[>[-<++++>]<<]> (25, 5) non-wrapping 103 +++>+>++>+<[>[-<++++>]<<]> (26, 5) non-wrapping 103 +>+>++>+++<[>[-<+++>]<<]> (25, 5) non-wrapping 104 +>++>++>+<[>[-<++++>]<<]>- (26, 5) non-wrapping 105 +>++>++>+<[>[-<++++>]<<]> (25, 5) non-wrapping 106 ++>++>++>+<[>[-<++++>]<<]> (26, 5) non-wrapping 106 +>+>++++<[>[-<+++++>]<<]> (25, 5) non-wrapping 107 +++>++>++>+<[>[-<++++>]<<]> (27, 5) non-wrapping 115 +>+>+++<[>[-<++++++>]<<]> (25, 5) non-wrapping 125 +>+>+>+<[>[-<+++++>]<-<]> (25, 5) non-wrapping 149 +>+>+>++<[>[-<++++>]<<]> (24, 5) non-wrapping 161 +>++>+>+<[>[-<+++++>]<<]> (25, 5) non-wrapping 181 +>+>++>+<[>[-<+++++>]<<]> (25, 5) non-wrapping 182 ++>+>++>+<[>[-<+++++>]<<]> (26, 5) non-wrapping 183 +++>+>++>+<[>[-<+++++>]<<]> (27, 5) non-wrapping 213 +>+>+>+++<[>[-<++++>]<<]> (25, 5) non-wrapping 229 +>+>++>+++<[>[-<++++>]<<]> (26, 5) non-wrapping 255 +>+>+>+>+>+>+>+>+[[[-<++>]<<]>]> (32, 10) non-wrapping 255 +>++>+>++<[>[-<+++++>]<-<]> (27, 5) non-wrapping
07:44, 20 November 2011 (UTC) an anonymous brainfucker.
- The one for 67 works, I just verified myself. Are you sure there's not a bug in your interpreter? You'll have to provide some more detail. —ehird 08:13, 20 November 2011 (UTC)
Cell usage below 0
Should cell usage below 0 be allowed? (eg. -[>+[+<]>>]> for 240; although this can be changed to >-[>+[+<]>>]> so that no cells below zero are accessed) David.werecat (talk) 11:16, 28 June 2012 (UTC)
- There are already old solutions starting with
>, so I'd say custom is that it's not allowed, as otherwise those would be redundant. --Ørjan (talk) 11:27, 28 June 2012 (UTC)
- It makes sense in terms of 'you can safely use them anywhere', yes. Although the wikipage did not say anything about that so I presumed wrapping also includes tape wrapping. -- Feuermonster (talk) 11:42, 28 June 2012 (UTC)
- Ok. I will recheck every solution and add as many '>' to the start as required. If the solution is still shorter that way we can keep it, else i'll remove it. -- Feuermonster (talk) 11:55, 28 June 2012 (UTC)
Added an Algorithm to THIS page
I've added it here because it's not a 'brainfuck' algorithm, but instead is one for a brainfuck generator (either manually or with a program) and so (IMO) does not fit on the Brainfuck algorithms page.
I note that the 333 value is actually one that may have been generated by this algorithm.
I've added it as an algorithm because I don't really want to add 4 billion strings to this page ... or is that infinity :-0 :-) Rdebath (talk) 10:50, 23 December 2013 (UTC)
Wrapping vs non-wrapping
Okay, I need a definition. I thought that "wrapping" basically meant that the value in the cell was incremented or decremented past the max/min and came back to zero. If it doesn't get back to zero it's just an overflow not a wrap and so meaningless in general because it's not possible to identify if a BF implementation uses signed or unsigned cells from inside BF.
But apparently this is supposed to be wrapping, and it doesn't even have to overflow:
>+>+>++>++>++>->+++[>[<+++++>-]<<]>[<+>-]<
It (obviously) uses a negative cell but does run successfully on a plain bignum implementation and similar signed non-wrapping implementations.
Is it actually defined to be wrapping or just a (minor) mistake ? Rdebath (talk) 09:04, 25 December 2013 (UTC)
- You're right. My mistake. I was confusing myself because it is possible for this representation to require a wrapping implementation for *some* numbers and bases. In particular, if the last digit is negative, it will enter an infinite loop on non-wrapping implementations. In short, it's only a coincidence that 45306 in balanced pental works in a nonwrapping implementation. --Quintopia (talk) 14:22, 25 December 2013 (UTC)
- I take back most of the above. the MSB will always be positive in a positive number, so it will always terminate in a non-wrapping implementation. Page updated to reflect this fact.--Quintopia (talk) 15:13, 25 December 2013 (UTC)
Note on crunchfuck and more values.
Result: 208 == +[+++++>-<]>+++ (15, 2, 465) Result: 208 == +[++++>-<+]>+++ (15, 2, 465) Result: 208 == +[+++>-<++]>+++ (15, 2, 465) Result: 208 == +[++>-<+++]>+++ (15, 2, 465) Result: 208 == +[+>-<++++]>+++ (15, 2, 465) Result: 208 == +[----->+<]>+++ (15, 2, 1851) Result: 208 == +[---->+<-]>+++ (15, 2, 1851) Result: 208 == +[--->+<--]>+++ (15, 2, 1851) Result: 208 == +[-->+<---]>+++ (15, 2, 1851) Result: 208 == +[->+<----]>+++ (15, 2, 1851) Result: 208 == +[->-[-<]>-]>-- (15, 5, 3454) Result: 208 == +[-[-<]>>----]< (15, 4, 654) Result: 208 == +[>+<-----]>+++ (15, 2, 1851) Result: 208 == +[>-<+++++]>+++ (15, 2, 465) Result: 208 == -[+++++>+<]>+++ (15, 2, 1851) Result: 208 == -[++++>+<+]>+++ (15, 2, 1851) Result: 208 == -[+++>+<++]>+++ (15, 2, 1851) Result: 208 == -[++>+<+++]>+++ (15, 2, 1851) Result: 208 == -[+>+<++++]>+++ (15, 2, 1851) Result: 208 == -[+[++<]>>++]<- (15, 4, 1552) Result: 208 == -[----->-<]>+++ (15, 2, 465) Result: 208 == -[---->-<-]>+++ (15, 2, 465) Result: 208 == -[--->-<--]>+++ (15, 2, 465) Result: 208 == -[-->-<---]>+++ (15, 2, 465) Result: 208 == -[->-<----]>+++ (15, 2, 465) Result: 208 == -[>+<+++++]>+++ (15, 2, 1851) Result: 208 == -[>-<-----]>+++ (15, 2, 465) Result: 208 == >+[+[++<]>>++]< (15, 3, 1545) Result: 208 == >+[+[++>]<<++]> (15, 3, 1545)
These are and many other sequences are in https://github.com/rdebath/crunchingbrains Rdebath (talk) 18:42, 16 September 2016 (UTC)
Updates to non-wrapping solutions
I recently discovered that the Power Series could be improved by moving the most significant value forward, just before the inner loop. Not only does this utilize one less cell, but it can often result in shorter programs. A good example of this is for 105:
>+>++>++>+[>[-<++++>]<<]> (25, 6) non-wrapping >+>+>+[>+[-<++++>]<<]> (22, 5) non-wrapping
The first value is moved forward, and the second and third are both decreased by the same amount. The last value remains as it was, as it doesn't ever reach the inner loop. I went through and cruched all values, keeping the best non-wrapping and soft-wrapping solutions. Many values had multiple equal length solutions, so to be objective, I used the following criteria:
- Prefer shorter solutions.
- Prefer solutions that utilize less cells.
- Prefer solutions that begin with
>. Rationale: depending on use case, may not be necessary. - Prefer solutions that end with
>or<. Rationale: may not be necessary, and also results in a large number of unique solutions (rather than just +/- neighboring entries). - All other things being equal, prefer solutions with fewer executed commands (i.e. faster solutions).
I obsoleted solutions only if they were strictly improved upon by length or by cell usage. There are, however, some previously existing solutions that do seem somewhat redundant, for example 115:
>+>+>+++<[>[-<++++++>]<<]> (26, 4) non-wrapping (previously existing) >+>+>+++[>[-<++++++>]<<]> (25, 5) non-wrapping (new)
Moving back one cell before the main loop uses one less cell, at the cost of one byte. I'm not convinced that keeping both solutions is necessary, though. Another case is for 106:
>+>+>++++<[>[-<+++++>]<<]> (26, 4) non-wrapping (previously existing) >++>+>+[>+[-<++++>]<<]> (23, 5) non-wrapping (new)
Although the first solution is different than the second, it could also be written one byte shorter as >+>+>++++[>[-<+++++>]<<]> (25, 5) non-wrapping, in which case it should be obsolete. Similarly redundant solutions are present for 106, 115, 149, 156, 161, 181, 202, 213, and 229. Most of these were obsoleted, only 115 and 149 remained optimal.
While I was at it, I decided to crunch the optimal 3-cell solutions for each value as well. These take two forms: a single cell initialization working rightwards, or a 3-cell initialization working leftwards. As an example, the following both produce 216:
++[->+++[->++<]>[-<++++>]<<]> >+>+++[-<[-<++>]<[->+++<]>>]<
The second one being preferred, due to starting with >. Previously, it seems that only the second of these were crunched, which I think is why many of them were missed.
I've also confirmed that the 2-cell solutions are optimal in length, although some could be improved according to the criteria above, for example 68 as ++++[->++++<]>+[-<++++>]< (17 x 4) rather than ++++++[>+++++++++++<-]>++ (6 x 11 + 2). I didn't actually update any of these, though. --Primo (talk) 08:04, 17 May 2017 (UTC)
How are we supposed to use numbers more than 255 in brainfuck?
Usually, we run brainfuck with a tape with 8 bit cells, however, the article introduces methods to store numbers over 255 (e.g. 45306). --None1 (talk) 10:42, 7 August 2023 (UTC)
- Either an interpreter that has larger cells or Brainfuck bitwidth conversions Rdebath (talk) 15:10, 29 April 2024 (UTC)