Karim Belabas on Fri, 14 Oct 2022 19:22:54 +0200


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

Re: polcyclo: overflow in precp(). 

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