20130702

*www.heteroclinic.net*

Episode III, An Implementation of Shuffling

**W**e 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?

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.

Episode II, a list of exercises

-- March 22, 2013

**A** list of exercises during the development of Recursive Random Bit Flip Permutation:

Episode IV, we forward G to T, T is 1024*G

Recursive Random Bit Flip Permutation

-- March 22, 2013

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).

Episode I 20130402

Will analysis find the hole, exist there holes?

**W**e 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.

Episode II 20130403

Some basic analysis

**I**f you trouble yourself by studying the program

Episode III 20130406

Seal with a cache -- feasibility analysis

**I**n 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.