LearnBuild toward a chatbotThe way through: peeling off bits
The way through: peeling off bits
Aim. At the end of this lesson your program divides 11,868 by 128, rounds it and keeps it within limits, in about 120 steps. In step 3 of lesson 4 that took 131,538.
Where the lessons are going
Counting costs a step for every unit of a number, so the division of the sum is stuck. The way out starts with something from step 7 of lesson 1: a cell that is full goes round to zero.
Push a number out of its cell
Try it: the cell holds 44, drawn as a row of eight switches. Press Double until the cell holds zero, and watch the switches:
What you just saw
Inside a cell a number is a row of switches that are on (1) or off (0). This cell has eight. They are worth 128, 64, 32, 16, 8, 4, 2 and 1, and the number is the worth of the "on" switches added up: 32 + 8 + 4 = 44. Such a switch is called a bit.
Doubling moves every bit one place to the left. The leftmost one has nowhere to go and falls off. That is the going round of step 7 of lesson 1, seen from the inside.
A question about one bit
Try it: press the bits to make a number that is zero after exactly three doublings, not sooner. Then press Double three times:
What you just saw
Three doublings push out the bits worth 128, 64 and 32. Your number was gone exactly then, so every bit below 32 was off, and the one worth 32 was on.
"Is the cell zero after three doublings?" is a question about particular bits. It is made from the only question brainfuck has, "is this cell zero?" (step 4 of lesson 1).
And it is cheap. Doubling three times is multiplying by 8: one loop, one step (step 3 of lesson 3).
Read a whole number, bit by bit
Try it: the number is 93. Press Play, or go to the last step. Then compare the cells called "bit" with the switches above the program:
What you just saw
The program found every bit of the number without counting it down. For each bit it did three things. It made a copy of the number and doubled it as often as needed (one step). It asked "zero?" (one step). And if the bit was on, it took that bit out of the number (a few steps).
This is called peeling: taking the bits off one at a time, the lowest first. The cost depends on how many bits a number has, not on how large it is.
Dividing by 128 without counting
128 is seven doublings, so dividing by 128 means throwing away the lowest seven bits. To round at the same time, add 64 first. Drag the number and watch which bits are kept:
The bits are worked out in this page, not by a brainfuck program. The next step runs the real one.
Notice that the kept bits are always the number divided by 128 and rounded, and that they only change when the number has moved on by a whole 128. Throwing bits away is how a program divides without counting.
Counting against peeling
Try it: press "Run both" for 11,868. Then make the number ten times as large and run both again:
| Divide by 128 and round | Answer | Steps |
|---|---|---|
| By counting (step 3 of lesson 4) | – | – |
| By peeling | – | – |
What you just saw
Ten times the number: counting takes ten times as long. Peeling takes a few steps more, because the number has three or four more bits.
Dividing by 128 is easy once you can see the bits: throw away the lowest seven and keep the rest. To round, add 64 first.
In the chat program, divide, round and keep within limits went from 1.2 to 1.5 million steps by counting (step 4 of lesson 4) to about 100 by peeling.
Keep it within limits
Try it: drag the sum upward until the result stops growing:
| Divided by 128 and rounded | |
| Result of the brainfuck program | |
| Steps |
What you just saw
The result may not go above 127 or below −128. Whatever is larger is cut off. This is called clamping. It keeps every number of the model small, so that the next multiplication stays cheap.
The program does not compare with 127. It cannot. It peels the bits it needs and then asks once: is anything left above them? If so, the number was too large.
This is the second part of the sum: 11,868 becomes 93.
What you can do now
Divide, round and clamp, at a cost of about a hundred steps whatever the number. With that, comparing is solved too: subtract, and look at one bit. The first obstacle is gone.
How the real program differs
The peel of step 3 for your number, bit by bit: start with the lowest bit and double the number 7 times, so that only the lowest bit can survive. Zero or not? If the bit was on, take it out. Then the next bit, with 6 doublings, and so on. The table shows it for the number of step 3.
Two honest notes. Peeling leans on "a multiplying loop is one step" (step 3 of lesson 3). Done one command at a time, a single doubling loop on a large cell would run for millions of rounds, so the real program needs a fast interpreter. And the program text depends on the size of the cells: the chat program is written for cells of 32 bits and gives nonsense on cells of 8 bits.
The same peel makes other things. Looking a value up in a list of 256 ready-made answers takes about 68 steps, against about 500 by counting. Step 2 of lesson 10 uses that.