What is the problem addressed by the paper? How to represent smooth shapes? How to smooth surfaces? How to process range-scanned meshes? How to improv normal and boundary continuity? image credit Alexa, et al. What is the approach used to resolve the problem? In differential geometry, a smooth surface is characterized by the existence of smooth…
[Summary] The One Hundred Year Study on Artificial Intelligence: An Enduring Study on AI and its Influence on People and Society
Today, technical fellow and director at Microsoft, Dr. Horvitz gave a lecture on The One Hundred Year Study on Artificial Intelligence: An Enduring Study on AI and its Influence on People and Society; I am also fortunate to have a lunch together with Eric. He has presented an update on the One Hundred Year Study on AI, described…
Fisher-Yates Shuffle
The correct way to do a shuffle is to choose a random other index to fill in the current index, which is uniform:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
function getRandom(floor, ceiling) { return Math.floor(Math.random() * (ceiling - floor + 1)) + floor; } function shuffle(theArray) { // if it's 1 or 0 items, just return if (theArray.length <= 1) return; // walk through from beginning to end for (var indexWeAreChoosingFor = 0; indexWeAreChoosingFor < theArray.length; indexWeAreChoosingFor++) { // choose a random not-yet-placed item to place there // (could also be the item currently in that spot) // must be an item AFTER the current item, because the stuff // before has all already been placed var randomChoiceIndex = getRandom(indexWeAreChoosingFor, theArray.length - 1); // place our random choice in the spot by swapping var valueAtIndexWeChoseFor = theArray[indexWeAreChoosingFor]; theArray[indexWeAreChoosingFor] = theArray[randomChoiceIndex]; theArray[randomChoiceIndex] = valueAtIndexWeChoseFor; } } |
Also, you may need a uniform random generator in C++:
|
1 2 3 4 5 6 7 |
#include <random> std::random_device rd; std::mt19937 mt(rd()); std::uniform_real_distribution<double> uniform_random(0.0, 1.0); // use as sample = uniform_random(mt); |
Protected: Optimization Using Sum-to-Product Identities
There is no excerpt because this is a protected post.
Likert Scale and Paired T-Test Are Not Good Friends
Non-parametric Tests Unfortunately, it’s the first time that I learnt that Likert scale cannot be used together with t-test. According to my favorite Stat Wiki by Prof. Koji Yatani, Roughly speaking, there are two cases in which you want to use non-parametric test: Ordinal data: If your data are ordinal (like the results from Likert-scale…
What are PCA and FLA / LDA?
PCA The main idea of PCA is to seek the most accurate data representation in a lower dimensional space. For a formal definition, according to Wikipedia, Principal component analysis (PCA) is a statistical procedure that uses an orthogonal transformation to convert a set of observations of possibly correlated variables into a set of values of…
What is P value?
P value is the probability that you are wrong if you reject the null hypothesis. or P value is the probability that you get equal or worse result if your experiment is right… or according to Wikipedia: For example, if you propose a hypothesis that Trump has more positive tweets than Hillary has, the your…
N Queens Problem Revisit using Bit Operations
Finally, I have some time to revisit the N queens problem using bit operations. The following functions could solve 11 queens in 1 second:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
class Solution { public: vector<vector<string>> solveNQueens(int n) { NQresult.clear(); NQpath.clear(); NQn = n; NQtotal = 0; bitNQueens(0, 0, 0); cout << NQtotal << endl; return NQresult; } private: /** [Q..... row = 101010 ..Q... ld = 100100 ....Q. rd = 000111 ......] or = 101111 pos = 010000 => p = (010000) & (110000) = 010000 => pos = 0; [Q..... row = 111010 ..Q... ld = 011000 ....Q. rd = 000111 .Q....] **/ vector<vector<string>> NQresult; vector<int> NQpath; int NQtotal; int NQn; void addNQueenSolution() { vector<string> v; for (int i = 0; i < NQn; ++i) v.push_back(string(NQn, '.')); for (int i = 0; i < NQn; ++i) { v[i][NQpath[i]] = 'Q'; //cout << v[i] << endl; } //cout << endl; NQresult.push_back(v); } // col: whether this col is occupied // ld: left diagnal for the current row // rd: right diagnal for the current row void bitNQueens(int col, int ld, int rd) { int allOccupied = (1 << NQn) - 1; if (col == allOccupied) { ++NQtotal; addNQueenSolution(); return; } int pos = allOccupied & (~(col | ld | rd)); while (pos != 0) { int p = pos & (-pos); // which way to go pos = pos - p; // get the rightmost 1 of position position NQpath.push_back(p == 1 ? 0 : (int)round(log(p) / log(2))); bitNQueens(col + p, (ld + p) << 1, (rd + p) >> 1); NQpath.pop_back(); } } }; |
So far to me, this is the most efficient algorithm for N queens. The code is mostly self-explenary. Please comment if anything cannot be understood.
|
1 2 3 |
// col: whether this col is occupied // ld: left diagnal for the current row // rd: right diagnal for the current row |
Simplest and Fatest GLSL Edge Detection using Fwidth
GLSL Edge Detection Yesterday, I read 834144373’s ShaderToy code which did GLSL Edge Detection in 97 chars, it was really simple and fast:
|
1 2 3 4 |
void mainImage(out vec4 o, vec2 u) { o -= o - length(fwidth(texture2D(iChannel0,u/iResolution.xy)))*3.; } |
Meanwhile, the rendering result is astonishingly awesome: However, there are some noise from the GLSL edge detection. Thus, I have made a little improvement on this algorithm and produced cleaner edges in this ShaderToy…
Testing GPUs Computational Power
Have you think of how many summation & multiply operations can you do within for-loops in GPU fragment shader? I irrigorously tested the following fragment shader on ShaderToy, which gives me 100,000 operations at 22 FPS on a GTX 1080, for 25, 000 operations, it runs smoothly at 60 FPS. So, what’s the limitation of…
Slideshow
