We created this file to test if hardware permits, if it is possible to generate a permutation of one G first G of nature numbers.
Test shows for e=30 in a single-thread mode, i7 level CPU, it took about two minutes to complete the program.
Yeh, but I am not a little bit greedy. Now I want to generate a random permutation of one T, T is 1024*G, numbers of the first T of Nature numbers, even the random is pseudo-. How can we achieve this? Or, can we achieve this with e.g. a 6-G mem laptop?
A list of exercises during the development of Recursive Random Bit Flip Permutation:
A pair of sharp eyes may already see through and catch a big hole of Recursive Random Bit Flip Permutation, but to fill the hole would seem to be easier.
It took longer time to imagine the bit-flip method. Shorter time (two or three) days finding the hole. Even shorter to imagine a way to fill the hole.
As of today, everything is still imagination, Mar 19, 2013.
In this episode, I meant to close the depth peeling transparency project and I will open the code. But I forgot to bring the code four years ago with my travel.
We will fill the hole in the coming episode(s).
We stop the topic about "Generating a Random Permutation of the First one G Nature Numbers", because "Recursive Random Bit Flip Permutation" is a different topic or just because of convenience.
I deeply worry about the completeness of the premutation created -- it may fall within particular pattern(s) of numbers.
My shallow attempt of group theory was not continuous.
At least this program struggles to provide a set or a none-repeating collection of numbers, so I would continue the analysis without requiring very high mathematics background.
How to start:
First we set size=5, generate a permutation:
In the source cpp file,
The results are a little bit confusing, but the numbers looks like a random permutation of intergers in [0,31]
Let's only show the last five bits:
For bit No.1, there is a clear bipartite pattern of 1s and 0s (as programming convention, the least bit is No.0). For each bit, there is another bit showing a bipartite pattern and the size is halved. The permutation we generate will always be in such a pattern. Definitely, we have many other patterns missing. This is not a hole, it is something porous.
If you trouble yourself by studying the program
In fact, from the begginning, we are not far from a solution.
"Recursive Random Bit Flip Permutation" clearly categorizes numbers in [0,2^n) into the tiered-bipartite hierarchy. For example, 2^40 numbers can be grouped into 1024*1024 groups.
Each group's size would be 1024*1024.
Using "Recursive Random Bit Flip Permutation", we can control which single group we want to compute. We assign the 1024*1024 groups each an index.
Then we shuffle the indices, in previous programs, we have been able to shuffle 1G numbers.
Suppose we have a cache size of 10*1024*1024 (10M unsigned long long is 80MB). Then each time we compute 10 groups of numbers and fill them in the cache.
Shuffle the cache. Carry on till all groups are processed.
For number in [0,2^n), there won't be numer(s) repeated, there won't be number(s) missed. We believe this cache-shuffle will seal the hole(s) of "Recursive Random Bit Flip Permutation".
You may argue, you can directly put 10^10 numbers to 100 groups. Shuffle the indices, shuffle the cache. Voila!
But "Recursive Random Bit Flip Permutation" definitely makes the numbers more statistically dispersed ( but easy to guess the over-all pattern).
Plus indices shuffle and cache shuffle, it is fair enough against guessing.
In the coming episode, we will try to use program to prove this idea.