Re: 3^k performance

Hi Bill
" - the powers function has a bug and is very slow for integers."

Which bug?

Thanks
Graziano

Il giorno sab 26 nov 2022 alle ore 09:47 Bill Allombert <
[email protected]> ha scritto:

> 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
>
>

-- 
Graziano Aglietti