Re: 3^k performance

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sat, Nov 26, 2022 at 08:47:39AM +0100, Ruud H.G. van Tol wrote:
> 
> A022330_1(n)=1+n+sum(k=1,n,logint(3^k,2))
> 
> A022330_2(n)=my(t=1);1+n+sum(k=1,n,logint(t*=3,2))
> 
> ? A022330_1(10^5)
> cpu time = 8,322 ms, real time = 8,352 ms.
> %15 = 7924941755
> 
> ? A022330_2(10^5)
> cpu time = 215 ms, real time = 217 ms.
> %16 = 7924941755
> 
> 
> So about a 40x difference.
> 
> 
> Is that worthwhile to look into?
> How to best approach that?

The simplest approach would be to use powers(3,10^5), with to caveat:
- this would require much more memory.
- the powers function has a bug and is very slow for integers.

A022330_3(n)=my(t=1,P=powers(3,n+1));1+n+sum(k=1,n,logint(P[k+1],2))

Cheers,
Bill