Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Check if one integer is an integer power of another

Tags:

algorithm

math

You'd do better to repeatedly divide y into x. The first time you get a non-zero remainder you know x is not an integer power of y.

while (x%y == 0)  x = x / y
return x == 1

This deals with your odd/even point on the first iteration.


It means logy(x) should be an integer. Don't need any loop. in O(1) time

public class PowerTest {

    public static boolean isPower(int x, int y) {
        double d = Math.log(Math.abs(x)) / Math.log(Math.abs(y));

        if ((x > 0 && y > 0) || (x < 0 && y < 0)) {
            if (d == (int) d) {
                return true;
            } else {
                return false;
            }
        } else if (x > 0 && y < 0) {
            if ((int) d % 2 == 0) {
                return true;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {

        System.out.println(isPower(-32, -2));
        System.out.println(isPower(2, 8));
        System.out.println(isPower(8, 12));
        System.out.println(isPower(9, 9));
        System.out.println(isPower(-16, 2));
        System.out.println(isPower(-8, -2));
        System.out.println(isPower(16, -2));
        System.out.println(isPower(8, -2));
    }

}

This looks for the exponent in O(log N) steps:

#define MAX_POWERS 100

int is_power(unsigned long x, unsigned long y) {
  int i;
  unsigned long powers[MAX_POWERS];
  unsigned long last;
  last = powers[0] = y;

  for (i = 1; last < x; i++) {
    last *= last; // note that last * last can overflow here!
    powers[i] = last;
  }
  while (x >= y) {
    unsigned long top = powers[--i];
    if (x >= top) {
      unsigned long x1 = x / top;
      if (x1 * top != x) return 0;
      x = x1;
    }
  }
  return (x == 1);
}

Negative numbers are not handled by this code, but it can be done easyly with some conditional code when i = 1


This looks to be pretty fast for positive numbers as it finds the lower and upper limits for desired power and then applies binary search.

#include <iostream>
#include <cmath>
using namespace std;

//x is the dividend, y the divisor.
bool isIntegerPower(int x, int y)
{
    int low = 0, high;
    int exp = 1;
    int val = y;
    //Loop by changing exponent in the powers of 2 and
    //Find out low and high exponents between which the required exponent lies.
    while(1)
    {
        val = pow((double)y, exp);
        if(val == x)
            return true;
        else if(val > x)
            break;
        low = exp;
        exp = exp * 2;
        high = exp;
    }
    //Use binary search to find out the actual integer exponent if exists
    //Otherwise, return false as no integer power.
    int mid = (low + high)/2;
    while(low < high)
    {
        val = pow((double)y, mid);
        if(val > x)
        {
            high = mid-1;
        }
        else if(val == x)
        {
            return true;
        }
        else if(val < x)
        {
            low = mid+1;
        }
        mid = (low + high)/2;
    }
    return false;
}

int main()
{
    cout<<isIntegerPower(1024,2);
}