Race Condition Random Seeder
20130702

Heteroclinic.net logo

www.heteroclinic.net

Generating a Random Permutation of the First one G Nature Numbers, G is 1024*1024*1024 Feasibility Analysis from Scratching and so forth
Episode III, An Implementation of Shuffling

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?

Science and Technology Promotion License Draft
Unless explicitly expressed, any material at www.heteroclinic.net should be considered as being within the realm of freedom of speech. The liablity of the owner of www.heteroclinic.net to the maximum is to modify/remove matters in dispute. The materials at www.heteroclinic.net: reliability is not guaranteed. Originality is conditionally guaranteed. You should be responsible yourself for any consequence hereby (download, executing, compilation). Redistribute 'as it is'.

There is definitely third party material involved. Zhikai will try his best to source the materials presented. But there may still be un-intentionally neglegance, insufficient documentation, improvised convenience copy introduced line-by-line string/text matched etc. Please understand that this site is just demonstrating the willingness of the builder to contribute to and promote the advancement of science and technology.

You are welcome to challenge the originality, claim license/copyright violation or point out fallacies, mistakes, un-founded-ness, seriousness-deficiency, e.g. April 1st technotes, etc. At this point, please present sound proof, prior arts etc.

For all materials at this site, all applicable licenses/rights are automatically cascaded to them from their bases. So far www.heteroclinic.net is not a commercial website so there is no economic or virtual damage to be acknowledged. Anything you want to put to commercial purpose, Zhikai is willing help you to resovle all the rights, licenses etc.

If you are interested in getting some of the source code not built together with the binaries, please contact Zhikai.
Generating a Random Permutation of the First one G Nature Numbers, G is 1024*1024*1024 Feasibility Analysis from Scratching and so forth
Episode II, a list of exercises
-- March 22, 2013

A list of exercises during the development of Recursive Random Bit Flip Permutation:
FiniteStepPermute.cpp
hash1gint.cpp
printbits.cpp
randombitflip.cpp
randombitfliputil.cpp
randombitfliputil2.cpp
RecursiveRandomBitFlipPermuationGeneration.cpp
trycatchtest.cpp
GenerateRandomNumberSet.java

Generating a Random Permutation of the First one G Nature Numbers, G is 1024*1024*1024 Feasibility Analysis from Scratching and so forth
Episode IV, we forward G to T, T is 1024*G
Recursive Random Bit Flip Permutation
-- March 22, 2013
Zhikai presents a new algorithm -- 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).

Recursive Random Bit Flip Permutation
Episode I 20130402
Will analysis find the hole, exist there holes?

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.

Recursive Random Bit Flip Permutation
Episode II 20130403
Some basic analysis

If you trouble yourself by studying the program RecursiveRandomBitFlipPermuationGeneration.cpp. You may find some of the terms I use here. For this program, we chose size=n, so we will have $2^n$ (Latex formula for 2 to the power of n) start_patterns. Given a fixed claw, the program can create $2^n$ different permutations of integers in [0,2^n). Obviously, not even requiring basic mathematical analysis like MATH30x or something, 2^n << (2^n)!. Since we use n bits, we can create n! claws. It is not rigorous to claim that function(start_pattern,claw) (it is returns a unique result, thus a function), will be the bi-jection map between a tuple(start_pattern,claw) and a permutation returned by the function. I also believe, it still holds that (2^n) * n! << (2^n)!, simple by observation, the pattern of permutation created misses a lot of other patterns. In the coming episode, we will try to fill the hole or, to say, to make the program less porous.

Recursive Random Bit Flip Permutation
Episode III 20130406
Seal with a cache -- feasibility analysis

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.