Large numbers in BF

BF does not have numerical constants as basic language elements, but it does have an increment operator. This means that all constants can be made by incrementing. The program fragment `+++' adds 3 to the current cell. However for large constants, this becomes rather cumbersome. This raises the question: which is the shortest program fragment to make, for example, the number 1643? Or, the opposite question: which is the largest number that can be calculated by a BF program consisting of 55 characters?

But, before we can ask ourselves these kind of questions, we have to define, what we consider as a constant number BF program, or for short, a CNBF program. We define a CNBF(n) program as follows:

It is rather obvious that the BF program consisting of n times a '+' symbols is a CNBF(n) program. The rather trivial conclusion from this is that at the shortest CNBF(n) program is at most n characters long, and that the largest number which can be calculated with a program of l characters is at least l.

As a convenience, we define SCNBF(n) to represent the length of the shortest CNBF(n) program, and LCNBF(l) as the largest number that can be calculated with a CNBF program consisting of l characters. Using these definitions, the above conclusions can be stated as: SCNBF(n) <= n and LCNBF(l) >= l.

Of course, there are better ways to make numeric constants than using only '+' symbols. For example, the following BF program calculates the value 30 by multiplying 6 with 5: >++++++[<+++++>-]<. This program only uses 6 + 5 + 7 = 18 characters. From this, we can simply conclude that SCNBF(n*m) <= n + m + 7. Note however, that the sequence '++++++' is a CNBF(6) program. The first sequence of '+' symbols in this kind of program can be substituted by a CNBF program. From this we can conclude that SCNBF(n*m) <= SCNBF(n) + m + 7. Thus SCNBF(210) <= SCNBF(30) + 7 + 7 <= 18 + 7 + 7 = 32. Of course, the second sequence of '+' symbols cannot be replaced by any CNBF program.

Now, how for calculating the number 211. 211 is simply 210 plus one. By simply adding a '+' behind the program for calculating 210, we get the program for calculating 31. Actually, all the CNBF programs we have see so far, add some number to the value in first memory cell. We could also call these `constant adding BF program', or CABF. Likewise, we could also define SCABF(n) and LCNBF(l). From what we have seen we could conclude that SCABF(n) <= SCNBF(n). The general conclusion we can draw is that SCNBF(a+b) <= SCNBF(a) + SCABF(b), and SCABF(a+b) <= SCABF(a) + SCABF(b).

And now for the number 209? That can be made by adding a '-' behind the program for calculating 210. All CABF programs can be changed into 'constant subtracting BF programs' (or CSBF) by changing all '+' working on the first memory cell into '-', and vice versa. Of course, SCSBF(n) is equal to SCABF(n) for all n. The general conclusion we can draw is that SCNBF(a-b) <= SCNBF(a) + SCABF(b), and SCABF(a-b) <= SCABF(a) + SCABF(b).

The next more power full method for generating large numbers, is using powers. Raising a number to a certain power is simply repeated multiplication. That means we have to create a loop, in which a number is multiplied with a constant for a number of times. So for the number 1024 the following BF program (with comments) will work:

  +              'store one in 1st memory location
  >>++++++++++   'store ten in 3rd memory location
  [ <<           'start of power loop
    [>++<-]      'the 2nd memory location is filled with the double of the 1st
    [<+>-]       'move the value from the 2nd back to the 1st memory location
  <<             '1st memory location contains 2 to the power 10
If you want to check this, just cut-and-past this fragment in the "Enter your BF progam" field of the BF online page, and press the "CN-execute" or "CN-execute-trace" button, and read the result in the field below the buttons. You do not need to worry about the comments.

So the general form is of the power loop is something like '>>p[<<[>a<-]>[<b-]>-]<<', where p, a, and b stand for a number of "+" symbols. The power loop multiplies the existing number in the first memory location with (a*b)^p. From this we can conclude that SCNBF(x*(a*b)^p) <= 21 + a + b + SCNBF(p) + SCNBF(x).

Note that the power loop is not a constant adding BF program as the the first location is multiplied with something. However, it can be made into a constant adding (or subtracting) program by surrounding it with '>' and '[<s>-]<', where s equal the "+" symbol for an adding program, and the "-" symbol for a subtracting program. From this we can conclude that SCABF(n) = SCSBF(n) <= SCNBF(n) + 8.

Although the power loop is rather powerfull in producing short BF programs which produce large numbers, it is only usefull for large numbers (and its close neighbours) which can be written in the form of x*(a*b)^p. However, there is a variation (or extenstion) to the power loop, which overcomes this limitation. These are the power loops of the form '>>p[<<k[>a<-]>l[<b-]>-]<<', in which l and k also represent a sequence of "+" symbols. This extended power loop multiplies the existing number in the first memory location with f(a,b,l,k,p), which equals (a*b)^p + (k*a+l)*b*(sum (a*b)^i for i=0..(p-1)). From this we can conclude that SCNBF(x*f(a,b,l,k,p)) <= 21 + a + b + l + k + SCNBF(p) + SCNBF(x).

The next step for even larger number is where we put a loop around the power loop. The most simple form of this, is where you repeat the assignment v := v*2^v a number of times, starting with v=1. If you apply the statement once, you get the number 2. Not very impressive. If you repeat it again, you get 2*2^2, which is 8. The third we finally starting to get somewhere, with the number 8*2^8, which equals to 2048. But after this it goes up very fast! The next number will be 2048*2^2048, a number with 622 digits. For the program that uses this principle, see what I wrote on January 24, 1999.

On April 15, 2009, I found another, possible better way, of generating large numbers.

Largest number for a given length

Below the table of BF programs of a given length that will produce the largest possible constant number.



If you want to try something yourself, have a look at: How to do arithmetics in BrainFuck?

Busy Beaver Turing Machines

There is some relation between the problem of generating large numbers in small BF programs, and the Busy Beaver Turing Machines.

About BF | home and email