Big numbers in BF

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:

• When started, all memory cells have the value zero, and the memory pointer points to the first memory cell. (This is a usual assumption for BF programs in general.)
• It will not move the memory pointer before the first memory cell.
• It will not store any negative number in any of the memory cells.
• When it terminates, the first memory cell contains the value n, and all other memory cells are zero (again).
• When it terminates, the memory pointer, points to the first cell again.

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

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 substracting) program by surrounding it with '>' and '[<s>-]<', where s equal the "+" symbol for an adding program, and the "-" symbol for a substracting 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 more bigger 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 onJanuary 24, 1999.

Largest number for a given length

Busy Beaver Turing Machines