Halton sequence
11, Jul, 2015Following on from the Blum Blum Shub post, there are times when you want a set of positions that look random, but which are spread out more evenly than a random plot would give. If you remember, we used BBS to plot this:
# # # # # ## # # # # # # # # # # # # # # # # # # # ## # # # # # # # # # # # # # # # # # # ## # # # # # # # # # # ## # # # ## # # # # # # # # # # # # # ## # # # # # # # ## # # # ## #
Whereas Halton sequences will give you something like this:
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
This works by following a simple but different patterns on each axis. The pattern is called a Van der Corput sequence, and here’s what it looks like in base 2:
The sequence is generated by “flipping” the index over the decimal point. For example, 12345 becomes 0.54321 or in binary, 110 becomes 0.011.
This is really simple to do in code. This will give you the above output (View on IDEOne):
#include <stdio.h>
#include <stdint.h>
#include <math.h>
float VanDerCorput(uint32_t index, uint32_t base)
{
float result = 0;
float f = 1.0f;
uint32_t i = index;
while (i > 0)
{
f /= static_cast<float>(base);
result += f * (i % base);
i /= base;
}
return result;
}
int main()
{
uint32_t Bitmap[32] = {0};
for (int i=0 ; i<100 ; ++i)
{
uint32_t x = (uint32_t) floorf(VanDerCorput(i, 2) * 32);
uint32_t y = (uint32_t) floorf(VanDerCorput(i, 3) * 32);
Bitmap[x] |= 1<<y;
}
for (uint32_t y=0 ; y<32 ; ++y)
{
for (uint32_t x=0 ; x<32 ; ++x)
{
printf("%c", Bitmap[x] & 1<<y ? '#' : ' ');
}
printf("\\n");
}
return 0;
}
