p-adic implementation in SAGE
Barukh Ziv
I would like to ask you about a problem I am encountering while using
NTL library for p-adic numbers manipulation. Sometimes, I get the
following internal error from NTL function:
"can't grow this _ntl_gbigint"
I saw a partial explanation on the following SAGE documentation page:
http://www.sagemath.org/doc/reference/sage/rings/padics/padic_ZZ_pX_CA_element.html,
where I read:
If you get an error 'internal error: can't grow this _ntl_gbigint,'
it indicates that moduli are being mixed inappropriately somewhere.
For example, hen calling a function with a ZZ_pX_c as an argument, it
copies.
If the modulus is not set to the modulus of the ZZ_pX_c, you can get
errors.
As SAGE system has implementation of p-adic numbers, I would like to
know whether there are good ways to overcome this problem while mixing
moduli (which is essential in operations such as lifting).
Best regards,
Barukh Ziv.
luisfe
On 24 mar, 06:13, Barukh Ziv <barukh....@gmail.com> wrote:
> Dear all,
>
> I would like to ask you about a problem I am encountering while using
> NTL library for p-adic numbers manipulation. Sometimes, I get the
> following internal error from NTL function:
>
> "can't grow this _ntl_gbigint"
Are you using ntl_ZZ_p or ntl_ZZ_pE? I have experienced the same type
of errors with the latter (due to bad manipulations of
ntl_ZZ_pEContext by myself.
Mike Hansen
> Dear all,
>
> I would like to ask you about a problem I am encountering while using
> NTL library for p-adic numbers manipulation. Sometimes, I get the
> following internal error from NTL function:
>
> "can't grow this _ntl_gbigint"
Are you able to post the code that causes this problem? That would
help a lot with trying to figure out what's going on.
--Mike
Barukh Ziv
Thank you for the quick reply. I will answer to both questions:
> Are you using ntl_ZZ_p or ntl_ZZ_pE? I have experienced the same type
> of errors with the latter (due to bad manipulations of
> ntl_ZZ_pEContext by myself.
Yes, I experience problems while using ZZ_pE as in this case NTL does
block allocation, and cannot re-allocate a single ZZ_p.
On Mar 24, 11:08 am, Mike Hansen <mhan...@gmail.com> wrote:
> Are you able to post the code that causes this problem? That would
> help a lot with trying to figure out what's going on.
>
> --Mike
Mike, unfortunately, the code is too complicated to be presented here,
but I will try my best to explain what kind of the problem
I am facing. Basically, the problem occurs once an ZZ_pX was created
with a certain modulus N, and then assigned from another
ZZ_pX created with a bigger modulus N' > N. Semantically, consider the
following algorhtm:
ZZ_pE a, ap;
// Initialize ap
while (precision < max_precision)
{
a = f(ap); // *
ap = a; // **
precision++;
}
where calculations in f() are done with modulus 2^precision. IMHO,
both statements (*) and (**) may lead to an error, as they should be
overwritten with bigger array.
This is essentially a problem stated in the aforementioned SAGE doc
page on p-adic element. So, I wonder, do you know any good ways to
overcome this? In particular, is there a way to explicitly re-allocate
a previously allocated ZZ_pX object? Another question: does NTL
perform an automatic garbage collection in any way?
Regards and thanks for your help,
B/
luisfe
Yes you can, altought if your code is very low level I am not sure on
the impact.
Consider this:
sage: a = ntl.ZZ_pContext(128)
sage: polynomial = ntl.ZZ_pX([1,2,3,4,5],a)
sage: for i in range(128):
....: a = ntl.ZZ_pContext(a.modulus()*2)
....: f = f.convert_to_modulus(a)
....:
sage: f
[1 2 3 4 5]
sage: f.get_modulus_context()
NTL modulus 43556142965880123323311949751266331066368
This create a new polynomial modulus the right context.However, this
will not work to change context in ZZ_pEX in which you are changing
your defining polynomial (succesive residuals of a p-adic f)
For example,
Suppose f = 15 + x ^2 and you want an algorithm to compute in
(ZZ/2^nZZ)[x] / ( f(x) )
sage: p = ntl.ZZ_pContext(2)
sage: f = [15, 0, 1]
sage: pe = ntl.ZZ_pEContext( ntl.ZZ_pX(f, p) )
sage: poly = ntl.ZZ_pEX([[1], [0], [0,1]], pe)
sage: p2 = ntl.ZZ_pContext(4)
sage: poly = poly.convert_to_modulus(p2)
sage: sage: poly.get_modulus_context()
NTL modulus [1 0 1] (mod 4)
Which is not what we want. Instead, you could add to ntl_ZZ_pEX a
function like (In the following function one should omit the pcontext
input c and use cE.get_pc() instead)
def convert_to_pE(self, ntl_ZZ_pContext_class c,
ntl_ZZ_pEContext_class cE):
"""
Returns a new ntl_ZZ_pE which is the same as self, but
considered modulo a different pE (but the SAME polynomial).
"""
cE.restore_c()
cdef ntl_ZZ_pEX ans = PY_NEW(ntl_ZZ_pEX)
_sig_on
ZZ_pEX_conv_modulus(ans.x, self.x, c.x)
_sig_off
ans.c = cE
return ans
with this function, the previous example would be:
sage: p = ntl.ZZ_pContext(2)
sage: f = [15, 0, 1]
sage: pe = ntl.ZZ_pEContext( ntl.ZZ_pX(f, p) )
sage: poly = ntl.ZZ_pEX([[1], [0], [0,1]], pe)
sage: p2 = ntl.ZZ_pContext(4)
sage: pe2 = ntl.ZZ_pEContext( ntl.ZZ_pX(f, p2) )
sage: poly = poly.convert_to_pE(p2, pe2)
sage: poly.get_modulus_context()
NTL modulus [3 0 1] (mod 4)
Another question: does NTL
> perform an automatic garbage collection in any way?
No idea, sorry
Barukh Ziv
Thanks for your reply. It's very interesting, although not easy to
understand.
In any case, I am more interested in C level and SAGE/C interface.
Also, I am failing to understand when NTL will enter the "error path".
For instance,
consider the following C++ code:
#include "NTL/ZZ_pX.h"
NTL_CLIENT
ZZ_p::init( power2_ZZ(128) );
ZZX p;
SetCoeff(p, 0, power2_ZZ(127));
SetCoeff(p, 1, power2_ZZ(126));
ZZ_pX pp = to_ZZ_pX(p);
ZZ_p::init( power2_ZZ(3) );
ZZ_pX pp2 = to_ZZ_pX(p);
pp2 = pp; // (*)
I would expect the (*) statement to result in an error, since pp2 was
allocated with smaller (and fixed) size than pp.
However, the program finishes normally! When I tried to debug it, I
ended up in macros defining vector classes, where debugging is
impossible...
Thanks,
B/
> No idea, sorry- Hide quoted text -
>
> - Show quoted text -