Code patterns ArithmeticSquare

Square

Replaces a number by its square.

Watch it run

The form “As a sum of odd numbers” works on 3 cells, named “x”, “counter” and “scratch”. Press Play, drag the step slider forwards and back, or change x with the slider:

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

A square is a sum of odd numbers: 1 + 3 + 5 + 7 = 16 = 4 × 4. The loop counts down from x and each round adds the next odd number, two for every unit still left plus one.

The other way is plain: copy x and multiply the two (see copy a value and multiply two cells).

The code

This is the program the figure ran. It is brainfuck as it stands: copy it, or open it in the playground, where you can change it:

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

Open in the playground32 characters

What it needs

Two scratch cells (odd-number form) or three (copy form). Any cell size; too large a square wraps.
The pointer ends where it started.

Common mistakes

Expecting the square of 16 or more to fit an 8-bit cell: 16 × 16 = 256 wraps to 0.

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. Exact formulas are checked on every case they run.
Form	Plain steps	Optimised steps
As a sum of odd numbers	about 7 × x × x	3 + 5x
Copy, then multiply	13 to 20 × x × x	6 + 4x

**Table 2.** Measured when this page was written.
Form	Values	Bits	Characters	Plain steps	Optimised steps
As a sum of odd numbers	x = 5	8	32	214	28
As a sum of odd numbers	x = 15	8	32	1,684	78
As a sum of odd numbers	x = 255	8	32	456,964	1,278
Copy, then multiply	x = 5	8	64	512	26

Other forms

Copy, then multiply

Layout: x, copy, two scratch cells.

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

Open in the playground64 characters

Run this form step by step

The form “Copy, then multiply” works on 4 cells, named “x”, “copy”, “scratch” and “counter”. Press Play, drag the step slider forwards and back, or change x with the slider:

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

Where it is used

Table lookup as a decision tree uses a table of squares as its example and gets the same answer in a fixed number of steps.

Sources

Source: Esolang wiki: Brainfuck algorithms: section "x = x * x" (Softengy): the sum of odd numbers.

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.