Re: polcyclo: overflow in precp().

Dear Karim,

Thank you for the explanation. As for using t_INTMOD, I see the following issue:

? polcyclo(22,Mod(10,2))
%1 = Mod(1, 2)
? polcyclo(22,Mod(10,11))
%2 = Mod(0, 11)

but

? polcyclo(22,Mod(10,22))
*** at top-level: polcyclo(22,Mod(10,22))
*** ^-----------------------
*** polcyclo: impossible inverse in Fl_inv: Mod(11, 22).
*** Break loop: type 'break' to go back to GP prompt

Why is this happening?

Does it mean that there is no other way, but to split the modulus into primepowers and to use chinese() afterwards?

Regards,

Max

On Fri, Oct 14, 2022 at 1:21 PM Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> wrote:

Hi Max,

* Max Alekseyev [2022-10-14 16:34]:
> 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().

1) Yes, t_PADICs are very inefficient and provided for convenience if
denominators are involved, when the much more efficient t_INTMOD are not
an option. Use a t_INTMOD !

Here, polcyclo(524308, Mod(10,4)) works and is instantaneous.

2) The real problem here is

? 2^262154*(1 + O(2)) - 1
*** _+_: overflow in precp().

because we're trying to construct a t_PADIC with so many significant
digits it can't even be represented given the current design of the
t_PADIC type.

The fact that we don't encode the p-adic precision or valuation in 64
bits is a known design bug in the t_PADIC type: we packed both together
in 64 bits to save on memory (and copying costs) instead of allowing one
codeword for each... It's silly nowadays but I won't change this: it's a
lot of work to remove those limits, and there is no application (our
handling of most of these "huge" t_PADICs being so bad anyway).
There are other analogous hardcoded limitations of other types, see
http://pari.math.u-bordeaux.fr/faq.html#limits

3) This occurs because we compute Phi_n(x) as

(*) Prod_{d|n} (x^d - 1) ^ mu(n/d)

and our n = 524308 has large divisors: so x^d - 1 kills us as explained above.

This formula, x^d - 1 computes a t_PADIC which is as precise as
possible given the input, which is ridiculous because it gets multiplied
by other t_PADICs whose precision is much smaller and will kill the
precision of x^d - 1.

4) Finally, the problem boils down to using (*) formally as written,
without bothering to analyze what "x" stands for, in which case we could
adapt our strategy whenever x is an inexact object.

It's doable and not very exciting. Also, we have lots of
'polynomial-evaluation functions' besides this one which may (or may not)
suffer from analogous inefficiencies or problems.

I don't think I'll do it ... :-)

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