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.

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

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

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

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

quote:

---

Original post by Jesper T
what about this:

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

---

The modulo operator is REALLY slow! I don''t know why it''s so slow, but you should do some benchmarks and experience it for yourself. I once used it in an image-processing algorithm (for a laser printer driver), and after I stopped using it, the performance was improved dramatically. I have found that there is ALWAYS a way to get (usually much) faster performance than using modulo.

Plus you are doing a lot of divisions, so I don''t see how it can be faster than the simple loop with max of 63 multiplications for the absolute worst case.

SS

Sure... modulo is slow because it imply a DIVISION : a=b*q+r => r is the result from a modulo b.

Jesper T,

Your function does not work for values of n >= 16, because it causes your variable nd to overflow. In fact, for a value of n = 16, nd is 0, resulting in a division by zero.

SS

quote:

---

Original post by BloodScourge
sorry for the double post...

---

You can edit one of the messages, then select delete at the top, then apply changes to remove it.

SS

Thanks for this advice (I''m new here...)