mdarikrayhan's blog

How to check if a number x is power of a number y
By mdarikrayhan, history, 4 years ago, In English

A recursive function that can check if a number num is power a anohter number base.

bool isPowerof(long long num, long long base)
{
    if (num <= 0)
        return false;
    if (num % base == 0)
        return isPowerof(num / base, base);
    if (num == 1)
        return true;
    return false;
}
  1. Limitation : num<= $$$2^{62}$$$ and 2<=base<= $$$2^{62}$$$
  2. Time complexity : O($$$log_{base}^{num}$$$).
  3. Sample submission : 169977243.
  • Vote: I like it
  • -16
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
4 years ago, hide # |
 
Vote: I like it -17 Vote: I do not like it

Try to use long doubles and gnu g++20 11.2.0 (64 bit)

bool isPowerofN(long long num, long long base)
{
    long double log_num = (std::log((long double)num) / std::log((long double)base));
    long long x = std::floor(log_num);
    long long y = std::ceil(log_num);
    if (x == y)
        return true;
    else
        return false;
}
→ Reply
»
4 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Btw, in order to check is integer $$$x$$$ power of $$$2$$$ it is better to use (x & (x - 1)) == 0

→ Reply
  • »
    »
    4 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    btw, x & -x == x is shorter and easier to remember.

    → Reply
    • »
      »
      »
      4 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +5 Vote: I do not like it

      Of course, it's hardly universal, but to me this formula is much less intuitive. Still, I think this explanation might help you wrap you head around the logic behind the two formulae, rather than remember them.

      The only thing you need to understand to understand (x & (x - 1)) == 0 is what x - 1 does: it takes the binary form of x, replaces its last one with zero and every zero after it with ones (i.e. ...10000 -> ...01111). So x and x - 1 agree on everything before the last one and disagree on everything after and including it. Therefore x & (x - 1) retains bits before the last one and drops everything after, effectively just resetting the lowest bit set.

      So (x & (x - 1)) == 0 asks: if I remove the last one bit, will I get nothing left? And it's trivial to see how this is equivalent to checking for a power of two (except when x == 0, of course, but that's intuitive too: if you've got nothing to remove, you still get nought).

      x & (-x) takes this one step further than necessary: you need to understand that -x is in fact ~(x - 1), which, as we have seen just before, agrees with x on everything after and including the last one and disagrees on everything before the last one, so in fact x & -x retains only the last bit set. So (x & -x) == x asks: if I only retain the last one bit (and drop every other bit), will I get no changes? I hope it's now easy to see how this is exactly dual to the other formula.

      → Reply
    • »
      »
      »
      4 years ago, hide # ^ |
       
      Vote: I like it +4 Vote: I do not like it

      __builtin_popcount(x)==1

      → Reply
      • »
        »
        »
        »
        4 years ago, hide # ^ |
         
        Vote: I like it +8 Vote: I do not like it

        It generates slightly different code, and seems to be slightly faster for int (on Codeforces). For long long, I could not possible to identify advantages (on Codeforces).

        On the other hand, it depends on the CPU. So, for example, on my local laptop, methods for int work the same by speed, but for long long popcount loses.

        Code (ofc with pragmas): https://godbolt.org/z/98753T416

        → Reply
»
4 years ago, hide # |
← Rev. 4  
Vote: I like it +5 Vote: I do not like it

log gives you an approximate value, because floating-point values are imprecise by their nature. And even if log gives the best approximation possible, you divide an approximation by another approximation, resulting in a worse approximation. All of this means that log_num may be not an integer but a value very near to it even if logically it should be integral.

In problems like this one, what you need to do is not check that log_num is an integer, which you're doing now, but that it's "near enough" to an integer. If you knew that "near enough" means "at most 0.00001 far from an integer", you could use abs(log_num - round(log_num)) < 0.00001 for that.

But in this case, you don't: if num is very big, you can't be certain what the epsilon should be. That's the problem with logarithms: a big change in the argument can yield an incomparably small change in the result, so we have to find another way, and it's like this: take log_num, round it to an integer and check that base to the power of the rounded log_num is indeed equal to num: pow(base, round(log_num)) == num.

Except that this won't work right either! pow is, just like every other floating-point function, only approximate: even if both of its arguments are integers, what pow(a, b) really does is best expressed by exp(log(a) * b), so the result might not be an integer but only a very near number. So you need to round it before comparing to num: round(pow(base, round(log_num))) == num.

And even that's not enough. long long is usually 64-bit. double is usually 64-bit too, but double pays for its increased precision with decreased precision for big numbers, so it can only store integers up to $$$2^{53}$$$ -- after that, it starts approximating them, e.g. $$$2^{53} + 1$$$ is equal to $$$2^{53}$$$. If you want your code to work with all long long numbers, you need to use long double, which is usually a 80-bit number (but not on MSVC, unfortunately), which allows it to express all integers that long long can.

→ Reply
  • »
    »
    4 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Thanks,mate.You were right about the approximation.

    By adding this line, if (fabs(log_num - round(log_num)) < 0.000001) I was able to check if the numbers were same or not and also in constant time. Here is the submission 169961565. Also, it can calculate accurately up numbers <=2^63.

    Here is the modified function : 

    bool isPowerof(long long num, long long base)
{
    long double log_num =log(num) / log(base);
    if (fabs(log_num - round(log_num)) < 0.000001)
    //if difference is less than 10^-5 then they are same number
    {
        return true;
    }
    else
    {
        return false;
    }
}
    → Reply
    • »
      »
      »
      4 years ago, hide # ^ |
       
      Vote: I like it +4 Vote: I do not like it

      Now you just didn't listen to like half of what I said and incorrectly believe you've got working code which only passes due to sheer luck and bad tests (try $$$2^{46} + 1$$$ with base $$$2$$$, for instance -- it fails). Good job.

      → Reply
      • »
        »
        »
        »
        4 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Droped the idea of solving it using log. Solved it using recursion and also the time complexity isn't that much for 1475A - Odd Divisor. If you have time can you check this solution mate ?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          Looks fine to me. I wouldn't use recursion though: it's slow and sometimes difficult to get right. A simple loop suffices:

          bool isPowerof(long long num, long long base)
{
    if (num <= 0)
        return false;
    while(num % base == 0) {
        num /= base;
    }
    return num == 1;
}

          And it's (arguably) easier to see how this works: it literally checks that num is one multiplied by base any number of times.

          → Reply