LearnBuild toward a chatbotObstacle 1: only one question
Obstacle 1: only one question
Aim. At the end of this lesson you have felt, in the step counter, why the obvious way to compare and to divide cannot work for a model.
Where the lessons are going
The sum is made: 11,868. The next part divides it by 128 and rounds. Multiplying was cheap. This is not, because a brainfuck program can ask only one question: is this cell zero?
Which one is bigger?
Try it: two cells, a holds 5 and b holds 3. Press Play, or Step, until the program has ended. How does it find out which is bigger?
What you just saw
There is no "bigger than" command. So the program took 1 from both numbers, again and again, until one of them was empty. What is left tells which was bigger, and by how much.
Every round it had to ask "is a empty yet?" without destroying a. So it first made a copy (step 2 of lesson 2) and tested the copy. That is about eleven steps a round.
The same, with bigger numbers
Try it: make both numbers large, a near 1000 and b near 900. Go to the last step and read how many steps it took:
What you just saw
The answer is right. But 5 against 3 took 34 steps, and 1000 against 900 took about ten thousand.
There is one round for every unit of the smaller number. The cost does not depend on how many numbers you compare. It depends on how large they are.
Divide 11,868 by 128
Try it: the slider stands at 11,868, the number from the sum. Drag it all the way to the right and watch the steps:
| Answer of the brainfuck program (divided by 128, rounded) | |
| Steps | |
| Steps for each unit of the number |
What you just saw
Dividing by counting: take 1 from the number, and every 128th time add 1 to the answer. For 11,868 the answer is 93, which is right.
It took 131,538 steps. About eleven for every unit of the number: twice the number, twice the steps.
How bad does it get?
Try it: now take a much larger number, 1,000,000. How many steps will dividing it take? Work it out from the table of step 3, type your estimate and check:
Hint
The table in step 3 shows the steps for each unit of the number. Multiply that by 1,000,000.
What you just saw
Your browser just did about eleven million steps for one division.
The chat program was measured on the same thing. One "divide, round and keep within limits" took 1.2 to 1.5 million steps by counting, and a model does one of those for every number it works out. With counting, a real model is out of reach.
What you can do now
Nothing new, and that is the point. You can compare and divide, but only by counting, and counting costs a step for every unit. The second part of the sum, 11,868 divided by 128, costs 131,538 steps this way.
Why a fast interpreter does not save it
The multiplying loop of step 3 of lesson 3 only adds and moves, so a fast interpreter does it in one step. A counting division has a question inside every round ("is this the 128th time?"), and a question is a loop of its own. The fast interpreter has to go through every round.
A model has to do three things of this kind all the time: divide, round, and cut a number off at a lowest and a highest value. All three are comparisons in disguise.