Ruud H.G. van Tol on Tue, 29 Nov 2022 14:05:26 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: 3^k performance 


On 2022-11-27 13:00, Bill Allombert wrote:

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);
}


I changed it to
A02230_3(n)= my(s=1,p3=1,p2=1,l2=0);for(k=1,n,p3*=3;p2<<=1;l2++;if(p3>p2,p2<<=1;l2++);s+=l2);s 
to make it return the desired output, see [A02230_3(n)|n<-[0..20]]

? A02230_3(10^5)
cpu time = 606 ms, real time = 612 ms.
%26 = 7924941755

So A02230_2 is still fastest. Almost as fast are:
my(t=1);1+n+sum(k=1,n,t*=3;logint(t,2))
my(t=1/3);sum(k=0,n,logint(t*=3,2)+1)
my(t=1/3);sum(k=0,n,t*=3;logint(t,2)+1)

-- Ruud