The discrete Hilbert curve *H*_{n} of level n can be viewed as a function from a single 2n-bit unsigned integer to two n-bit unsigned integers.
The straightforward method for computing a single point (x,y) = H(t) on this curve requires O(n) operations to compute one bit of the result at a time
(see the Wikipedia article for details).

This can be sped up to O(log n) using parallel prefix ideas as follows:

- Uninterleave the bit string t into two n-bit strings (tx,ty), which takes O(log n) operations.
- Note that each pair of bits in the result (x,y) is given by a applying one of the isometries of the square to the corresponding pair of bits in (tx,ty). The particular isometry is determined by the product of the isometries produced by all higher bits.
- Use a parallel prefix circuit to compute the isometries for each bit pair. Conveniently, the isometries required form a
subgroup of
*D*_{4}isomophic to*Z*_{2}x*Z*_{2}, so the group products are just xors. This takes O(log n) operations if n is within the word size of the machine. - Compute all bits of the result using the isometries with O(1) operations.

The file hilbert.c contains random access and incremental versions of this algorithm, as well as testing code.

To see what one of these actually looks like, here's a Hilbert curve of level 8 mapping a smooth ramp from green to blue to red into the square: