• 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 5822 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
quote:
Original post by Kippesoep
Hmmm... You''re actually calculating the number, Axter, so you can do away with the whole log thing:





Uhm, of course you''re right. Silly me... That should speed things up nicely, since the number of multiplications is going to be relatively small, since k is a realively small integer anyway.

Nice.

SS

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
This might work, a recursion algorythm, not 100% sure about huge numbers though.

bool func(int m, int n)
{
if(m==n)return true;
if((int)(m/n)==m/n)
{
return func(m/n, n);
}
else
{
return false;
}
}

Share this post


Link to post
Share on other sites
That won''t work.
  
if((int)(m/n)==m/n)

is always true, because m and n are ints. I think what you meant is basically:
  
if(!(m%n))

Other than that, your function is basically the same as Axters, except it uses recursion and division. I''m no expert on the matter, but that seems a lot slower than simply multiplying in a for loop (and could blow the stack if the recursion goes too deep). That said, to make the function 100% correct, there should be a special case for when n == 0. I also noticed the loop can be made one iteration shorter:
  
bool PowerOf(unsigned hyper m, unsigned int n)
{
if (!n) return !m;
unsigned hyper mTest = n; //instead of 1

while (mTest < m)
mTest *= n;
return m == mTest;
}

I like these little challenges. Can anyone improve on it further?

Share this post


Link to post
Share on other sites
As some of you said, the easiest way to figure out if a number m is a power of n is to perform :

log(m)
pow=------
log(n)

and if pow is an integer then m is a power of n.

Share this post


Link to post
Share on other sites
As some of you said, the easiest way to figure out if a number m is a power of n is to perform :

pow=log(m)/log(n)

and if pow is an integer then m is a power of n.

Sorry for the old layout...

Share this post


Link to post
Share on other sites
Ok ... use the very first log based solution ... but change all floats to doubles ... that's a start ...

BUT ... it is still limited by the fact that a signed int only holds 2 billion ... so for numbers greater than that, try long long instead of int ... but it may not help much ... because a double does not really have 64 bits of precision in the mantissa - so at some point, certain interger values simply do not exist in the double's dataset. ...

here's a test you can run over night.

    
long long iValue;
double dValue;
long long iValue2;

// starting at zero and continuing

// while the number is positive and valid

while (for iValue = 0; iValue >= 0; ++iValue)
{
dValue = iValue;
iValue2 = dValue;

// test for correct conversion

if(iValue != iValue2)
{
cout << "Mismatch at iValue: " << iValue << ", iValue2: " << iValue2;
exit(1);
}
}


and if you want feedback (at the cost of wasted performance on the test), you can say: if (iValue % 10000 == 0) cout << "completed: " << iValue;

good luck

Edited by - Xai on February 8, 2002 5:45:42 PM

Share this post


Link to post
Share on other sites
What are you trying to explain ???
Don''t worry for your overflow hypothesis, because log(2^32)=9.63 so I think it will fit easily in a float or double...
Don''t forget : logarithm was created in order to simplify multiplications using smaller numbers...

Share this post


Link to post
Share on other sites
If you want to handle larger integer the best choice is to write your own log function on integer...
I hope I interstood your way of thinking...

Share this post


Link to post
Share on other sites
quote:
Original post by BloodScourge
As some of you said, the easiest way to figure out if a number m is a power of n is to perform :

pow=log(m)/log(n)

and if pow is an integer then m is a power of n.

Sorry for the old layout...


As has been pointed out in previous replies, ANY variation of the log(m)/log(n) solution to this problem won’t work, simply because these functions do not have the resolution to resolve between the values 34271896307633 and 34271896307632, for instance. I have tested this, even with double, it does not work.

The original problem suggested that being able to resolve between two large values like that was a requirement.

The solution to the problem:

    

bool PowerOf(unsigned hyper m, unsigned int n)
{
if (!n)
return !m;

unsigned hyper mTest = n;

while (mTest < m)
mTest *= n;

return m == mTest;
}



…is probably the best one (thanks to Kippesoep for tweaking the algo). The hyper type is a 64-bit integer, and this would give reliable results of values for m of up to 18,446,744,073,709,551,615. I don’t see that there can be a range problem here.

This is a perfect example of where floating point (any precision), is NOT the correct solution. Try any variation of it, and you'll see it's unreliable. I'm a firm believer in floating point, but there are rare cases where it's a bad idea.

Think about it for a while: You want to represent the values 34271896307633 and 34271896307632 each with a log value. The value is "compressed" into a much smaller range (due to the log curve). There's just no way to get the resolution to tell those numbers apart after you've taken their log.

