Karim Belabas on Tue, 01 Nov 2022 14:11:00 +0100


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

Re: polcyclo: overflow in precp().


* Bill Allombert [2022-10-31 10:42]:
> On Fri, Oct 14, 2022 at 10:33:51AM -0400, Max Alekseyev wrote:
> > Can anything be done about this error?
> > 
> > ===
> > ? allocatemem(2^31)
> >   ***   Warning: new stack size = 2147483648 (2048.000 Mbytes).
> > ? polcyclo(524308,10+O(2^2))
> >   ***   at top-level: polcyclo(524308,10+O(2^2))
> >   ***                 ^--------------------------
> >   *** polcyclo: overflow in precp().
> >   ***   Break loop: type 'break' to go back to GP prompt
> > break>
> > ===
> 
> You can try
> 
> mypolcyclo(n,a,p,e)=
> {
>   my(P=1,v=valuation(a,p));
>   if(v==0
>     ,polcyclo(n,a+O(p^e))
>     ,fordiv(n,d,P*=(if(d*v<e,a^d,0)-1)^moebius(n/d));
>     P+O(p^e))
> }
> 
> ? mypolcyclo(524308,10,2,100)
> %31 = 1+2^2+2^3+2^5+2^6+2^8+2^12+2^13+2^15+2^17+2^20+2^21+2^26+2^27+2^28+2^29+2^30+2^32+2^33+2^37+2^41+2^43+2^46+2^48+2^51+2^52+2^53+2^54+2^55+2^56+2^59+2^63+2^65+2^70+2^74+2^75+2^78+2^84+2^85+2^89+2^90+2^92+2^93+2^94+2^96+2^97+2^98+O(2^100)

I added specific code to polcyclo_eval() for t_PADIC arguments with
positive valuation. Even though it complicates the code, it's a legitimate
usecase which is hard to reproduce efficiently from first principles.

? polcyclo(524308, 10+O(2^99))
%1 = 1 + 2^2 + 2^3 + 2^5 + 2^6 + 2^8 + 2^12 + 2^13 + 2^15 + 2^17 + 2^20 + 2^21 + 2^26 + 2^27 + 2^28 + 2^29 + 2^30 + 2^32 + 2^33 + 2^37 + 2^41 + 2^43 + 2^46 + 2^48 + 2^51 + 2^52 + 2^53 + 2^54 + 2^55 + 2^56 + 2^59 + 2^63 + 2^65 + 2^70 + 2^74 + 2^75 + 2^78 + 2^84 + 2^85 + 2^89 + 2^90 + 2^92 + 2^93 + 2^94 + 2^96 + 2^97 + 2^98 + O(2^100)

Committed to the 'master' branch.

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251), Université de Bordeaux
Vice-président en charge du Numérique
T: (+33) 05 40 00 29 77; http://www.math.u-bordeaux.fr/~kbelabas/
`