Nice series—look familiar?

0        1        2        3        4        5        6        7
8        9       10       11       12       13       14       15
16       18       20       22       24       26       28       30
32       36       40       44       48       52       56       60
64       72       80       88       96      104      112      120
128      144      160      176      192      208      224      240
256      288      320      352      384      416      448      480
512      576      640      704      768      832      896      960
1024     1152     1280     1408     1536     1664     1792     1920
2048     2304     2560     2816     3072     3328     3584     3840
4096     4608     5120     5632     6144     6656     7168     7680
8192     9216    10240    11264    12288    13312    14336    15360
16384    18432    20480    22528    24576    26624    28672    30720
32768    36864    40960    45056    49152    53248    57344    61440
65536    73728    81920    90112    98304   106496   114688   122880
131072   147456   163840   180224   196608   212992   229376   245760
262144   294912   327680   360448   393216   425984   458752   491520
524288   589824   655360   720896   786432   851968   917504   983040
1048576  1179648  1310720  1441792  1572864  1703936  1835008  1966080
2097152  2359296  2621440  2883584  3145728  3407872  3670016  3932160
4194304  4718592  5242880  5767168  6291456  6815744  7340032  7864320

The answer, of course, is that they are floating point numbers. Well, clearly that’s not true, they are integers, but the distribution is the same as floating point numbers, and just need some appropriate scaling, for example, by dividing by 8388608 to get a nice set of numbers in the interval [0,1).

Notice that for all but the first row, every entry in a row has the same number of digits in its binary representation – they are normalized, with the first row corresponding to the denormalized numbers of IEEE-754. Without the denormalized numbers, zero would be sitting in splendid isolation, surrounded by a great hole, ready to catch the unwary.

Also, the numbers in each row are the same distance apart, with the gap at row n+1 being twice the gap at row n. Again, the first row is the exception, the gap here is the same as the second row – so the first 16 numbers form a uniformly spaced sequence from 0 – there isn’t anything very peculiar about the denormalized numbers, they just represent a continuation of the first row of normalized numbers to fill the gap down to zero.

We can see how a scaled comparison of floats might work too – within each row, two elements are close if they are within n places of each other, or equivalently, if they are within some constant multiple of the row gap. For elements in different rows, we can either just carry on counting the number of intervening numbers, or continue using the row gap to define a neighbourhood of each number. For example, if “close” means “twice the row gap”, then 22 is close to 18, 20, 24 and 26; 16 is close to 12, 13, 14. 15, 18 and 20; and 15 is close to just 13, 14 and 16. This notion of closeness is discussed by Knuth in TAOCP.

We don’t have to be twoist about this, here’s a similar sequence based on powers of 3, with 10 elements in each segment. This gives us 5 denormalized values:

0       1       2       3       4
5       6       7       8       9      10      11      12      13      14
15      18      21      24      27      30      33      36      39      42
45      54      63      72      81      90      99     108     117     126
135     162     189     216     243     270     297     324     351     378
405     486     567     648     729     810     891     972    1053    1134
1215    1458    1701    1944    2187    2430    2673    2916    3159    3402
3645    4374    5103    5832    6561    7290    8019    8748    9477   10206
10935   13122   15309   17496   19683   21870   24057   26244   28431   30618
32805   39366   45927   52488   59049   65610   72171   78732   85293   91854
98415  118098  137781  157464  177147  196830  216513  236196  255879  275562
295245  354294  413343  472392  531441  590490  649539  708588  767637  826686
885735 1062882 1240029 1417176 1594323 1771470 1948617 2125764 2302911 2480058

Once again, each row, except the first, every number has the same number of digits in its base 3 representation.