Fastest way to test if a number is a power of n?
Author
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.
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:
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.
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.
Nickm posted almost exactly what I was about to post 
. I was testing it to make sure my math wasn''t screwed up, heh.
. I was testing it to make sure my math wasn''t screwed up, heh.
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
I also initially thought it''s the way to do it, but it seems it will only work for smaller numbers.
SS
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.
or write your own log function, to be as precise
as you want it to be.
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)
try using double...you''re putting in values that are beyond the range of a float, and the log functions return double values anyway.
How about this:
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
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
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;} This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
