On Mon, Apr 26, 2010 at 3:37 PM, Michael Rybalkin
<[email protected]> wrote:
> Thanks! With your help I found solution to my problem but it wasn't
> trivial. I'll describe my
> steps because they might be helpful for someone.
Or you could just do this (use the symbolics):
sage: var('x')
sage: f = x^(10^10) + x^90248023849 - 93989*x+3
sage: f(x = Mod(19,next_prime(10^50)))
68822914080709477961261204042570749508670917822367
sage: a = f(x = Mod(19,next_prime(10^50))); a
68822914080709477961261204042570749508670917822367
sage: parent(a)
Symbolic Ring
sage: a.pyobject()
68822914080709477961261204042570749508670917822367
sage: parent(a.pyobject())
Ring of integers modulo 100000000000000000000000000000000000000000000000151
>
> Finally I wrote simple function, that evaluates polynomial at a
> specified point:
> def poly_eval (poly, a):
> coeffs = poly.coefficients()
> exp = f.exponents()
> value = poly.base_ring()(0)
> for i in range(len(coeffs)):
> value += coeffs[i] * a^(exp[i])
> return value
>
> But at first I tried to dig into sage source code (this is the
> benefits of open-source projects).
>
> I found that Sage cannot evaluate polynomials of very high degree even
> for rings,
> where implementation isn't broken.
>
> At first I changed GF(p) field to IntegerModRing(p):
> sage: p = next_prime(10^50)
> sage: modRing = IntegerModRing(p)
> sage: R.<x> = PolynomialRing(modRing,sparse=True)
>
> And after that I successeded in constructing
> sage: f = x^(10^10)
>
> But evaluation f(2) is failing with MemoryError in
> File "polynomial_element.pyx", line 570, in
> sage.rings.polynomial.polynomial_element.Polynomial.__call__ (sage/
> rings/polynomial/polynomial_element.c:6687)
> File "/usr/local/sage-4.3.5/local/lib/python2.6/site-packages/sage/
> rings/polynomial/polynomial_element_generic.py", line 386, in list
> v = [zero] * (self.degree()+1)
>
> I found out that Polynomial.__call__ method evaluates data via
> CompiledPolynomialFunction,
> but CompiledPolynomialFunction accept polynomials only in dense form,
> because it accepts f.list() and
> this method tries to allocate list with 10^10 elements.
>
> I changed f to
> sage: f = x^(10^50)
> And evaluation gave me another exception because of conversion
> f.degree() to long in
> File "polynomial_element.pyx", line 499, in
> sage.rings.polynomial.polynomial_element.Polynomial.__call__ (sage/
> rings/polynomial/polynomial_element.c:5606)
> OverflowError: long int too large to convert to int
>
> All evaluation of generic (even sparse) polynomials is based on
> precondition that f.degree() can be
> fit into long data type. And changing long variables into variable-
> length integers can cause slowdown in
> evaluation dense polynomials. So I found out that changing existing
> sage code to support sparse
> polynomials isn't easy task in general. But simple solution (poly_eval
> function) can be used directly
> or it can be added to the polynomial_element_generic.py if polynomial
> is very sparse.
>
> PS: maybe this should be send to sage-devel.
>
> On 25 апр, 11:19, William Stein <[email protected]> wrote:
>> On Sat, Apr 24, 2010 at 10:22 PM, Robert Bradshaw
>>
>>
>>
>>
>>
>> <[email protected]> wrote:
>> > On Apr 24, 2010, at 5:36 PM, Michael Rybalkin wrote:
>>
>> >> How to get monomial with large exponent in the polynomial rings?
>>
>> >> For example I hsave polynomial ring over large finite field:
>> >> p = next_prime(10^20)
>> >> R.<x> = PolynomialRing(GF(p), sparse=True)
>>
>> >> Monomial x^(10^7) construction takes 2 seconds:
>> >> time tmp = x^(10^7)
>>
>> >> Monomial x^(10^8) construction uses all 6 Gb server memory and cannot
>> >> finish.
>> >> And without 'sparse=True' option I cannot even get x^(10^6).
>>
>> >> What is the limitations for monomial exponents in polynomial rings?
>> >> What can be done in my case? For example GAP handles this case without
>> >> any problem.
>>
>> > Seems like the sparse=True flag is horribly broken for GF(p)[x]:
>>
>> > sage: p = next_prime(10^20)
>> > sage: R.<x> = PolynomialRing(GF(p), sparse=True)
>> > sage: type(x)
>> > <type 'sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX'>
>>
>> > sage: R.<x> = PolynomialRing(QQ, sparse=True)
>> > sage: x^(10^8)
>> > x^100000000
>>
>> > - Robert
>>
>> This is now
>>
>> http://trac.sagemath.org/sage_trac/ticket/8762
>>
>> William
>>
>>
>>
>> > --
>> > To post to this group, send email to [email protected]
>> > To unsubscribe from this group, send email to
>> > [email protected]
>> > For more options, visit this group at
>> >http://groups.google.com/group/sage-support
>> > URL:http://www.sagemath.org
>>
>> --
>> William Stein
>> Professor of Mathematics
>> University of Washingtonhttp://wstein.org
>>
>> --
>> To post to this group, send email to [email protected]
>> To unsubscribe from this group, send email to
>> [email protected]
>> For more options, visit this group
>> athttp://groups.google.com/group/sage-support
>> URL:http://www.sagemath.org
>
> --
> To post to this group, send email to [email protected]
> To unsubscribe from this group, send email to
> [email protected]
> For more options, visit this group at
> http://groups.google.com/group/sage-support
> URL: http://www.sagemath.org
>
--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org
--
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-support
URL: http://www.sagemath.org
