Re: Simple way to show number is a power?


Timothy Murphy wrote:

> The reason I asked the question was that the methods I have seen
> all involve looking up x = 1/p log(n) in (electronic) log tables,
> and then testing the integers close to e^x,
> which seems quite sufficient in any real case,
> as the log is always reasonably small.
>
> I guess your suggestion is the same,
> except that one computes the log explicitly by a series
> with known maximum error?

Don't bother with logarithms.

Solve x**p - n = 0 with Newton's rule.
If done with careful attention to precision,
solving this with a unit error bound has the
same time complexity as multiplying n with itself.

.

Relevant Pages