Computer Vision News - November 2016

Every month, Computer Vision News shows you a nice trick that will make your work easier. This time, our engineers will tell you about review a novel trick by Daniel Lemire , published on his blog and concerning fast module operation . This trick was recently included in the Google deep learning package TensorFlow, boosting its performance by 10-20% ( see here ) . Keep reading and you will see why. Random, random, random... Random numbers are everywhere: Algorithm developers are using random numbers in many situations such as in hash tables, the Monte Carlo method and the RANSAC algorithm, to name just a few. Since random numbers are so frequently used, the efficiency of generating them is critical for the performance of many algorithms. When generating random numbers, typically there is a function that can generate a 32bit random number, but how do you convert this 32bit number into your desired integer in the range of 0..N ? Several solutions exist: if N is a power of two this is easy, all you need to do is just shift the number by the desired bit number. In cases where N is not a power of 2, it can be approximated by using floor(2 32 /N) - when N is small this approximation is not bad. However, what do you do when N is large? A solution for this could be to use the module operator. Module solution is a fair solution with a small bias toward preferred small numbers. The main drawback of the module operator is that it is expensive, since it involves divisions which are expensive operations for a CPU. For instance, on the latest 64bit processor (Skylake) division involved six clock cycles with latency of 26 cycles. While multiplication involved one cycle with latency of 3 cycles. No doubt multiplications are preferable to divisions. Can we (somehow) perform the module operation using multiplication instead of divisions? Yes! If your N is smaller than the 32bit number and you are using a 64bit processor, as it is in the vast majority of cases. Then you can use this simple and efficient function: 10 Computer Vision News Trick Fast Module Operation Trick