1

I'm working on algorithm that heavily uses min() function to find the smallest number of three numbers. Program is written in C/C++ language. Temporarily I use

min( number1, min(number2, number3))

But it took about 90% of CPU time. What's the fastest solution of this problem? Maybe any bitwise trick or something?

Mohit Jain
  • 30,259
  • 8
  • 73
  • 100
nosbor
  • 2,826
  • 3
  • 39
  • 63

2 Answers2

3

As long as your compiler is optimizing that's probably as good as you're going to get. 

#include <algorithm>

int test(int i, int j, int k)
{
  return std::min(i, std::min(j, k));
}

compiled with g++ -S -c -O3 test.cpp I get

cmpl    %edi, %esi
movl    %edx, %eax
cmovg   %edi, %esi
cmpl    %edx, %esi
cmovle  %esi, %eax
ret

Perhaps you didn't pass any optimization flags when compiling?

user657267
  • 20,568
  • 5
  • 58
  • 77
  • Thanks for reply. I used optimization and code is the same as your but despite it, it is still the most heavy used function. Maybe I should try change logic of algorithm... – nosbor Apr 18 '14 at 19:59
1

Check this solution if it helps you

quoting below code from above reference

int x;  // we want to find the minimum of x and y
int y;   
int r;  // the result goes here 

r = y ^ ((x ^ y) & -(x < y)); // min(x, y)

One more trick under same heading is

r = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // min(x, y)

You can remove -1 from trick 2. It works only on some systems and is not portable.

You can extend this idea to find minimum of 3 numbers.

static inline int min3(int x, int y, int z)
{
  register int r, d;
  d = x - y;
  r = y + (d & (d >> (sizeof(int) * CHAR_BIT))); /* add -1 if required */
  d = r - z;
  r = z + (d & (d >> (sizeof(int) * CHAR_BIT))); /* add -1 if required */
  return r;
}

If range of your numbers is very less, you can even use some look up, or more efficient but hack.

Mohit Jain
  • 30,259
  • 8
  • 73
  • 100
  • 2
    You really can't beat the compiler with these simple operations, your code ends up having 11 instructions in assembly vs 5 for `std::min(x, std::min(y, z));` – user657267 Apr 18 '14 at 05:23