Code patterns Advanced: wrapping cells of a known widthPick the largest by a race

Pick the largest by a race

Finds which of many numbers is the largest, without comparing any two of them.

Watch it run

The form “Two digits of four bits” works on 31 cells; the named ones are “result 0”, “high 0”, “low 0”, “result 1”, “high 1”, “low 1”, “result 2”, “high 2”, “low 2”, “result 3”, “high 3”, “low 3” and “scratch”. Press Play, drag the step slider forwards and back, or edit the scores:

The figure needs JavaScript. The program below is the result for the example values.

Add 1 to every number at the same time, again and again. The first one to reach the top was the largest. "Add 1 to all" is one flat loop: one step, however many numbers there are.

"Has anyone arrived?" is a scan (see find a zero cell or a marker). The numbers are stored as "distance still to go", so an arrival is a zero cell, and [>>>>>] slides over all the others and stops on it. If nobody has arrived it stops on an empty frame at the end, and a marker there says "go round again".

A race over the whole value would take up to 256 rounds. So each number is split into two digits of 4 bits. The race is run on the high digits first, 16 rounds at most; only the winners of that race take part in the race on the low digits.

The first of several equal numbers wins, because the scan comes from the left.

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:

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+[-<<<<<<<<<<<<<<<<<<<<<<<<<+>>>---------------->-------------------------------->+>>>---------------->-------------------------------->+>>>---------------->-------------------------------->+>>>---------------->-------------------------------->>>>>>]<<<<+[>>>>+[-<<<<<<<<<<<<<<<<<<<<<<+>>>>>+>>>>>+>>>>>+>>>>>>>]<<<<<<<<<<<<<<<<<<<<<<[>>>>>]<<]<[>>>>++++++++++++++++<>>>>>[>>>>>]<<<]>[>>>>+[-<<<<<<<<<<<<<<<<<<<<<+>>>>>+>>>>>+>>>>>+>>>>>>]<<<<<<<<<<<<<<<<<<<<<[>>>>>]<<<]>+<<[<<<<<]>>>>>>>>>>>>>>>>>>>>>>>>>>->>>>+[-<<<<<<<<<<<<<<<<<<<<<<<<<->>>>>->>>>>->>>>>->>>>>>>>>>]<<<<<<<<<<<<<<<<<<<<<<[-]>[-]>>>>[-]>[-]>>>>[-]>[-]>>>>[-]>[-]

Open in the playground663 characters

What it needs

Each number in a frame of five cells: marker, marker, result, high digit, low digit, with one empty frame before and after. One scratch cell.
Any cell size that wraps. The numbers are used up; the result is a 1 in the result cell of the winner.
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.

Common mistakes

Racing on whole values. With 512 numbers a round is about 515 steps; 200 rounds are 100,000 steps.
Forgetting the empty frames at both ends: the scan needs a place to stop, and the walk home needs one too.

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

**Table 1.** The cost as a function of the values.
Form	Plain steps	Optimised steps
Two digits of four bits	hundreds to thousands	about (numbers + 3) per round; at most 32 rounds
The naive way: count down and test each one	grows with numbers × (255 − best)	about 10 per number per round; 255 − best rounds

**Table 2.** Measured when this page was written.
Form	Values	Bits	Characters	Plain steps	Optimised steps
Two digits of four bits	the scores = 93, 41, 207, 150	8	663	3,891	62
Two digits of four bits	the scores = 3, 1, 2, 0, 3, … (8)	8	1,175	9,604	384
Two digits of four bits	the scores = 255, 255	8	407	412	30
The naive way: count down and test each one	the scores = 93, 41, 207, 150	8	536	954,386	1,825
The naive way: count down and test each one	the scores = 3, 1, 2, 0, 3, … (8)	8	1,384	17,385,019	18,487
The naive way: count down and test each one	the scores = 255, 255	8	232	1,147	31

Against the naive way

The race of the first version of this project: count every number down by 1 per round, and test each one for zero with a copy.

The numbers, row by row

this pattern: the scores = 3, 1, 2, 0, 3, … (8)

384the naive way: the scores = 3, 1, 2, 0, 3, … (8)

18,487

This pattern against the naive way, on 8-bit cells, measured when this page was written. The bars show the last row: optimised steps.

Values	Optimised steps		Plain steps		Characters
Values	pattern	naive	pattern	naive	pattern	naive
the scores = 93, 41, 207, 150	62	1,825	3,891	954,386	663	536
the scores = 3, 1, 2, 0, 3, … (8)	384	18,487	9,604	17,385,019	1,175	1,384

Measured in the project for 512 scores on 32-bit cells: about 5,000 optimised steps with digits of 2 bits, against 119,000 to 595,000 for the baseline, depending on how high the best score is. measured in the project

Other forms

to measure against The naive way: count down and test each one

The lowest "distance to go" wins, so each score is stored as 255 − score. Scores in cells 0…, results after them.

>>>>>>>>+[>>>+<<<<<<<<<<<[->>>>>>>>>+>+<<<<<<<<<<]>>>>>>>>>>[-<<<<<<<<<<+>>>>>>>>>>]<[>>-<<[-]]>>[<<<[->+>+<<]>>[-<<+>>]<[<-<<<<+>>>>>[-]]>>[-]]+<<<<<<<<<<[->>>>>>>>+>+<<<<<<<<<]>>>>>>>>>[-<<<<<<<<<+>>>>>>>>>]<[>>-<<[-]]>>[<<<[->+>+<<]>>[-<<+>>]<[<-<<<+>>>>[-]]>>[-]]+<<<<<<<<<[->>>>>>>+>+<<<<<<<<]>>>>>>>>[-<<<<<<<<+>>>>>>>>]<[>>-<<[-]]>>[<<<[->+>+<<]>>[-<<+>>]<[<-<<+>>>[-]]>>[-]]+<<<<<<<<[->>>>>>+>+<<<<<<<]>>>>>>>[-<<<<<<<+>>>>>>>]<[>>-<<[-]]>>[<<<[->+>+<<]>>[-<<+>>]<[<-<+>>[-]]>>[-]]<<<<<<<<<<<->->->->>>>>]<<<<<<<<[-]>[-]>[-]>[-]

Open in the playground536 characters

Run this form step by step

The form “The naive way: count down and test each one” works on 12 cells; the named ones are “to go 0”, “to go 1”, “to go 2”, “to go 3”, “result 0”, “result 1”, “result 2” and “result 3”. Press Play, drag the step slider forwards and back, or edit the scores:

The figure needs JavaScript. The program below is the result for the example values.

Where it is used

Build toward a chatbot, lesson 11, "Choosing the word": it chooses the next word piece this way.
In the chat model: argmax in patterns.js picks the next word piece out of tens of thousands: see How it works, section "Choosing the word". splitDigits makes the digits with the bit peel.

Sources

Source: This project: emit.js and patterns.js: argmax, argmaxRaceNaive (the baseline), frames, splitDigits.

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.