Example:

log(34271896307633) = 13.534938135161013213941868837612
log(34271896307632) = 13.534938135161000541912343394266

That means you need to be accurate at least up to about 16 digits. This assumes the log function gave reliable results in the first place. The accuracy of double is only guaranteed up to 15 digits, so we see that this solution breaks down even before it gets to the values given for the original problem.


SS





Edited by - Axter on February 8, 2002 8:37:32 PM

Share this post


Link to post
Share on other sites

First of all, as the original poster of this problem, I''m
very glad to see some lively discussions going on. The
problem is very simply to state, yet intricately difficult
to solve. It''s kind of like Fermat''s Last Theorem.

I''d have to say that using the logarithm "function" is not
necessarily the fastest nor the most accurate. Think about
how the "log" function is implemented. The stock version
that comes with your favorite compilers probably uses some
variations of iterative evaluation, up to a pre-defined
tolerance level. You have no control over it whatsoever.

I asked for the "fastest", not the "easiest" function to
write, which takes up 2 lines of code if using the "log"
function. Of course, you can always write your own
version of "log", which is where part of the challenge
comes from.

In fact, it may even be faster to just multiply "n" over
and over again until it is larger than or equal to "m".
Yes, I used 34271896307633 "on purpose", to bring out
the limits of "float" and "double" as to render the "log"
functions useless.

The jury is still out as to what is the FASTEST way to do
it in C/C++ (no assembly required).


Premature optimizations can only slow down your project even more.

Share this post


Link to post
Share on other sites
quote:
Original post by Null and Void
Axter, I have no idea what compiler you're using, but the "hyper" type is not part of ANSI/ISO C/C++.




Sorry for that, I was just using the most commonly used compiler.

It's int64, __int64, long long, etc, whatever. Sixty-four bits. I thought it was pretty clear.

Next time I'll consult the ANSI/ISO C/C++ standard to make sure my samples comply 100%...

SS



Edited by - Axter on February 8, 2002 9:36:43 PM

Share this post


Link to post
Share on other sites
quote:
Original post by tangentz
Premature optimizations can only slow down your project even more.

Silly incestations can stop it completly...
The problem is, there''s no way to get at the carry flag from C/C++, and that''s a faster way to implement poly-QWORD integer math.

You can use __int64 which will get you up to 18,446,744,073,709,551,616, but if you want to go beyond that, you''ll want to use some assembly to perform math.

In C/C++, you could add two numbers, then compare the result to the max of the two numbers added together, and that would tell you if it carried or not (if the result is less, it carried). Or you can write some assembly and use a single op code, ADC, add w/carry. There''s also an instruction that multiples two 32bit int''s and returns a 64bit result (in edx:eax), so you can propegate multipications as well.

Or find an arbitrary math package that''s already done this

Share this post


Link to post
Share on other sites
what about this:

          

bool powerOf(unsigned __int64 x, unsigned int n)
{
// (edit) Added th n==0 case

if(n == 0)
{
if(x == 0)
{
return true;
}
else
{
return false;
}
}
// This will catch most of the false cases,

// especially if n is large

if((x%n)!=0) { return false; }

unsigned int nb = n*n;
unsigned int nc = nb*nb;
unsigned int nd = nc*nc;

while(x > nd)
{
x /= nd;
if((x%n)!=0) { return false; }
}

while(x > nc)
{
x /= nc;
if((x%n)!=0) { return false; }
}

while(x > nb)
{
x /= nb;
if((x%n)!=0) { return false; }
}

while(x > n)
{
x /= n;
if((x%n)!=0) { return false; }
}

return true;
}



Im not sure how fast the modulo operator works with large numbers though.

My post up, your post down, my site here


Edited by - Jesper T on February 9, 2002 8:43:59 AM

Share this post


Link to post
Share on other sites
I''m pretty sure that the multiplication method must be fastest. At worst you are looking to put the smallest n and the biggest m (to find m = n^k) ie with 64 bits you enter n=2 and m=2^64-1.

So you only have to do 64 multiplication anyway (worst unoptimized case.

Then do some form of subdivision, ie try something like:

a = n^4
if x < a then look in that range k = 0,...,3
if x < a*a then look in range k = 4,...,7
etc etc

I''m sure a clever choice of ''4'' could give you speed up.

Alternatively you could find midpoint style method. if you n is 2, then try k=32, then either k = 16 or 48. That needs 6 at most

PS. The ASM implementation would be beautiful

Share this post


Link to post
Share on other sites

  • Advertisement