Sama Suomeksi
Front Page
Overview
Schedule
Lectures
Guides
Topics
Teachers
T-106.290 Ohjelmoinnin laboratoriotyöt
A bijection from 232 to 232.
In some tests you may wish to generate dispersed values, but use those values with a non-uniformly distributed frequency. This may be problematic if the random number generator you use produces adjacent values, such as integers in the range 1 to N. Therefore you need to scatter the values given by the random number generator into a wider range of possible values.It is dangerous to use overly simple scatters, such as a bitwise xor with a constant, because many adjacent values may be mapped to adjacent or nearly adjacent values. On the other hand you also have to ensure no two values are mapped to the same value, because this would distort the distribution.
I give below a function which scatters 32-bit unsigned integers. It guarantees that no two input values are mapped to the same value.
typedef unsigned long uint32_t; /* The 32-bit unsigned integer type. */
/* Numbers from 0 to 255 in random order and split so that bits 6 and
7 have been moved to bit positions 30 and 31, bits 4 and 5 have
been moved to 22 and 23, bits 2 and 3 have been moved to 14 and 15,
and bits 0 and 1 to bits 7 and 8, all other bits being zero. The
entropy of the table is almost 1684 bits. */
static uint32_t scatter_bits[256] = {
0xC080C040, 0x000040C0, 0xC0404040, 0x8000C0C0, 0x40000000, 0xC0C04080,
0x00008000, 0xC0800080, 0xC0400080, 0x00C00000, 0x80400080, 0x00C0C000,
0x808000C0, 0x80C04000, 0x80C0C000, 0x00800080, 0x00804040, 0x808040C0,
0x00400000, 0x804000C0, 0xC04000C0, 0x40808000, 0xC0C00000, 0x00800040,
0x8040C000, 0xC08080C0, 0x00C0C040, 0xC0004040, 0x00404080, 0x40004000,
0xC080C000, 0x00C04000, 0x40808080, 0x80C00000, 0xC040C080, 0xC0800040,
0x8080C080, 0xC000C040, 0x00C08040, 0xC04040C0, 0x80008040, 0x40408080,
0x400040C0, 0xC040C040, 0x40C000C0, 0x0080C040, 0x0080C080, 0x80400040,
0xC000C0C0, 0x00000080, 0xC0C08040, 0x0040C000, 0x004040C0, 0xC0C080C0,
0x000080C0, 0x00C00040, 0x8080C040, 0x00808040, 0xC0000000, 0x8040C080,
0x40C08040, 0xC0404000, 0x800000C0, 0x404000C0, 0x40800080, 0xC0400000,
0xC0804000, 0x80004040, 0x4040C0C0, 0xC0808080, 0x00404040, 0xC0C00040,
0x4000C0C0, 0x4080C080, 0x00408000, 0x004080C0, 0x80C00080, 0x00C08000,
0x80004080, 0xC0008000, 0x400000C0, 0x40C040C0, 0x40C00080, 0x40004080,
0x40C00000, 0x80C04080, 0x00C04040, 0x4000C080, 0x40C08080, 0x00008040,
0x00400040, 0x40004040, 0x80C0C040, 0x00408080, 0xC0C04000, 0x4080C040,
0x4040C000, 0xC0C04040, 0xC00000C0, 0x8000C080, 0xC0804040, 0xC0C0C080,
0xC0404080, 0x80800000, 0xC0C08080, 0x00004000, 0x40C04000, 0x40400040,
0x40404040, 0x40C080C0, 0x804040C0, 0x80C08040, 0x80000000, 0xC0408000,
0x004000C0, 0x40400000, 0x80000080, 0x40400080, 0x00000040, 0xC000C000,
0x80004000, 0xC080C080, 0x00400080, 0x008080C0, 0x00804000, 0x40408040,
0x40C0C080, 0x4080C000, 0x00C0C080, 0x40C00040, 0x40C04080, 0x80808040,
0xC0004000, 0xC000C080, 0xC08040C0, 0x80000040, 0x0040C080, 0x80808000,
0x0000C0C0, 0x8080C0C0, 0xC0C0C040, 0x00008080, 0x00C080C0, 0x0080C000,
0x00800000, 0x4040C040, 0xC0408080, 0x00404000, 0x8040C0C0, 0xC0000080,
0x408080C0, 0x40804080, 0x0000C080, 0xC0C0C000, 0xC00040C0, 0x80C040C0,
0xC0800000, 0x400080C0, 0xC0C0C0C0, 0x40808040, 0x00C000C0, 0xC0C00080,
0x80804040, 0x80008000, 0xC08000C0, 0x00C00080, 0x4080C0C0, 0x80800080,
0x00C04080, 0x0080C0C0, 0x40408000, 0x80C000C0, 0x80C08000, 0x80404040,
0x808080C0, 0x0040C0C0, 0x40804000, 0x0000C040, 0x404040C0, 0x80408000,
0x408040C0, 0xC0004080, 0xC0808000, 0x80C04040, 0x804080C0, 0x40C08000,
0x000000C0, 0x4000C040, 0x00004080, 0x00804080, 0x00808000, 0x80C00040,
0xC04080C0, 0x00C0C0C0, 0x008040C0, 0x40404080, 0xC0804080, 0x40C0C040,
0x800080C0, 0x80404080, 0xC0400040, 0x0040C040, 0x008000C0, 0xC040C0C0,
0x40008040, 0x00408040, 0x0000C000, 0x80400000, 0x40804040, 0x40C0C000,
0x404080C0, 0x40008000, 0x00000000, 0x80008080, 0x4040C080, 0xC00080C0,
0xC0C08000, 0xC080C0C0, 0x80404000, 0x8080C000, 0xC0C000C0, 0xC0008040,
0x40C0C0C0, 0x40000080, 0x40000040, 0x80800040, 0x80804000, 0x408000C0,
0xC0000040, 0x40404000, 0x40C04040, 0x40008080, 0x00C08080, 0x40800040,
0x800040C0, 0x8040C040, 0xC0408040, 0x80C08080, 0x80C0C0C0, 0x80408080,
0x4000C000, 0x80808080, 0xC0008080, 0x80C080C0, 0x8000C000, 0x00808080,
0x80804080, 0x00004040, 0x40800000, 0x00C040C0, 0x8000C040, 0x80408040,
0xC040C000, 0xC0808040, 0x80C0C080, 0xC0C040C0
};
/* This function implements a very complicated mapping from 32-bit
unsigned integers to 32-bit unsigned integers so that no two
integers map to he same value.
It has been verified experimentally with the chi-square-test that
this is just as good a scatterer function for `uint32_t's as a good
random number generator. */
uint32_t scatter(uint32_t x)
{
uint32_t y;
int i;
for (i = 0; i < 6; i++) {
y = scatter_bits[x & 0xFF];
x >>= 8;
y >>= 2;
y |= scatter_bits[x & 0xFF];
x >>= 8;
y >>= 2;
y |= scatter_bits[x & 0xFF];
x >>= 8;
y >>= 2;
x = y | scatter_bits[x];
}
return x;
}