www.heteroclinic.net

 Introduction of www.heteroclinic.net Brief Www.heteroclinic.net is the personal home page of Zhikai Wang. Zhikai holds a master degree of computer science from Concordia University, Canada. You can consult Zhikai for general issues related to computer science and software engineering. Zhikai specilizes in: - concurrent programming - network programming - computer graphics (3D) - general enterprise IT solutions Zhikai's brain mountaineering: -In Depth 3D Computer Graphics -Tiny CSV Reader: some experimenting code to parse CSV FILE -Bunny: 3D Computer Graphics OpengGL C/C++ (live) -QTPlaut -MatPlaut -Android Mobile + Facebook API -Magic Hexagon -the Lorenz System -the CR3BP -Depth Peeling Transparency (Merged to Bunny) -Real Time Caustics (Merged to Bunny) -Mesh Simplification (Merged to Bunny) -Age of Concordia -Battleship (live) -Cobag -Runtime Deadlock Detection (closed and transferred to treetor/jdfr bundle)- -Concurrency Basics(live) -QtWagon -- study 3D objects with QT GUI -Race Condition Random Seeder -Treetor: tree visualization tool and JDFR -Recursive Random Bit Flip Permutation -Project Friends Torus: Social Network in a new Dimension (live) -Project Sinpixa: Zhikai's Composite Number Equation (live) -Foaken, a mini project about Facebook Login API for Java Desktop Application, based on NanoHTTPD -Two-pass 3D Object and Mouse Collision Detection -Preemptive Overflow Prevention -Functional Programmatic Combinatorics -Light Jsd: Light-weight Java httpd context for Javascript Functional Programatic Combinatorics IIK-Combination20141015 Functionally program K-combination. package net.heteroclinic.experiment.lambdatest; import java.util.ArrayList; import java.util.List; /** * @author Zhikai Wang/www.heteroclinic.net * This class is an example/exercise to provide a code base to compute k-combinations of a set, using functional programming features. * Given third party license acknowledged and this header kept or quoted, you can utilize this program at will. * Juggling elements among: * [spared][selected][remaining] */ public class LambdaChooseSpareCombination { public interface ListPrintor { public boolean print (List l, int segmentLength); } public interface Reeper { public boolean harvest(ListPrintor listPrintor, List spared, List choices, List remaining, int K); } public interface KCombination { // Juggling elements among: [spared][selected][remaining] public void juggle ( Reeper r,ListPrintor listPrintor,List spared, List choices, List remaining, int K); } public static void main(String[] args) { List a = new ArrayList(); for (int i = 1; i<=5 ; i++) { a.add(i); } ListPrintor lPrintor = (l,s)-> new Object () { public boolean run (List l, int segmentLength) { for (int i:l) System.out.print(i+ " "); System.out.println(); return true; } }.run(l,s); Reeper reeper = (l,s,c,r,k) -> new Object () { public boolean run (ListPrintor listPrintor,List spared, List choices, List remaining, int K ) { if ( choices.size() >= K ) { // Print choices listPrintor.print(choices,K); return true; } else if ( remaining.size() <= K - choices.size()) { // Print remaining + choices List pl = new ArrayList(); pl.addAll(choices); pl.addAll(remaining); listPrintor.print(pl,K); return true; } return false; } }.run(l,s,c,r,k); KCombination kComb = (r,p,s,c,m,k) -> new Object () { public void choose ( Reeper r,ListPrintor listPrintor,List spared, List choices, List remaining, int K) { if (r.harvest(listPrintor, spared, choices, remaining, K)) return; // For the first element of the remaining if ( remaining.size() <= 0) return; int firstOfRemaining = remaining.get(0); // Choose it, call choose to pick one more choices.add(firstOfRemaining); remaining.remove(new Integer(firstOfRemaining)); List ns = new ArrayList(); ns.addAll(spared); List nc = new ArrayList(); nc.addAll(choices); List nr = new ArrayList(); nr.addAll(remaining); choose ( r, listPrintor,ns,nc, nr, K); // Spare it, call choose to pick one more spared.add(firstOfRemaining); choices.remove(new Integer(firstOfRemaining)); ns = new ArrayList(); ns.addAll(spared); nc = new ArrayList(); nc.addAll(choices); nr = new ArrayList(); nr.addAll(remaining); choose ( r, listPrintor, ns,nc, nr, K); } }.choose(r,p,s,c,m,k); kComb.juggle(reeper, lPrintor, new ArrayList (), new ArrayList (),a, 3); } } Safe Integer Addition Analysis20140629 For the addition of two integers a and b, we know how to safely predict an overflow instance. For two integers addition, the carry will be exactly 1, the remainder is a- (M - b + 1), for a >= b > 0; if b is 0, there won't be overflow. Preemptive Overflow Prevention IIA Fundamental Mathematical Analysis20140528 To simplify the problem, we only deal with unsigned integers. I.The mathematical condition for sum overflow: A + B > M <=> M - A < B. The right hand side operation will not cause an overflow, but the left hand side may cause an overflow. A and B are the sum operands and unsigned integers. M is the max value below overflow. II.The mathematical condition for multiplication overflow: A and B are the multiplication operands and unsigned integers. If A is equal to 0, there will not be overflow. Otherwise, A * B > M <=> M / A < B. M is the max value below overflow. Similarly, the RHS of the equivalence formula is overflow safe. Race Condition Random Seeder 20130917 Introduction: Race Condition Random Seeder is a tool aiming to create random seeds for random generators. It utilizes modern computer systems' high frequency CPU clock and multitasking in paralell features. By creating man-made race condition, we retrieve a volatile boolean value that threads race upon. The values retrieved thus form a bit-bundle representing a numerical value. We can say, we can achieve to some degree true random, or software random, in an isolated system. Such system is like modern computer system, having two or more independent computing units. So I may say you may let a computer do something all by itself, in some degree (to a great degree) independent of the environment. In release R-2.0 (C/C++), we no longer utilize any mem* ops, but utilize well-implemented ADTs. The aim is to return a Bitset or std::string, so the users can parse the bit-bundle to the built-in numerical types. This practice seems to increase the chance of survival of this program. In release R-2.2 (Java), we tried to repeat the same principle we did in C/C++ in Java. The effect is not quite satisfying by observation. In my experiments, we have to force the threads sleep/context switch to add the entropy. Mainly, this should relate particularly to JVM thread slicing settings. By observation, it causes a single thread dominate the shared flip. In C++/C test, forcing threads to sleep/context switch thus yielding each other is not necessary. We have to mention, the particular setting shown as below worked at a particular combo of OS, JVM and hardware. You can tune the parameters so the results can be statistically satisfying. Note: forcing the threads to sleep/context switch thus yielding each other significantly drags down the performance. In contrast in C++/C test, forcing threads to sleep/context switch thus yielding each other is not necessary (it is a given combo of conditions leading to this observation). Again, you can find some key parameters to tune with by studying the source code. This program due to its nature will not be of high performance. It is suggested to be used as a seeder program for other random generators, e.g. linear congruential random generator etc. Release 2.0 (C/C++) how-to in Cygwin/Linux/UNIX shell console (pthread lib required): Download/compile/execute RaceConditionRandomSeederR2d0BitsetImpl.cpp wget www.heteroclinic.net/attached/RaceConditionRandomSeederR2d0BitsetImpl.cpp g++ -o RaceConditionRandomSeederR2d0BitsetImpl.exe RaceConditionRandomSeederR2d0BitsetImpl.cpp -lpthread ./RaceConditionRandomSeederR2d0BitsetImpl.exe Release 2.2 (Java): The effect is not quite satisfying by observation. /* Science and technology promotion license applied (third-party licenses/rights auto-cascaded, free usage of this program for non-commercial purposes, the liability of Zhikai Wang/ www.heteroclinic.net is to remove/modify matters in dispute) (c) Zhikai Wang/ www.heteroclinic.net 2013 */ /* Introduction: Race Condition Random Seeder Release is a tool aiming to create random seeds for random generators. It utilizes modern computer systems' high frequency CPU clock and multitasking in paralell features. By creating man-made race condition, we retrieve a volatile boolean value that threads race upon. The values retrieved thus form a bit-bundle representing a numerical value. We can say, we can achieve to some degree true random, or software random, in an isolated system. Such system is like modern computer system, having two or more independent computing units. So I may say you may let a computer do something all by itself, in some degree (to a great degree) independent of the environment. In this release R-2.2, we tried to repeat the same principle we did in C/C++ in Java. The effect is not quite satisfying by observation. In my experiments, we have to force the threads sleep/context switch to add the entropy. Mainly, this should relate particularly to JVM thread slicing settings. By observation, it causes a single thread dominate the shared flip. In C++/C test, forcing threads to sleep/context switch thus yielding each other is not necessary. We have to mention, the particular setting shown as below worked at a particular combo of OS, JVM and hardware. You can tune the parameters so the results can be statistically satisfying. Note: forcing the threads to sleep/context switch thus yielding each other significantly drags down the performance. In contrast in C++/C test, forcing threads to sleep/context switch thus yielding each other is not necessary (but again, it is a given combo of conditions). Again, you can find some key parameters to tune with by studying the source code. This program due to its nature will not be of high performance. It is suggested to be used as a seeder program for other random generators, e.g. linear congruential random generator etc. */ import java.util.ArrayList; import java.util.BitSet; import java.util.List; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Future; import java.util.concurrent.TimeUnit; import java.util.concurrent.atomic.AtomicLong; public class RaceConditionRandomSeederR2d2JavaImpl { public static final int nooftasks =4; // In my experiments, we have to force the threads sleep/context switch to add the entropy. // Mainly, this should relate particularly to JVM thread slicing settings. By observation, it causes a single thread dominate the shared flip. // In C++/C test, forcing threads to sleep/context switch thus yielding each other is not necessary. // We have to mention, for the particular setting as below, worked at a particular combo of OS, JVM and hardware. // We can say, we can achieve to some degree true random, or software random, in an isolated system. // Such system is like modern computer system, having two or more independent computing units. // So I may say you may let a computer do something all by itself, in some degree (to a great degree) independent of the environment. // You can tune the parameters so the results can be statistically satisfying. // Note: forcing the threads to sleep/context switch thus yielding each other significantly drags down the performance. // In C++/C test, forcing threads to sleep/context switch thus yielding each other is not necessary. public static final long racerSlice = 10l; //Micro seconds public static final long anchorSlice = 100l; //Micro seconds public static CountDownLatch latch = new CountDownLatch(nooftasks); public static volatile boolean shared = false; protected static List results ; public static synchronized List getResults(){ if (null == results) results = new ArrayList(); return results; } public static String incarnateBitsetviaByte (BitSet bs, String separator) { return incarnateBitsetviaByte (bs, separator, -1); } public static String incarnateBitsetviaByte (BitSet bs, String separator,int totalBytesUseingForAlign) { String result =""; int i = 0; byte[] barr = bs.toByteArray(); if (separator != null && separator.length() > 0) { for (i=barr.length-1; i>=0; i--) { String str = Integer.toBinaryString( 0xff & barr[i]); result += str.length()= 2 && result.substring(result.length() - separator.length(), result.length()).equals(separator)) { result = result.substring(0,result.length() - separator.length()); } } else { for (i=barr.length-1; i>=0; i--) { String str = Integer.toBinaryString( 0xff & barr[i]); result += str.length() 0) { for (i=0; i< totalBytesUseingForAlign; i++) { String str = Integer.toBinaryString( 0); larger += str.length()= 2 && larger.substring(larger.length() - separator.length(), larger.length()).equals(separator)) { larger = larger.substring(0,larger.length() - separator.length()); } } else { for (i=0; i< totalBytesUseingForAlign; i++) { String str = Integer.toBinaryString( 0); larger += str.length()= 2, args[0] represents bit-length, * args[1] represents the number of bit-bundles you need. * You can call the main directly in Another function. * Like RaceConditionRandomSeederR2d2JavaImpl.main(64,1024), then access * the public static List results which buffered the bits bundles. */ public static void main(String[] args) { int bundleLength = 128; int totalBundles = 64; try { if (args.length >= 2) { bundleLength = Integer.parseInt(args[0]); totalBundles = Integer.parseInt(args[1]); } } catch (Exception e) { bundleLength = 64; totalBundles = 32; } List tasks = new ArrayList(); List> fl = new ArrayList>(); ExecutorService exec = Executors.newCachedThreadPool(); for (int i = 0; i < nooftasks; i++) { tasks.add(new Task()); } for (Task t : tasks) { fl.add(exec.submit(t)); } try { latch.await(); } catch (InterruptedException e) { e.printStackTrace(); } try { TimeUnit.MICROSECONDS.sleep(1000); } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } for (int i = 0; i < totalBundles; i++) { BitSet bs = new BitSet(); for (int j = 0 ; j < bundleLength; j++) { try { TimeUnit.MICROSECONDS.sleep(anchorSlice); } catch (InterruptedException e) { // e.printStackTrace(); } bs.set(j,shared); } getResults().add(incarnateBitsetviaByte(bs,"-", bundleLength%Byte.SIZE==0 ? bundleLength/Byte.SIZE: bundleLength/Byte.SIZE + 1 )); } // There are various ways to stop the Task threads. // It is resembling brake and full stop a car or similar mechanical devices. for (Future f : fl) { f.cancel(true); while (!f.isDone()) ; } Shared.halted = true; exec.shutdown(); System.out.println("Show buffered results."); for (String s: getResults()) { System.out.println(s); } System.out.println("End of main."); } } Jdfr and Treetor Quick-Starts Timestamp 201302 We relase jdfr1.0.jar and treetorplus3.jar in January, 2013. Introduction: - treetor, a tree/forest rendering tool - jdfr, Java Dead-lock Free Runtime (the goal, may be too ambitious) Features: - the bundle fully supports Java ReentrantLock - treetor can render a tree graph or forest graph with some dozens of thousand nodes - so far, the bundle only runs with JDK/JRE 7. - check the blog sections for more details. Download: wget http://www.heteroclinic.net/attached/jdfr1.0.jar wget http://www.heteroclinic.net/attached/treetorplus3.jar Quick-starts: Linux java -cp treetorplus3.jar;jdfr1.0.jar javax.util.concurrent.profilable.test.Test20130120_MultiTier .\ or Windows java -cp treetorplus3.jar:jdfr1.0.jar javax.util.concurrent.profilable.test.Test20130120_MultiTier ./ It will create ".png"s in the current directory. Multi-tier java -cp treetorplus3.jar;jdfr1.0.jar javax.util.concurrent.profilable.test.Test20130120_MultiTier .\ Fast java -cp treetorplus3.jar;jdfr1.0.jar javax.util.concurrent.profilable.test.Test20130120_Fast .\ Random java -cp treetorplus3.jar;jdfr1.0.jar javax.util.concurrent.profilable.test.Test20130121_Random .\ Simple dead-lock profiled java -cp treetorplus3.jar;jdfrbeta01.jar javax.util.concurrent.profilable.test.Test20121210_DEAD_LOCK_VISUAL .\ Generating a Random Permutation of the First one G Nature Numbers, G is 1024*1024*1024 Feasibility Analysis from Scratching and so forthEpisode 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. wget www.heteroclinic.net/attached/RecursiveRandomBitFlipPermuationGeneration.cpp g++ -o RecursiveRandomBitFlipPermuationGeneration.exe RecursiveRandomBitFlipPermuationGeneration.cpp ./RecursiveRandomBitFlipPermuationGeneration.exe /* Science and technology promotion license applied. (c) Zhikai Wang/ www.heteroclinic.net 2013 */ /* results: $g++ -o RecursiveRandomBitFlipPermuationGeneration.exe RecursiveRandomBitFlipPermuationGeneration.cpp$ ./RecursiveRandomBitFlipPermuationGeneration.exe It took 25.849 seconds for size=30. So theoretically for size = 40 (forty bits) will take 25.84 * 1024 seconds, namely ABT 5,000 minutes. My 6G/Q9000/Vista Cygwin laptop can do it. You print the result for small value of variable 'size', e.g., 5, 4 etc. */ #include #include #include #include #include #include #include // ULLONG_MAX should be 2^64-1 = 1.8446744073709551615e+19 // 20! is 2.43290200817664e+18 // 21! is 5.109094217170944e+19 //overflow // So it is not possible to use index permutation, we still need shuffling. // c is the length void printULLinBits (unsigned long long start_pattern) ; void shuffleAnArray (int c, int * myarray) { //srand(3); int array_i=0; for (array_i=0; array_i < c-1 ; array_i++) { int v = rand() % (c -array_i); //std::cout<<"v:"<= c) continue; int tmp = myarray[cursor ]; myarray[cursor ] = myarray[array_i]; myarray[array_i] = tmp; } } //std::cout<=1 && position <= 64 // I am not sure about the endianness of bit OPs inline void flipOneBitofAULL (unsigned long long * p_start_pattern, int position) { (*p_start_pattern) ^= 1 << (position-1); } // inline void flipOneBitofAULL (unsigned long long * p_start_pattern, int position) { // int spi = position; // //unsigned long long start_pattern = ULLONG_MAX; // unsigned long upper_pattern = 0LL; // unsigned long lower_pattern = 0LL; // //memcpy(&lower_pattern, &start_pattern, sizeof lower_pattern); // //memcpy(&upper_pattern, (char *) &start_pattern + sizeof lower_pattern, sizeof upper_pattern); // memcpy(&lower_pattern, p_start_pattern, sizeof lower_pattern); // memcpy(&upper_pattern, (char *) p_start_pattern + sizeof lower_pattern, sizeof upper_pattern); // if ( spi < 32 ) { // lower_pattern &= ~(1 << spi); // memcpy(p_start_pattern, &lower_pattern, sizeof lower_pattern); // } else { // upper_pattern &= ~(1 << (spi-32)); // memcpy( (char *) p_start_pattern + sizeof lower_pattern,&upper_pattern, sizeof upper_pattern); // } // std::cout<= currentdepth > 1s // If you pet something with claw(s), other things' pattern(s) may be changed. void recursiveRandomBitsFlipPermute(unsigned long long * p_start_pattern, int totaldepth, int currentdepth, int * claw, bool printdeepest ) { if ( currentdepth < totaldepth) { //std::cout<<"currentdepth "< 0 ) { //std::cout<<"\t\t"<< * p_start_pattern<<"\t claw"< 0 ) { //std::cout<<"\t\t"<< * p_start_pattern<<"\t claw"< bsup(upper_pattern); std::bitset<32> bslo(lower_pattern); std::cout<