CARDIAC › Tips and tricks › Lay your tables out by tens
Lay your tables out by tens
On CARDIAC, where a table sits in memory decides how fast a program can find things in it, and how
big the program is. This page starts with the obvious layout, shows where it goes wrong, and then shows a better
one that CARDIAC's own manual used and almost nobody has used since.
Lists
CARDIAC has a hundred cells, 00 to 99. Write them out ten to a line and the first digit of an address is its line,
and the second digit is how far along the line it is: cell 63 is line 6, place 3. Every map on this page is
CARDIAC's whole memory drawn that way, with table data in blue, code in green and variables in yellow.
A list is the easy case. Put the items one after another, and if the list starts at cell 40, item i is in cell
40 + i, however long the list is. There's only one sensible way to lay out a list. It gets interesting in two
dimensions.
Table dataCodeVariables and constantsCell 00, always 001Free
Ten high scores in cells 40 to 49. Each is labelled with its place in the list, which is also the last
digit of its address.
Tables
In Minesweeper, when you uncover a square, the game shows how many mines touch it, counting the diagonals. Here's
that count on a board of four rows by six squares. The program reads a square and prints how many of its eight
neighbours are mines. In the maps, each square is labelled with its row and column, and the squares with mines are
in red.
Every version uses the same loop. It starts from the square's top-left neighbour and adds a list of offsets to
reach the other seven, stopping at a -1. What changes from one version to the next is where the board sits, how the program
works out the top-left neighbour's address, and the offsets.
The obvious way
C-style
Most of us would lay the board out the way C lays out a two-dimensional array: the rows one straight after another, from cell 40. The top-left neighbour of the square in row r, column c
is in cell 40 + 6r + c - 7, and CARDIAC can't multiply, so the program gets 6r by adding r six times.
Table dataCodeVariables and constantsCell 00, always 001Free
Worse, it gets the wrong answer at the edges. The square at the start of row 2 has a "left neighbour" at the
end of row 1, so for row 2, column 0 the program counts the mine at the end of row 0 and prints 2 when the
answer is 1. On the top row it reads cells that aren't on the board at all. For row 0, column 0 it adds up
part of its own code and prints 902. Six of the 24 squares come out wrong.
cell contents notes
10 070 INP 70 cells 10-11: the row and the column
11 071 INP 71
12 170 CLA 70 cells 12-17: 6r, by adding r six times
13 270 ADD 70
14 270 ADD 70
15 270 ADD 70
16 270 ADD 70
17 270 ADD 70
18 271 ADD 71 cells 18-20: x is ADD the top-left neighbour, cell 40 + 6r + c - 7
19 272 ADD 72
20 673 STO 73
21 175 CLA 75 cells 21-31: add up the eight neighbours, one offset at a time, until the -1
22 332 TAC 32
23 273 ADD 73
24 626 STO 26
25 174 CLA 74
26 200 ADD 00 ADD a neighbour, written by cell 24
27 674 STO 74
28 121 CLA 21
29 200 ADD 00
30 621 STO 21
31 821 JMP 21
32 574 OUT 74 cells 32-33: print the count
33 900 HRS 00
40 000 cells 40-45: row 0; 1 is a mine
41 001
42 000
43 000
44 000
45 001
46 000 cells 46-51: row 1; 1 is a mine
47 000
48 000
49 001
50 000
51 000
52 000 cells 52-57: row 2; 1 is a mine
53 000
54 001
55 000
56 000
57 000
58 001 cells 58-63: row 3; 1 is a mine
59 000
60 000
61 000
62 001
63 000
70 000 r
71 000 c
72 233 ADD 33: the top-left neighbour of the square at 40
73 000 x
74 000 the count
75 000 the neighbours' offsets from the top-left one: a row is 6 cells
76 001
77 002
78 006
79 008
80 012
81 013
82 014
83 -001 -1: no more
Step through it in Cardigan
With 2 and 0 it prints 2, which is wrong. It takes 62 cells and runs 103 instructions.
C-style, with a border
The usual fix is a border of empty squares all the way round, so that every square on the board has eight
real neighbours. Now each row is eight cells, the board takes 48, and the top-left neighbour is in cell
40 + 8r + c, so the program adds r eight times.
Table dataEdge: holds 0, no mineCodeVariables and constantsCell 00, always 001Free
cell contents notes
10 036 INP 36 cells 10-11: the row and the column
11 037 INP 37
12 136 CLA 36 cells 12-19: 8r, by adding r eight times
13 236 ADD 36
14 236 ADD 36
15 236 ADD 36
16 236 ADD 36
17 236 ADD 36
18 236 ADD 36
19 236 ADD 36
20 237 ADD 37 cells 20-22: x is ADD the top-left neighbour, cell 40 + 8r + c
21 238 ADD 38
22 639 STO 39
23 189 CLA 89 cells 23-33: add up the eight neighbours, one offset at a time, until the -1
24 334 TAC 34
25 239 ADD 39
26 628 STO 28
27 188 CLA 88
28 200 ADD 00 ADD a neighbour, written by cell 26
29 688 STO 88
30 123 CLA 23
31 200 ADD 00
32 623 STO 23
33 823 JMP 23
34 588 OUT 88 cells 34-35: print the count
35 900 HRS 00
36 000 r
37 000 c
38 240 ADD 40: the top-left neighbour of the first square
39 000 x
40 000 cells 40-47: the border, a row of 0s
41 000
42 000
43 000
44 000
45 000
46 000
47 000
48 000 the border
49 000 row 0; 1 is a mine
50 001
51 000
52 000
53 000
54 001
55 000 the border
56 000 the border
57 000 row 1; 1 is a mine
58 000
59 000
60 001
61 000
62 000
63 000 the border
64 000 the border
65 000 row 2; 1 is a mine
66 000
67 001
68 000
69 000
70 000
71 000 the border
72 000 the border
73 001 row 3; 1 is a mine
74 000
75 000
76 000
77 001
78 000
79 000 the border
80 000 cells 80-87: the border, a row of 0s
81 000
82 000
83 000
84 000
85 000
86 000
87 000
88 000 the count
89 000 the neighbours' offsets from the top-left one: a row is 8 cells
90 001
91 002
92 008
93 010
94 016
95 017
96 018
97 -001 -1: no more
Step through it in Cardigan
With 2 and 0 it prints 1, and every square comes out right. It takes 88 cells and runs 105
instructions.
Why not just check for the edges?
On most computers you'd skip the border and test for the edges in code: run the rows from the larger of r - 1
and 0 to the smaller of r + 1 and 3, the same for the columns, and add up what's inside. We wrote that out for
CARDIAC. The four edge tests and the two loops come to about 76 cells of code, and with the board and its
variables the program needs about 114 cells. CARDIAC has a hundred, so it doesn't fit at all. The border costs
24 cells of zeros, and the program that uses it runs straight through without a single test. On CARDIAC, clever
memory layout beats clever code.
A better way
The better way was pioneered by CARDIAC's creators, David Hagelbarger and Saul Fingerman, in the Nim
programs on pages 41 and 47–48 of the original CARDIAC manual, but it has largely been forgotten. Here we go
into it in more depth.
It sounds wrong: leave holes in the table. Start every row ten cells after the one before, and the row and column
you're looking for turn out to be the address itself. The tabs show the board by tens, first
with the row and column on two cards, then as one number.
By tens
Give every row a line of memory, at 50, 60, 70 and 80. The gaps do the border's job: column 6 is the border to
the right of each row, column 9 is the border to the left of the next, and lines 4 and 9 are the border above
and below. The top-left neighbour is in cell 50 + 10r + c - 11, and 10r is one shift.
Table dataEdge: holds 0, no mineCodeVariables and constantsCell 00, always 001Free
Look at the offsets, too: 0, 1, 2, 10, 12, 20, 21 and 22. Read as two digits, they're the row and column of
each neighbour within the 3 by 3 square around the one you uncovered, with 11, the square itself, left out.
Columns 7 and 8 aren't anyone's neighbour, so the variables live there.
cell contents notes
10 047 INP 47 cells 10-11: the row and the column
11 048 INP 48
12 147 CLA 47 cells 12-13: 10r, one shift
13 410 SFT 10
14 248 ADD 48 cells 14-16: x is ADD the top-left neighbour, cell 50 + 10r + c - 11
15 257 ADD 57
16 658 STO 58
17 130 CLA 30 cells 17-27: add up the eight neighbours, one offset at a time, until the -1
18 328 TAC 28
19 258 ADD 58
20 622 STO 22
21 167 CLA 67
22 200 ADD 00 ADD a neighbour, written by cell 20
23 667 STO 67
24 117 CLA 17
25 200 ADD 00
26 617 STO 17
27 817 JMP 17
28 567 OUT 67 cells 28-29: print the count
29 900 HRS 00
30 000 the neighbours' offsets from the top-left one: rows are 10 apart
31 001
32 002
33 010
34 012
35 020
36 021
37 022
38 -001 -1: no more
39 000 cells 39-46: the border above row 0
40 000
41 000
42 000
43 000
44 000
45 000
46 000
47 000 r cells 47-48, 57-58 and 67: variables, in the gap where no square looks
48 000 c
49 000 the border, in the gap
50 000 cells 50-55: row 0; 1 is a mine
51 001
52 000
53 000
54 000
55 001
56 000 the border, in the gap
57 239 ADD 39: the top-left neighbour of the square at 50
58 000 x
59 000
60 000 cells 60-65: row 1; 1 is a mine
61 000
62 000
63 001
64 000
65 000
66 000
67 000 the count
69 000
70 000 cells 70-75: row 2; 1 is a mine
71 000
72 001
73 000
74 000
75 000
76 000
79 000
80 001 cells 80-85: row 3; 1 is a mine
81 000
82 000
83 000
84 001
85 000
86 000
89 000
90 000 cells 90-96: the border below row 3
91 000
92 000
93 000
94 000
95 000
96 000
Step through it in Cardigan
With 2 and 0 it prints 1, and every square comes out right. It takes 82 cells and runs 99
instructions.
By tens, one number
Now give the square as a single number, row then column: 20 for row 2, column 0. On the board by tens, that
number plus 39 is the top-left neighbour's address. There's nothing to work out. The program adds the
instruction ADD 39 to the number and that's the first neighbour.
Table dataEdge: holds 0, no mineCodeVariables and constantsCell 00, always 001Free
cell contents notes
10 047 INP 47 cells 10-13: the square as one number, row then column: 20 is row 2, column 0
11 147 CLA 47
12 248 ADD 48
13 657 STO 57
14 127 CLA 27 cells 14-24: add up the eight neighbours, one offset at a time, until the -1
15 325 TAC 25
16 257 ADD 57
17 619 STO 19
18 158 CLA 58
19 200 ADD 00 ADD a neighbour, written by cell 17
20 658 STO 58
21 114 CLA 14
22 200 ADD 00
23 614 STO 14
24 814 JMP 14
25 558 OUT 58 cells 25-26: print the count
26 900 HRS 00
27 000 the neighbours' offsets from the top-left one: rows are 10 apart
28 001
29 002
30 010
31 012
32 020
33 021
34 022
35 -001 -1: no more
39 000 cells 39-46: the border above row 0
40 000
41 000
42 000
43 000
44 000
45 000
46 000
47 000 the square cells 47-48, 57-58: variables, in the gap where no square looks
48 239 ADD 39: the top-left neighbour of the square at 50
49 000 the border, in the gap
50 000 cells 50-55: row 0; 1 is a mine
51 001
52 000
53 000
54 000
55 001
56 000 the border, in the gap
57 000 x
58 000 the count
59 000
60 000 cells 60-65: row 1; 1 is a mine
61 000
62 000
63 001
64 000
65 000
66 000
69 000
70 000 cells 70-75: row 2; 1 is a mine
71 000
72 001
73 000
74 000
75 000
76 000
79 000
80 001 cells 80-85: row 3; 1 is a mine
81 000
82 000
83 000
84 001
85 000
86 000
89 000
90 000 cells 90-96: the border below row 3
91 000
92 000
93 000
94 000
95 000
96 000
Step through it in Cardigan
With 20 it prints 1, and every square comes out right. It takes 78 cells and runs 96
instructions.
| The board | Cells | Instructions | Right everywhere? |
| C-style | 62 | 103 | No, 6 wrong |
| C-style, with a border | 88 | 105 | Yes |
| By tens | 82 | 99 | Yes |
| By tens, one number | 78 | 96 | Yes |
The instruction counts are close, because visiting eight neighbours costs the same in every layout. The
difference is in getting started. The C-style board is small but wrong. Fixing it with a border makes it right, and
bigger, and slower to find a square. The board by tens is right everywhere, finds its square with one shift or
with no arithmetic at all, and keeps its variables in cells the border doesn't need.
Three dimensions
An address has only two digits, so a third dimension has to share one. The trick is to number things so that two
dimensions fit in a single digit. In 3D tic-tac-toe, the board is three layers of 3 by 3, and the nine squares of a
layer can be numbered 1 to 9 like the keys on a phone. Then the layer is the tens digit and the square is the
units, so square 5 on layer 2 is 25.
The program puts an X on a square and says whether it fills a pillar, the same square on all three layers. X is 1
and O is -1, so a pillar is all X's exactly when it adds up to 3.
C-style
The 27 squares go one after another from cell 50, nine to a layer. The program reads the layer, row and
column, 0 to 2 each, and the square is in cell 50 + 9z + 3y + x: it adds z nine times and y three times. Each
square is labelled with its layer and its keypad number, so you can see the layers wrap across the lines.
Table dataCodeVariables and constantsCell 00, always 001Free
cell contents notes
10 080 INP 80 cells 10-12: the layer, the row and the column, 0-2 each
11 081 INP 81
12 082 INP 82
13 180 CLA 80 cells 13-21: 9z, by adding z nine times
14 280 ADD 80
15 280 ADD 80
16 280 ADD 80
17 280 ADD 80
18 280 ADD 80
19 280 ADD 80
20 280 ADD 80
21 280 ADD 80
22 281 ADD 81 cells 22-24: 3y
23 281 ADD 81
24 281 ADD 81
25 282 ADD 82 cells 25-29: STO 50 + 9z + 3y + x, then put the X there: cell 00's 1
26 283 ADD 83
27 629 STO 29
28 100 CLA 00
29 600 STO 00 written by cell 27
30 181 CLA 81 cells 30-33: 3y + x again, for the pillar
31 281 ADD 81
32 281 ADD 81
33 282 ADD 82
34 284 ADD 84 cells 34-39: the pillar under it: CLA, ADD and ADD, one layer apart
35 640 STO 40
36 285 ADD 85
37 641 STO 41
38 286 ADD 86
39 642 STO 42
40 100 CLA 00 cells 40-42: add up the pillar, written by the cells before
41 200 ADD 00
42 200 ADD 00
43 787 SUB 87 cells 43-48: three X's make 3; anything less isn't a full pillar
44 347 TAC 47
45 500 OUT 00 a full pillar: print 1
46 900 HRS 00
47 588 OUT 88 print 0
48 900 HRS 00
50 001 cells 50-58: layer 0; 1 is X, -1 is O
51 000
52 000
53 000
54 001
55 000
56 -001
57 000
58 000
59 000 cells 59-67: layer 1; 1 is X, -1 is O
60 -001
61 001
62 000
63 001
64 000
65 000
66 000
67 -001
68 000 cells 68-76: layer 2; 1 is X, -1 is O
69 000
70 000
71 000
72 000
73 000
74 001
75 000
76 000
80 000 z
81 000 y
82 000 x
83 650 STO 50
84 150 CLA 50
85 109 CLA to ADD, and one layer on
86 009 one layer on
87 003
88 000
Step through it in Cardigan
With layer 2, row 1, column 1, the middle square, it prints 1: that fills the pillar. It takes 75
cells and runs 37 instructions.
By tens
Each layer gets a line, and square s of layer z is in cell 40 + 10z + s. The first cell of each line, where
square 0 would be, is free for a variable.
Table dataCodeVariables and constantsCell 00, always 001Free
cell contents notes
10 040 INP 40 cells 10-11: the layer, 0-2, and the square, 1-9
11 050 INP 50
12 140 CLA 40 cells 12-17: 10z: one shift; STO 40 + 10z + s, then put the X there
13 410 SFT 10
14 250 ADD 50
15 260 ADD 60
16 618 STO 18
17 100 CLA 00
18 600 STO 00 written by cell 16
19 150 CLA 50 cell 19: the square, for the pillar
20 270 ADD 70 cells 20-25: the pillar under it: CLA, ADD and ADD, one layer apart
21 626 STO 26
22 271 ADD 71
23 627 STO 27
24 272 ADD 72
25 628 STO 28
26 100 CLA 00 cells 26-28: add up the pillar, written by the cells before
27 200 ADD 00
28 200 ADD 00
29 773 SUB 73 cells 29-34: three X's make 3; anything less isn't a full pillar
30 333 TAC 33
31 500 OUT 00 a full pillar: print 1
32 900 HRS 00
33 574 OUT 74 print 0
34 900 HRS 00
40 000 z cells 40, 50 and 60: variables, in the cell before each layer
41 001 cells 41-49: layer 0; 1 is X, -1 is O
42 000
43 000
44 000
45 001
46 000
47 -001
48 000
49 000
50 000 s
51 000 cells 51-59: layer 1; 1 is X, -1 is O
52 -001
53 001
54 000
55 001
56 000
57 000
58 000
59 -001
60 640 STO 40
61 000 cells 61-69: layer 2; 1 is X, -1 is O
62 000
63 000
64 000
65 000
66 000
67 001
68 000
69 000
70 140 CLA 40
71 110 CLA to ADD, and one layer on
72 010 one layer on
73 003
74 000
Step through it in Cardigan
With layer 2, square 5 it prints 1. It takes 60 cells and runs 23 instructions.
By tens, one number
Give the move as one number, 25, and that number plus 40 is the square. The pillar comes from its last digit,
which SFT 33 cuts out.
Table dataCodeVariables and constantsCell 00, always 001Free
cell contents notes
10 040 INP 40 cells 10-14: the move as one number, layer then square: 25 is layer 2, square 5
11 140 CLA 40
12 260 ADD 60 STO 40 + the move
13 615 STO 15
14 100 CLA 00
15 600 STO 00 put the X there: cell 00's 1, written by cell 13
16 140 CLA 40 cells 16-17: the square, 1-9, is the last digit
17 433 SFT 33
18 270 ADD 70 cells 18-23: the pillar under it: CLA, ADD and ADD, one layer apart
19 624 STO 24
20 271 ADD 71
21 625 STO 25
22 272 ADD 72
23 626 STO 26
24 100 CLA 00 cells 24-26: add up the pillar, written by the cells before
25 200 ADD 00
26 200 ADD 00
27 773 SUB 73 cells 27-32: three X's make 3; anything less isn't a full pillar
28 331 TAC 31
29 500 OUT 00 a full pillar: print 1
30 900 HRS 00
31 574 OUT 74 print 0
32 900 HRS 00
40 000 the move cells 40, 50 and 60: variables, in the cell before each layer
41 001 cells 41-49: layer 0; 1 is X, -1 is O
42 000
43 000
44 000
45 001
46 000
47 -001
48 000
49 000
51 000 cells 51-59: layer 1; 1 is X, -1 is O
52 -001
53 001
54 000
55 001
56 000
57 000
58 000
59 -001
60 640 STO 40
61 000 cells 61-69: layer 2; 1 is X, -1 is O
62 000
63 000
64 000
65 000
66 000
67 001
68 000
69 000
70 140 CLA 40
71 110 CLA to ADD, and one layer on
72 010 one layer on
73 003
74 000
Step through it in Cardigan
With 25 it prints 1. It takes 57 cells and runs 21 instructions.
| The board | Cells | Instructions |
| C-style | 75 | 37 |
| By tens | 60 | 23 |
| By tens, one number | 57 | 21 |
All three are right for every move. Here the tens layout is about 40 percent faster and 15 cells smaller, because
with the keypad numbering the move itself is the address.
When not to
Rows wider than ten don't fit, since a row has to stay inside its line. A plain list gets nothing from this,
because its entries are one apart either way. And memory only has ten lines, so a tall table leaves less room for
everything else. Tens also stops paying when a program never works out an address from coordinates, for example
when its addresses are all written out ahead of time in a table. For a board, a grid, or anything you look up by
two small numbers, though, lay it out by tens.
Know a trick like this one? Send it to nerd@strangequery.com and it
might end up here.
The short version of
this tip, with the others in all the tips.