Code patternsAdvanced: wrapping cells of a known widthTable lookup as a decision tree
Table lookup as a decision tree
Gives entry number x of a fixed table, in a number of steps that depends on the size of the table and not on x.
Watch it run
The form “A table of squares” works on 11 cells; the named ones are “x” and “y”. Press Play, drag the step slider forwards and back, or change x with the slider and edit the choice of entries:
The figure needs JavaScript. The program below is the result for the example values.
The table is not on the tape. It is in the program text, as a tree of if and else: first "is bit 0 of x set?", inside each answer "is bit 1 set?", and so on. At the end of each path one entry is added to the result.
The questions are the tests of the bit peel, so no bit is ever stored. A table of 256 entries is 8 questions deep: about 70 steps.
The price is length. Every entry has its own path in the text. The table of 16 squares here is about 4,000 characters; with 256 entries it is 134,000.
The code
This is the program the figure ran, written by the generators for these values and this cell size. It is brainfuck as it stands: copy it, or open it in the playground, where you can change it:
[->>>>>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>>>+<<<<<<<<<<]>>>>>[->++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<]>[-<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>]<[-<<<++++++++++++++++>>>]>>>>>[-<<<<<<<<<<+>>>>>>>>>>]<<<<<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++[->++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<]>[-<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>]<[->>++++++++++++++++<<]<<<[->+>++++++++<<]>>>>>>>+<<<<<[[-]>>>>>-<<[-<<<<->>>>>+<]>[-<+>]<<<<<[-<+>>++++<]>>>>>>+<<<<<[[-]>>>>>-<<[-<<<<<-->>>>>>+<]>[-<+>]<<<<<<[->+>++<<]>>>>>>>+<<<<<[[-]>>>>>-<<[-<<<<---->>>>>+<]>[-<+>]<<<<<[->+<]>>>>>>+<<<<<[[-]>>>>>-<<<<<<<<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>]>>>>>[-<<<<<<<<+++++++++++++++++++++++++++++++++++++++++++++++++>>>>>>>>]<<<<<]>>>>>[-<<<<<<[->+<]>>>>>>+<<<<<[[-]>>>>>-<<<<<<<<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>]>>>>>[-<<<<<<<<+++++++++>>>>>>>>]]<<<<<]>>>>>[-<<<<<<<[->+>++<<]>>>>>>>+<<<<<[[-]>>>>>-<<[-<<<<---->>>>>+<]>[-<+>]<<<<<[->+<]>>>>>>+<<<<<[[-]>>>>>-<<<<<<<<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>]>>>>>[-<<<<<<<<+++++++++++++++++++++++++>>>>>>>>]<<<<<]>>>>>[-<<<<<<[->+<]>>>>>>+<<<<<[[-]>>>>>-<<<<<<<<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>]>>>>>[-<<<<<<<<+>>>>>>>>]]]<<<<<]>>>>>[-<<<<<<[-<+>>++++<]>>>>>>+<<<<<[[-]>>>>>-<<[-<<<<<-->>>>>>+<]>[-<+>]<<<<<<[->+>++<<]>>>>>>>+<<<<<[[-]>>>>>-<<[-<<<<---->>>>>+<]>[-<+>]<<<<<[->+<]>>>>>>+<<<<<[[-]>>>>>-<<<<<<<<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>]>>>>>[-<<<<<<<<++++++++++++++++++++++++++++++++++++>>>>>>>>]<<<<<]>>>>>[-<<<<<<[->+<]>>>>>>+<<<<<[[-]>>>>>-<<<<<<<<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>]>>>>>[-<<<<<<<<++++>>>>>>>>]]<<<<<]>>>>>[-<<<<<<<[->+>++<<]>>>>>>>+<<<<<[[-]>>>>>-<<[-<<<<---->>>>>+<]>[-<+>]<<<<<[->+<]>>>>>>+<<<<<[[-]>>>>>-<<<<<<<<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>]>>>>>[-<<<<<<<<++++++++++++++++>>>>>>>>]<<<<<]>>>>>[-<<<<<<[->+<]>>>>>>+<<<<<[[-]>>>>>-<<<<<<<<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>>]>>>>>[-<<<<<<<<>>>>>>>>]]]]<<[-]
What it needs
- Cells that wrap at a known width. The program text is made for that width (8, 16 or 32 bits) and gives wrong answers on any other.
- To be fast it needs an interpreter that does a flat loop in one step. In plain steps the shifts are long loops and the gain is lost.
- Nine scratch cells. The table length is a power of two. An x past the end counts from the start again.
Common mistakes
- Using it for a big table. The text grows with the table; the tape form, store and fetch by index, does not.
- Using a tree where x is nearly always tiny. A chain of "take 1 off, still not zero?" is shorter and then just as fast: that is the form The naive way: a chain on this page.
What it costs
A plain step is one command. An optimised step is one step of an interpreter that folds runs of the same command and flat loops. Choose the values and watch the two bars; What costs what explains how cost is counted:
The figure needs JavaScript. The table below has the measured steps.
Cost as a formula, and measured
| Form | Plain steps | Optimised steps |
|---|---|---|
| A table of squares | thousands | about 40 for 16 entries, 60 to 80 for 256 |
| The naive way: a chain | grows with x | about 4 per unit of x |
| Form | Values | Bits | Characters | Plain steps | Optimised steps |
|---|---|---|---|---|---|
| A table of squares | entries = 16; x = 5 | 32 | 4,035 | more than 30,000,000 | 38 |
| A table of squares | entries = 256; x = 3 | 32 | 134,250 | more than 30,000,000 | 61 |
| A table of squares | entries = 256; x = 100 | 32 | 134,250 | more than 30,000,000 | 69 |
| A table of squares | entries = 256; x = 255 | 32 | 134,250 | more than 30,000,000 | 82 |
| The naive way: a chain | entries = 16; x = 5 | 32 | 328 | 152 | 23 |
| The naive way: a chain | entries = 256; x = 3 | 32 | 66,328 | 88 | 15 |
| The naive way: a chain | entries = 256; x = 100 | 32 | 66,328 | 12,407 | 403 |
| The naive way: a chain | entries = 256; x = 255 | 32 | 66,328 | 71,152 | 1,023 |
Against the naive way
The same table as a chain: take 1 off x and add the next difference, once for every unit of x.
The numbers, row by row
This pattern against the naive way, on 16-bit cells, measured when this page was written. The bars show the last row: optimised steps.
| Values | Optimised steps | Plain steps | Characters | |||
|---|---|---|---|---|---|---|
| pattern | naive | pattern | naive | pattern | naive | |
| entries = 256; x = 3 | 57 | 15 | 296,377 | 88 | 133,198 | 66,328 |
| entries = 256; x = 100 | 65 | 403 | 8,060,647 | 12,407 | 133,198 | 66,328 |
| entries = 256; x = 255 | 78 | 1,023 | 20,528,684 | 71,152 | 133,198 | 66,328 |
Measured in the project for a table of 256 entries and a random x: about 68 optimised steps with the tree, against about 500 with the chain. measured in the project
Other forms
to measure against The naive way: a chain
Nested loops, one per entry. Short text, and a cost per unit of x.
[->>+>+<<<]>>>[-<<<+>>>]<[-<+>[-<+++>[-<+++++>[-<+++++++>[-<+++++++++>[-<+++++++++++>[-<+++++++++++++>[-<+++++++++++++++>[-<+++++++++++++++++>[-<+++++++++++++++++++>[-<+++++++++++++++++++++>[-<+++++++++++++++++++++++>[-<+++++++++++++++++++++++++>[-<+++++++++++++++++++++++++++>[-<+++++++++++++++++++++++++++++>[-]]]]]]]]]]]]]]]]
Run this form step by step
The form “The naive way: a chain” works on 4 cells; the named ones are “x”, “y” and “counter”. Press Play, drag the step slider forwards and back, or change x with the slider and edit the choice of entries:
The figure needs JavaScript. The program below is the result for the example values.
Where it is used
- Build toward a chatbot, lesson 10, "Looking back": the weights of attention and the reciprocal for its division come from two such tables.
- In the chat model:
lookupin patterns.js, for the weights of attention and for dividing by their total: see How it works, section "Looking back at the other words".
Sources
- Source: This project: emit.js and patterns.js: lookup, lookupChain (the baseline).
Every program on this page was run on many inputs, in plain and in optimised mode, and compared with JavaScript. The explanations are written for this page.