• Advertisement

Archived

This topic is now archived and is closed to further replies.

Fastest way to test if a number is a power of n?

This topic is 5910 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Let''s say you need to find out if a number, m, is a power of another number, n. i.e. Does m = n ^ k for some k? e.g. 2048 is a power of 2 since 2 ^ 11 = 2048 34271896307633 is a power of 17 since 17 ^ 11 = 34271896307633 But 317239 is not a power of 5 It''s not too hard when n = 2. You can build a small table of (1,2,4,8,16,32...1024) if your m is small. Similarly for other cases of n. What about when m is 4 billion? Let''s write a function like this: bool PowerOf(unsigned int m, unsigned int n) { //return true if m is a power of n //return false otherwise } What is the best/fastest way to write this C/C++ function? (No assembly please). Premature optimizations can only slow down your project even more.

Share this post


Link to post
Share on other sites
Advertisement
It''s quite simple actually, just use the log-function: to test whether x is a power of n, compute n log(x). If the result is a whole number, then x is a power of n. For example:

  
int PowerOf(float n, float x)
{
float result = log(n) / log(x);
return (result==int(result));
}


To compute n log(x), you''ll have to calculate e log(x) or 10 log(x), and then divide the result by e log(n) or 10 log(n). I''m not sure if this could be optimized more without assembly, in the code above I used the e log(x) function, but 10 log(x) could be faster or slower, I would''t know about that.

Share this post


Link to post
Share on other sites
I just tested the log(m) / log(n), and it does not have the resolution to resolve the large numbers like 34271896307633, as in the example. For instance, it returns the same value for 34271896307632, 34271896307633 and 34271896307634, so I''m afraid that''s not a viable solution.

I also initially thought it''s the way to do it, but it seems it will only work for smaller numbers.

SS

Share this post


Link to post
Share on other sites
Find an arbitrary precision math package. Those example numbers you posted probably all get rounded to the same near-by number due to the way floating point numbers are stored.

Share this post


Link to post
Share on other sites
try using double...you''re putting in values that are beyond the range of a float, and the log functions return double values anyway.

Share this post


Link to post
Share on other sites
How about this:

      
bool PowerOf(unsigned hyper m, unsigned int n)
{
int k = int(log(m) / log(n) + 0.5);

unsigned hyper mTest = 1;

for(int nLoop = 0; nLoop < k; nLoop++)
mTest *= n;

return m == mTest;
}


I tested this, it seems to work with very large numbers. It gets around the precision problem. Not sure about performance, but it gives the right results.

BTW, Silvanis, even double is not precise enough with those large numbers, I tested it.

SS



Edited by - Axter on February 3, 2002 5:34:05 PM

Share this post


Link to post
Share on other sites
Hmmm... You''re actually calculating the number, Axter, so you can do away with the whole log thing:
  
bool PowerOf(unsigned hyper m, unsigned int n)
{
unsigned hyper mTest = 1;
while (mTest < m)
mTest *= n;
return m == mTest;
}



Share this post


Link to post
Share on other sites

  • Advertisement