I should note that fib.b was the first nontrivial brainfuck program I wrote, in 2001 I think, and this version is very close to that one.
This program computes Fibonacci numbers (https://oeis.org/A000045). Because these numbers grow very large, it takes multiple cells to store each one. I wanted to output the numbers in decimal, so it seemed easiest to store one decimal digit per cell.
Cell size varies enough among brainfuck implementations that I generally avoid relying on it, for portability. (Even where cells are large, putting large values in them tends to be horribly slow anyway.)
The algorithm is fairly simple: keep the last two numbers computed (call them A and B). Output the last number (B), then replace A with B while replacing B with the sum A+B, then repeat. The question then is how to represent these values in brainfuck's memory. On paper, adding 6765 to 10946 would use four rows:
111 (carries)
6765 (A)
+10946 (B)
17711 (sum)
We need to squeeze this into one dimension to fit in the brainfuck array. We could do something like
1 1 1
6 7 6 5
1 0 9 4 6
1 7 7 1 1
1 1 1 0 6 7 6 5 1 0 9 4 6 1 7 7 1 1
C C C C A A A A B B B B B S S S S S
but it ends up being much better to interleave the numbers, more like
1 1 1
6 7 6 5
1 0 9 4 6
1 7 7 1 1
0 0 1 1 1 6 0 7 1 7 9 7 1 6 4 1 0 5 6 1 0 0 0 0 ...
C A B S C A B S C A B S C A B S C A B S C A B S ...
partly because this puts corresponding digits of the different numbers a small and uniform distance apart, and also because this way, as the numbers grow, they don't bump into each other, or need to be moved out of each other's way: each number has 1/4 of the array reserved for itself. So we split the brainfuck array conceptually into parallel arrays, one for each row; the sum A+B would go in the cells marked S in this diagram, and so on. This basic technique will be useful in many future programs.
This arrangement wants more tweaking for the Fibonacci program, though. Because numbers (as usually written) grow to the left and the brainfuck array is unbounded to the right, it makes most sense to store the numbers backward (most significant digit to the right), so they can grow rightward into the available space. This means outputting B from right to left, and then updating A and B from left to right, carrying 1s to the right as needed.
Another question comes up here: how to tell where a number ends? How to tell the difference between a 0 digit in the middle of a number, and a 0 that's empty space past the end of the number? Several solutions are possible; The answer I hit on for this program was to add one more row of cells to show the length of the longest number present; these cells will be 1 for the whole length of the number, or 0 for blank space outside the number. We don't need two separate length markers, because A and B are always within one digit of the same length, so treating them as the same length is like adding a harmless leading 0 digit to A whenever it's shorter.
So that would have meant splitting the brainfuck array into fifths. But in fact, it ended up being possible to split it only into thirds. We don't need a whole row for the carries; I found that they can just be added directly into the applicable A cells. And we don't need a separate row for the sum: because we plan to have the sum replace B, and we're computing the sum one digit at a time, we can put each digit of the sum straight into the appropriate B cell, and move that digit of B into the matching A cell. That is, we can update A and B one digit at a time; we never need to store the whole of all three numbers (A, B, and A+B) at the same time. We do need extra cells to use for calculation, but we can reuse the length-marker cells for this purpose. I ended up calling those T cells because they're used as (T)emporary variables.
The memory layout I actually ended up using, then, is like this (just before adding 6765 and 10946):
5 6 7 6 (A)
6 4 9 0 1 (B)
0 1 1 1 1 1 0 0 (length marker)
5 1 6 6 1 4 7 1 9 6 1 0 0 1 1 0 0 0 0 0 0 ...
0 10 A T B A T B A T B A T B A T B A T B A T B ...
That 10 in the second cell is to output as a linefeed after each number.
At this point, outputting the number is easy. For each T cell that's 1, from right to left, increase the matching B cell by 48 (the ASCII value of the '0' character), output it, and decrease it by 48 again. Adding digits is easy too; the part I found hard was figuring out how to do the carries, breaking "15" into "5, carry the 1". The solution I found for this program was basically a switch/case statement: a set of nested loops that peel off one case at a time. For all cases where the sum is less than 10, we skip past the innermost loops that carry the 1. This is not the most concise solution possible, though it may be the quickest.]
>++++++++++>+>+ Initialize: linefeed=10, A=1, T=1, B=0.
[ Main loop: each iteration outputs one Fibonacci number from B and computes the next one (A+B).
[ Output loop: outputs one digit per iteration
+++++[>++++++++<-] Increase B digit by 48 for visible output (ASCII codes for the visible digit characters '0' through '9' are 48 through 57)
>.< Output ASCII for this digit of B.
++++++[>--------<-] Decrease B by 48 to restore it to range 0-9.
+<<< Restore T=1, and go left to the next T marker, if any.
] End of output loop; go back to output next digit, or exit.
>.>> All digits of B have been output. Output linefeed (ASCII code 10) and go back to the leftmost T marker.
[ Update loop: each iteration updates one digit of A and B (setting A to B and B to A+B, with carries)
[-] Clear T to 0 (it was either 1 or 2 before)
<[>+<-] Move this digit of A to empty T cell for the moment.
>>[<<+>+>-] Set A cell = B, and T cell = (A+B) (may exceed 9 now, so we may need to carry a 1 next).
<[>+<-[>+<-[>+<-[>+<-[>+<-[ Start moving sum from T cell to B cell gradually. (If sum was 0-5 we skip forward as soon as we finish moving it.)
>+<-[>+<-[>+<-[>+<- Continue moving sum if it was greater than 5 (this line is cases 6-9).
[ We enter this loop if sum exceeded 9, so we need to carry a 1.
>[-] Set B cell = 0 (last digit of "10"; this is case 10).
>+ Add 1 to the next digit of A (this is a way to carry a 1 into the next digit of the sum, because in the next iteration of the update loop, that digit of A will go into the sum, but will not persist apart from that).
>+ Add 1 to the next T marker to ensure it's nonzero, so the update loop will be executed at least once more. (The next T might have been zero if this sum is longer than the old B, and this is the last carry which lengthens B. A+B is one digit longer than B every 4th or 5th Fibonacci number.)
<<<- Decrease the current T by the 1 we just added to the sum. (We're still moving the sum from T cell to B cell gradually; this long case just changed "9" into "10", carrying a 1.)
[>+<-] Move the rest of the sum from T cell to B cell. (If sum was 11-19, this sets B cell = 1-9 to match, storing the sum's second digit in B cell by running this loop 1-9 times. This handles cases 11-19.)
]]]]]]]]]] Ends of skip loops for cases where sum was 0-9 and we skipped doing the carry
+>>> Restore marker T=1 and go to next T marker, if any, to update next digit of A and B.
] End of update loop; go back to loop start and update next digit, or exit loop when all digits have been updated.
<<< Done updating. New sum A+B is in B cells, previous B value is in A cells now. Go back to rightmost T marker.
] End of main loop, which never terminates; go back to start of main loop and output the new sum.
This program showed me:
-That handling variable-sized data is necessary and not too hard
-Breadcrumb technique for scanning through data with [>>>] (optionally doing more things at each cell, as in this case)
-Interleaved storage technique for giving several numbers (or whatever) their own space without their getting in each other's way
-Don't keep data around longer than you need it. (heuristic)
-Keep written maps of the memory layout at different times; brainfuck is less self-documenting than most languages, so your code alone isn't enough.
(In this case the maps for the update loop might look something like this:
0 10 a t' b a t b 0 0 0
0 10 a' 0 b a t b 0 0 0
0 10 0 a b' a t b 0 0 0
0 10 b c' 0 a t b 0 0 0
0 10 b 0' c a t b 0 0 0
0 10 b t c a t' b 0 0 0
I often keep these maps with pen and paper.)
-Case statement technique (which I next used for a verbose ROT13 program)
-To consider reversing reversible transformations rather than making temporary copies of values. x+48-48=x.
-That a brainfuck program needn't be terribly slow or complicated. (This one executes <450 commands per character of output. The operations are O(log n) in the numbers involved, which is optimal.)