LearnBuild toward a chatbotObstacle 2: two numbers from the tape
Obstacle 2: two numbers from the tape
Aim. At the end of this lesson your program multiplies −25 by −60 with both numbers on the tape, in under 60 steps.
Where the lessons are going
In lesson 3 the weight stood in the program, as plus signs. But a model also multiplies two numbers that only appear while it runs, and then neither of them can be written into the program.
The obvious way: a loop inside a loop
Try it: a is 6 and b is 7, both on the tape. Go to the last step. Then start again and step through a few rounds to see how it works:
What you just saw
For every unit of a, the program added a full copy of b to the total. Six rounds of 7 make 42. Each round is a small loop of its own: a loop inside a loop.
That is five steps a round. For a = 6 it is nothing.
Now with a number below zero
Try it: the sum has the product −25 × −60. Set a to −25 and b to −60, go to the last step and read how many steps it took:
What you just saw
The answer is right: 1,500. The cost is absurd: 327,557 steps.
A cell cannot hold −25. It holds "25 below the top", which is 65,511 on the cells of this demo. The loop does not know that this means −25. It runs 65,511 rounds, and the total goes round and round and lands on the right number.
The cells of the chat program are much larger. There −25 is 4,294,967,271, and this loop would take about 21 billion steps (worked out, not run: 5 steps a round). The whole chat program spends 1.6 to 1.9 billion steps on a word piece.
The way out, by hand
Try it: these are the bits of a = −25. Press every bit that is on. Each press adds b times the worth of that bit to the total:
b = −60. The leftmost bit counts as −128.
Total: 0
What you just saw
Six presses, and the total is 1,500. This is multiplying the way you do it on paper, with bits in place of digits. It is called shift and add.
Each part is something you already have. Which bits of a are on: that is the peel of step 3 of lesson 5. "b times 4" is multiplying by a fixed number: one step (step 3 of lesson 3).
The leftmost bit of a number that may be negative counts as −128. Nothing more is needed for numbers below zero.
The same, as a program
Try it: go to the last step and compare the number of steps with the 327,557 of step 2:
| −25 × −60 | Steps |
|---|---|
| Loop inside a loop, cells of this demo (16 bits) | |
| Loop inside a loop, cells of the chat program (32 bits) | |
| Shift and add, cells of the chat program |
Measured here, except the row marked "worked out".
What you just saw
The cost no longer depends on how large the numbers are, or on their sign. It depends on how many bits a has (eight here) and how many of them are on.
In the chat program one such product went from about 195,000 steps to about 43.
What you can do now
Multiply any two numbers from the tape, below zero or not, for a few dozen steps. Every product of the sum can now be made, wherever its numbers come from. The second obstacle is gone.
How the real program differs
When the plain loop wins. For a very small a that is not below zero, a few rounds are cheaper than reading eight bits. But the program is written before the numbers are known. Shift and add costs about the same every time, so it is the safe choice wherever numbers can be large or negative.
A bonus. Peeling a is most of the work. When the same a must be multiplied by many different numbers, a is peeled once, and every extra product costs only a step or two for each bit that is on. The chat program uses exactly that for its scores: see the note "Where the scores come from" of lesson 10.
The 21 billion of step 2. 4,294,967,271 rounds of 5 steps. The 5 steps a round were measured on the smaller cells; the large case was not run.