Re: probable bug of "ispower" function in GP: FALSE, apologies!

On Thu, Jan 12, 2023 at 01:13:22PM +0100, Karim Belabas wrote:
> * Vincent Lefevre [2023-01-12 12:40]:
> > On 2023-01-12 12:31:09 +0100, [email protected] wrote:
> > > I misunderstood the definition of "ispower"!
> > > 
> > > I wanted a function that identify directly if some integer is a power of 2
> > 
> > I suppose that you can use something like
> > 
> >   ispower(64,,&n)
> > 
> > and check that n is 2. But I suppose that for large numbers, this may
> > be inefficient because ispower() will not just check for powers of 2.
> 
> Use hammingweight(N) == 1. 
> 
> Or v = valuation(N,2); N >> v == 1 if you need the exact power. (Will be
> a little slower.)

You can also use

N == 1<<logint(N,2)

Whether this is faster depend whether you expect N to be prime or not
(valuation(N,2) is very fast if N is odd!)

N=2^1000;
#
for(i=1,10^6,hammingweight(N) == 1)
for(i=1,10^6,N>>valuation(N,2) == 1)
for(i=1,10^6,N == 1<<logint(N,2))
for(i=1,10^6,valuation(N,2) == logint(N,2))
N=random(2^1000);
for(i=1,10^6,hammingweight(N) == 1)
for(i=1,10^6,N>>valuation(N,2) == 1)
for(i=1,10^6,N == 1<<logint(N,2))
for(i=1,10^6,valuation(N,2) == logint(N,2))

which gives

time = 98 ms.
time = 94 ms.
time = 89 ms.
time = 95 ms.

time = 133 ms.
time = 101 ms.
time = 85 ms.
time = 90 ms.

Cheers,
Bill.