22

This recent code golfing post asked the possibilities of fast implementation in C the following (assuming n is an unsigned integer):

if (n==6 || n==8 || n==10 || n==12 || n==14 || n==16 || n==18 || n==20)

One possible simplification is to observe that the numbers a[]={6,8,10,12,14,16,18,20} form an arithmetic progression, so shifting the range and then using some bitwise tricks

if (((n - 6) & 14) + 6 == n)

leads to a shorter (and probably indeed more efficient) implementation, as answered by John Bollinger.

Now I am asking what is the analogously elegant (and hopefully equally efficient) implementation of

if (n==3 || n==5 || n==11 || n==29 || n==83 || n==245 || n==731 || n==2189)

Hint: this time the numbers a[k] form a geometric progression: a[k]=2+3^k.

I guess in the general case one cannot do better than sort the numbers a[k] and then do a logarithmic search to test if n is a member of the sorted array.

10
  • 12
    if this is a time over space tradeoff then I would allocate a 2189 words buffer filled with zeros except for the specific locations (3, 5, 11 etc...) and simply perform an array lookup (which is extremely quick since it is hardware implemented). This is not very elegant but will give you top time performance with the cost of space performance. May 2, 2016 at 7:45
  • 2
    Shouldn't such questions be posted on codereview.stackexchange.com?
    – CinCout
    May 2, 2016 at 7:58
  • 2
    FWIW, ((n - 6) & 14) + 6 == n can be simplified to (n - 6) | 14 == 14. May 2, 2016 at 8:08
  • 3
    @UriBrecher - For 2k values, maybe. For the general case, the impact of a huge lookup table on cache is probably not negligible. May 2, 2016 at 12:08
  • 2
    Are you going for raw speed, or elegant-looking C code? They are likely to be different. Division (including modulo) operations are about the slowest operations there are on modern processors, so thiru's answer looks cool, but likely won't be faster than a series of comparisons. Check your compiler's output and benchmark before making a decision, if you actually do care about speed. Also consider that branches are slow in tight loops. If your optimizer isn't smart enough to do this substitution automatically (Clang is, others aren't), consider using bitwise OR instead of logical OR. May 2, 2016 at 14:26

6 Answers 6

25
if ((n > 2) && (2187 % (n - 2) == 0))

Checks if (n - 2) is a power of 3 and is less than or equal to 2187 (3 to the power of 7)

As a generalization, to check if any unsigned integer n is a power of prime number k, you can check if n divides the largest power of k that can be stored in an unsigned integer.

10
  • 1
    It's a nice answer, but you should change "less than or equal to 2187" to "less than or equal to 2189". Also, you should add a preliminary verification of n > 2. May 2, 2016 at 8:10
  • 2
    @thiru Great work! (I can confirm via testing that your solution is correct and is faster (1.14703 ns, compared to 3.34201 ns)
    – Isaac
    May 2, 2016 at 8:40
  • 3
    Beware that division operations (including modulo) are basically the slowest instructions there are on modern processors, far slower than comparisons. So although this is a neat way to write the code (and granted, exactly the answer the asker was looking for), it is probably not the fastest code. May 2, 2016 at 14:31
  • 3
    @CodyGray 32-bit integer division is much slower than comparison, but should be faster than a single mispredicted jump May 2, 2016 at 17:27
  • 2
    Let's accept this as being analogously elegant. I thank you for your answer.
    – Matsmath
    May 3, 2016 at 7:37
8

This is very similar to recognizing a power of three, and you can adapt for example this solution:

bool test(unsigned x) {
    x -= 2;
    if (x > 2187)
        return 0;
    if (x > 243)
        x *= 0xd2b3183b;
    return x <= 243 && ((x * 0x71c5) & 0x5145) == 0x5145;
}

With the given range, this can be further simplified (found by brute force):

bool test2(unsigned x) {
  x -= 2;
  return x <= 2187 && (((x * 0x4be55) & 0xd2514105) == 5);
}
1
  • 2
    Heck, this is some good stuff here. Could you elaborate in a few lines how you got from the "basic" version to the "advanced" version? What is the big idea here?
    – Matsmath
    May 3, 2016 at 9:53
5

Hint: this time the numbers a[k] form a geometric progression: a[k]=2+3^k.

n = 2 + 3^k
n - 2 = 3^k

(n - 2) / 3^k = 1
(n - 2) % 3^k = 0

k = 0 ~ n-2 = 3^0 = 1, n = 3
k = 1 ~ n-2 = 3^1 = 3, n = 5
k = 2 ~ n-2 = 3^3 = 9, n = 11

if (n > 2 && isPow(n-2, 3))

with definition of function isPow(x,y)

bool isPow(unsigned long x, unsigned int y)
{
    while (x % y == 0)
    {
        x /= y;
    }

    return x == 1;
}

n = n  ~ n-2 = 3^k/3 = 3^(k-1)/3 = .. = 3^1/3 = 1%3 != 0
n = 11 ~ n-2 = 9/3 = 3/3 = 1%3 != 0
n = 5  ~ n-2 = 3/3 = 1%3 != 0
n = 3  ~ n-2 = 1%3 != 0

Similiarly we can deduct k..

int k = findK(n-2, 3);

int findK(unsigned long x, unsigned int y)
{
    unsigned int k = 0;

    while (x % y == 0)
    {
        x /= y;
        k++;
    }

    if (x == 1) return k;
    else return (-1);
}

n - 2 = 3 * 3^(k-1)       for k > 0
(n - 2) / 3 = 3^(k-1)
(n - 2) / 3 / 3 = 3^(k-2)
(n - 2) / 3 / 3 / 3 = 3^(k-3)
(n - 2) / 3 / 3 / 3 / 3 = 3^(k-4)
..
(n - 2) / 3 / 3 / ..i times = 3^(k-i)
..
(n - 2) / 3 / 3 / ..k times = 3^0 = 1
4
  • 1
    Has the same time complexity as linear search. May 2, 2016 at 10:24
  • @n.m. I was going for the analogously elegant
    – Khaled.K
    May 2, 2016 at 11:04
  • In your first code: why do you move the 3* to the left become a / 3 and at the next step you move it right again and move left the 3^(k-1) term? Also you repeated the equation (n - 2) % 3^k = 0 twice.
    – Bakuriu
    May 2, 2016 at 13:14
  • @Bakuriu yes the repeated equation is a typo, the 3 and 3^(k-1) swapped to show off how to apply (n - 2) % 3^k = 0 in the function isPow(x,y)
    – Khaled.K
    May 2, 2016 at 15:50
3

Found a similar problem in a related post: You can use std::find

bool found = (std::find(my_var.begin(), my_var.end(), my_variable) != my_var.end());
// my_var is a list of elements.

(make sure you include <algorithm>).

For this kind of stuff, in 99% of cases, there is a library that does the job for you.

9
  • 2
    std::find has linear runtime. I don't think that would count as the fastest implementation possible...
    – Jens
    May 2, 2016 at 8:02
  • 2
    For 8 values, this may well be fast - many CPUs have a repeated-compare operation with a counter to limit the amount of data searched, and it's not much data to cache. I wouldn't be at all surprised if this outperformed a binary search. May 2, 2016 at 8:15
  • 1
    @TonyD I think there was a presentation on one of the C++ conferences where it was actually measured and the linear search is faster for small sets. However, the question also asks for the general case, and he is counting assembler instructions. In this artificial case, I don't think a linear search qualifies.
    – Jens
    May 2, 2016 at 8:56
  • 3
    @Matsmath In this profession we operate with facts, not feelings. May 2, 2016 at 10:25
  • 4
    @Matsmath Why would including a library compromise performance? The function call will probably be inlined anyway. The performance will not be different than a hand-written loop.
    – Jens
    May 2, 2016 at 10:28
3

One very efficient way to do this sort of thing is with a set, especially an unordered_set. As a hash table, search is average constant, worst linear. It is also much more elegant than a string of conditions and scales well.

Simply insert the values you want to compare against, and count the value in the set. If it is found, it's one of your tested values.

std::unordered_set< int > values;
values.insert( 3 );
values.insert( 5 );
values.insert( 11 );
values.insert( 29 );
values.insert( 83 );
values.insert( 245 );
values.insert( 731 );
values.insert( 2189 );

...

if( values.count( input ) )
    std::cout << "Value is in set.\n";
else
    std::cout << "Value is NOT in set.\n";
4
  • 2
    I like this approach to the problem. What continues to surprise me is that here you don't exploit the structure of the numbers, that is, the fact that they are not just some random numbers, but they form a geometric progression. You claim here that this enormous information has no impact whatsoever on performance, which, of course, could be true, but it is something that looks counter-intuitive to me.
    – Matsmath
    May 2, 2016 at 14:27
  • @Matsmath Well, there's implicitly another equally important piece of information about these numbers that exploiting the mathematical progression ignores: how they impact the hashing function, and thus how they are handled in the set. That said, you might be able to exploit the series progression in writing a custom hashing function; that might allow collisions to be eliminated entirely and thus force constant search. However, that's mostly an academic observation, I don't think anyone would ever do that for this sort of thing.
    – user3995702
    May 2, 2016 at 14:44
  • @WilliamKappler I disagree with your last comment sentence: en.wikipedia.org/wiki/Perfect_hash_function. There are rare cases, when this is needed.
    – maaartinus
    May 2, 2016 at 16:18
  • Let me clarify, by "this sort of thing" I meant using one in the context of replacing a chained conditional, rather than custom hash functions as a whole. It would seem really excessive to write a custom hash function for around 10 elements. But there's definitely cases where custom functions are helpful in a broader context.
    – user3995702
    May 2, 2016 at 16:21
0

Here's what I came up with:

bool b;
if (n >= 3 && n <= 2189)
{
    double d = std::log(n - 2)/std::log(3); // log₃(n - 2)
    b = std::trunc(d) == d; // Checks to see if this is an integer
    // If ‘b’ then ‘n == a[log₃(n - 2)]’
}
else b = false;

if (b)
{
    // your code
}

As the number n is a small integer, floating point inaccuracies shouldn't be a problem.

Ofcourse it won't be as fast as integer arithmetic, an it doesn't fit snuggly in an expression, it is probably faster than some kind of array search, especially if you where to increase the maximum n value.

EDIT I tested my code (without optimizations enabled) and on average (for all n less than or equal to 2189) my version took 185.849 ns wheras the || version took 116.546 ns, (running my program multiple times yielded similar results) so this is not faster. Also for some bizarre reason, it sets b to false when n == 245, (it should be true).

6
  • 1
    What if n < 2? BTW, computing a single log probably takes more than the original expression. At least for log(3), since the question is about performance, you should probably maintain it in a static variable (i.e., compute it only once). May 2, 2016 at 7:54
  • @barakmanos thanks I fixed that. Hmm, I didn't think of that, perhaps I'll test it...
    – Isaac
    May 2, 2016 at 7:57
  • Second thought, log with negative probably returns -inf of NaN, in which case, the test that follows will probably work. May 2, 2016 at 7:59
  • static double log3 = std::log(3). May 2, 2016 at 7:59
  • 3
    Why are you testing it without the optimisations? That pretty much makes the whole point of which one is faster moot.
    – Davidmh
    May 2, 2016 at 10:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.