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 6096 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

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 on other sites
  inline bool PowerOfTwo(unsigned a) { return !((a-1)&a)}

Share on other sites
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 on other sites
Nickm posted almost exactly what I was about to post . I was testing it to make sure my math wasn''t screwed up, heh.

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 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 on other sites
or write your own log function, to be as precise
as you want it to be.

[Hugo Ferreira][Positronic Dreams][]
"Research is what I''m doing when I don''t know what I''m doing."
- Wernher Von Braun (1912-1977)

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 on other sites

  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 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;}

1. 1
Rutin
47
2. 2
3. 3
4. 4
5. 5

• 13
• 10
• 12
• 10
• 13
• Forum Statistics

• Total Topics
632994
• Total Posts
3009767
• Who's Online (See full list)

There are no registered users currently online

×