graziano aglietti on Sat, 26 Nov 2022 10:47:20 +0100


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

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 <Bill.Allombert@math.u-bordeaux.fr> 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