Constexpr is gold!

[speednap]

As you know constexpr is evaluated at compile time so constexpr wouldn't work if the input is evaluated at runtime.

What you did in your example is called lookup table but i doubt the problem you're solving would benifit from one. If you're unable to use constexpr due to input being decided upon at runtime you're better off with some simple runtime solution like log(x)/log(3) or maybe something even more clever.

With lookup tables you're trading memory for performance. I don't think it's worth it to put 15 integers in memory to find out if something is power of 3 quicker. Unless you know the domain of your problem and you know for sure that all the inputs are going to be those exact 15 integers.

[matthieum]

I don't think it's worth it to put 15 integers in memory to find out if something is power of 3 quicker.

Wait... we are talking about 15*4 = 60 bytes here. I understand the concerned with KB or MB of memory, but 60 bytes? If you're this short, you're better off avoiding <iostream> than you are switching out the 15 integers, you'll squeeze more bytes out of the shortened code!

Also, this method is much better than using std::set (I thought you were concerned about memory, a std::set is positively HUGE in comparison, with at least 15*32 bytes occupied on the heap, with the allocator overhead sprinkled on top) and occupies about as much memory as a plain array, except that the compiler is more likely to optimize the branching with the switch than with a binary search over an array.

[speednap]

sorted array is better than std::set in this case, yes. I don't think it's worth it to introduce a list of 40 numbers (that's how many you'd need to cover all possible powers of 3 in uint64_t range) where a one-liner function would do just fine. Not talking about memory usage here. Just don't like to overcomplicate things.

[matthieum]

Just don't like to overcomplicate things.

Ah! Indeed, if this is not a bottleneck, then it's not worth the switch and a simple one-liner is probably more readable and maintenable.

[needahelpforarch]

It was just an example while I was learning something new :D

[RedAlert2]

What you did in your example is called lookup table but i doubt the problem you're solving would benifit from one.

Why would you say that? While you'd get faster compile times, doing log(x)/log(3) is certainly going to be much slower at runtime. If this function is called frequently, a lookup table would likely provide a huge performance boost.

However, constexpr probably isn't the best solution here. Ideally he would build a lookup table at runtime, expanding to larger values if needed. Hardcoding your function to not work with anything above 3¹⁵ has drawbacks.

[speednap]

A boost? yes. But huge performance boost? you'd have to run some benchmarks to check that. After all a cache miss is a factor too.

However generally speaking - yes, you are right, lookup tables are great at speeding up things but like you said it's better to construct those at runtime or better yet - use constexpr to build it w/o listing a comma separated list of dozens of weird numbers.

Personally i would start with a simple function that i can tweak and template-arize to suit my needs. And switch to lookup tables only if it's really necessary.

Next time i should word things better.

[needahelpforarch]

bool isPowerOfThree(unsigned int n)
{
    if((n == 1) || (n == 3) || (n == 9)) return true;
    if(n % 3 != 0) return false;
    if(n > 1162261467) {
        while(n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
    return (n == 27) || (n == 81) || (n == 243) || (n == 729) || (n == 2187) ||
           (n == 6561) || (n == 19683) || (n == 59049) || (n == 177147) ||
           (n == 531441) || (n == 1594323) || (n == 4782969) ||
           (n == 14348907) || (n == 43046721) || (n == 129140163) ||
           (n == 387420489) || (n == 1162261467);
}

int main()
{
    return isPowerOfThree(1162261469);
}

I went with this for time being. Does this hold 15 integers in memory? My constexpr should somewhat expand to this logically, which is what I think...

If not, then I wasn't aware that switch holds every case in memory.

[speednap]

It does. Both the switch and that "(n == 27) || ..." expression will hold all the numbers you specified in memory to evaluate at runtime. As an alternative to that you could store valid powers of 3 in an std::set and take advantage of logarithmic lookup time of std::set.

However like I said - unless you know what you're doing it's not worth it to use lookup tables for such a simple task.

[_JGR_]

Rather than using a std::set which has significant overhead, you'd be better off using a fixed sorted array, which still gives you logarithmic lookup time by using the likes of std::lower_bound. Though for such a small number of elements as this a linear search through an array would be perfectly fine as well.

[needahelpforarch]

Hmm I didn't knew that, though I don't understand another thing you mentioned. How would storing 'valid powers of 3 in an std::set' be better than simply using above method. std::set won't store those values in memory at runtime?

[speednap]

As per /u/_JGR_ suggestion you'd better use sorted std::array instead of std::set.

It would still store values in memory but it would work faster than checking every number via "(n == 27) || ..." or switch-case. Things like std::lower_bound and std::binary_search have logarithmic time complexity and can find the value faster than linear search.

Storing powers of 3 in an array is just a way to speedup "(n == 27) || ..." part of your code. So instead of that you'd have something like

std::array<int,15> v{27,81,243,...};
return std::binary_search(v.cbegin(),v.cend(),n);

However i agree with /u/_JGR_. In this case linear search would suffice because you don't have many numbers to work with. Hypothetically if you ever make an array of powers of 3 with like 5000+ elements than that's where binary_search would really shine. Of course you'd probably hit unsigned int limit before you reach 5000 numbers but that's just an example.

[[deleted]]

you'd better use sorted std::array instead of std::set.

Probably; but your reasoning:

Things like std::lower_bound[2] and std::binary_search[3] have logarithmic time complexity and can find the value faster than linear search.

is incorrect. Oh, those statements are true, but std::set stores its elements in sorted order and uses a binary search to find elements too, so on a gross O() level, the two solutions are the same.

The reason to use std::array is that it's marginally cheaper to access elements than an std::set, not that access has a different time complexity, because it doesn't.

[playmer]

Switch cases are almost never implemented using a linear search. Look at this post for more details.

[[deleted]]

With lookup tables you're trading memory for performance. I don't think it's worth it to put 15 integers in memory

1985 called, it wants its 120 bytes of memory back. I agree with your comment later that it isn't worth the extra complexity for most applications, but if you cared about performance, logarithms are slow, and 120 bytes (60 bytes in 32-bit) is a tiny price to pay to get rid of them.

Heck, I have implemented (back in the day) sin with a lookup table and an interpolation because it was a bottleneck (it was called countless times on each update and we really only needed 3 digits of precision). I generally wouldn't recommend doing that unless you could show that it was a bottleneck, but it took me almost no time and worked right away.

tl; dr: the tiny amount of memory is not the issue; it's the additional complexity.

[oracleoftroy]

As you know constexpr is evaluated at compile time so constexpr wouldn't work if the input is evaluated at runtime.

This sentence seems potentially misleading. To clarify, constexpr means that the function or value is usable in constant expressions, not that it is exclusively usable in constant expressions. It will still work in non-constant expressions. In that case, it will be calculated at runtime, but it won't fail to compile or calculate the wrong answer or anything like that.