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?

I suggest

A022330_3(n)=
{
  my(s=1+n,p3=1,p2=1,l2=1);
  for(k=1,n,
    p3 *= 3; p2 <<= 1; l2++;
    if(p3 > p2, p2 << = 1; l2++);
    s+=l2);
}

Cheers,
Bill.