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

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

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?

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.

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...

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 validwhile (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

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...

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...

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

Axter, I have no idea what compiler you''re using, but the "hyper" type is not part of ANSI/ISO C/C++.