Code patterns ArithmeticPowers of two, and powers

Powers of two, and powers

Works out 2 to the power n, or x to the power y.

Watch it run

The form “2 to the power n” works on 3 cells, named “n”, “result” and “scratch”. Press Play, drag the step slider forwards and back, or change n with the slider:

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

Start at 1 and double it n times. Doubling is multiplying by the constant 2 (see multiply by a constant), into a scratch cell and back.

A general power is the same loop round a multiplication (see multiply two cells) instead of a doubling.

Doubling a number moves all its bits one place up. On a wrapping cell the top bit falls out. That is the idea the bit peel turns into a tool.

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 playground23 characters

What it needs

One scratch cell for 2ⁿ, three for x to the power y. n and y are used up.
Any cell size. The result wraps: 2⁸ is 0 on 8-bit cells.

Common mistakes

Expecting 0 to the power 0 to be 0. The loop never runs, so the answer is the 1 it started with.
Leaving the base behind: the general form keeps a copy of x in a scratch cell and must clear it at the end. The snippet on the wiki does not.

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
2 to the power n	grows with 2ⁿ	2 + 4n
x to the power y	grows with the result	grows with the result ÷ x

**Table 2.** Measured when this page was written.
Form	Values	Bits	Characters	Plain steps	Optimised steps
2 to the power n	n = 0	8	23	4	2
2 to the power n	n = 5	8	23	540	22
2 to the power n	n = 12	8	23	2,900	50
x to the power y	x = 3; y = 4	8	63	2,643	181
x to the power y	x = 2; y = 5	8	63	1,605	149

Other forms

x to the power y

Layout: x, y, three scratch cells. x becomes the result.

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

Open in the playground63 characters

Run this form step by step

The form “x to the power y” works on 5 cells, named “x”, “y”, “base”, “scratch” and “counter”. Press Play, drag the step slider forwards and back, or change x and y with the sliders:

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

Where it is used

The bit peel multiplies by a power of two to push bits out of the cell.
In the project: pow2 and shl in patterns.js build large powers of two from short loops.

Sources

Source: Esolang wiki: Brainfuck algorithms: section "x = x^y" (chad3814); here with its scratch cell cleared at the end.

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.