2008/9/22 Georg S. Weber <[EMAIL PROTECTED]>:
>
>
>
> On 22 Sep., 10:39, "John Cremona" <[EMAIL PROTECTED]> wrote:
>> 2008/9/21 Georg S. Weber <[EMAIL PROTECTED]>:
>>
>>
>>
>>
>>
>> > Hi John,
>>
>> > On 21 Sep., 21:16, "John Cremona" <[EMAIL PROTECTED]> wrote:
>> >> The long test in ell_finite_field.py which causes problems on this
>> >> platform is this:
>> >> sage: E = EllipticCurve('389a')
>> >> sage: for p in prime_range(10000): #long time (~20s)
>> >> ... if p != 389:
>> >> ... G=E.change_ring(GF(p)).abelian_group()
>>
>> >> I would like to know if there is something going on there which can be
>> >> fixed.
>>
>> >> Can you test these and see if they work:
>>
>> >> sage: for p in prime_range(10000):
>> >> ... if p != 389:
>> >> ... F=GF(p)
>>
>> >> and
>>
>> >> sage: for p in prime_range(10000):
>> >> ... if p != 389:
>> >> ... Ep=E.change_ring(GF(p))
>>
>> >> and
>>
>> >> sage: for p in prime_range(10000):
>> >> ... if p != 389:
>> >> ... G=E.change_ring(GF(p)).cardinality()
>>
>> >> Thanks,
>>
>> >> John
>>
>> > the following line works fine:
>>
>> > sage: for p in prime_range(10000):
>> > ... if p != 389:
>> > ... F=GF(p)
>>
>> > as does that one (note the 3000 instead the 10000):
>>
>> > sage: for p in prime_range(3000): #long time
>> > (~20s)
>> > ... if p != 389:
>> > ... Ep = E.change_ring(GF(p))
>>
>> > but now with 4000 (yet no 10000) it fails:
>>
>> > sage: for p in prime_range(4000): #long time
>> > (~20s)
>> > ... if p != 389:
>> > ... Ep = E.change_ring(GF(p))
>>
>> > with the following message:
>> > ...
>> > sage -t -long devel/sage/sage/schemes/elliptic_curves/
>> > ell_finite_field.py
>> > halt 14
>>
>> > error: no more memory
>> > System 5112k:5112k Appl 4598k/513k Malloc 4082k/5k Valloc 1024k/508k
>> > Pages 144/112 Regions 2:2
>>
>> > A mysterious error (perphaps a memory error?) occurred, which may have
>> > crashed doctest.
>> > [37.2 s]
>> > exit code: 768
>>
>> > ----------------------------------------------------------------------
>> > The following tests failed:
>>
>> > sage -t -long devel/sage/sage/schemes/elliptic_curves/
>> > ell_finite_field.py
>> > Total time for all tests: 37.2 seconds
>> > ...
>>
>> > Mysteriously, monitoring the RAM footprint during this half minute,
>> > nothing strange seems to happen. Of the 2 GB physical memory, more
>> > than 1.3 GB RAM is free at minimum all the time. Of the virtual RAM of
>> > the Sage processes, there is one python process of some 360 MB or so,
>> > and one gp processes of 600 MB or so, but that's it essentially.
>> > Monitoring this half minute with "3000" as a prime boundary instead of
>> > "4000" does not show any difference to me, especially the RAM
>> > footprint of all the processes involved is the same (300+MB python,
>> > 600+MB gp), apart from passing the test :-).
>>
>> > For completeness, the following passes (the original line with only
>> > "3000" instead of "10000"):
>>
>> > sage: for p in prime_range(3000): #long time
>> > (~20s)
>> > ... if p != 389:
>> > ... G=E.change_ring(GF(p)).abelian_group()
>>
>> > So, "E.change_ring(GF(p))" is somehow the culprit, being called for
>> > primes p up to 4000 (or 10000) instead of only up to 3000.
>> > I' m curious if you can make sense of this --- I'll be online again
>> > tomorrow evening.
>>
>> Right, so it's not the creation of the finite fields GF(p) which is
>> causing trouble, and neither is it the code in abelian_group() (good
>> -- that's the bit I wrote).
>>
>> The change_ring() function just creates a new elliptic curve each
>> time. So you should see the same behaviour if you replace
>> Ep = E.change_ring(GF(p))
>> with
>> Ep = EllipticCurve(GF(p),[0,1,1,-2,0])
>> in the loop. To test this without having to avoid p=389 try this:
>> sage: for p in prime_range(100000): EllipticCurve(GF(p),[0,1,1,10,13])
>>
>> (That curve will be ok for all p!=100931).
>>
>> John
>>
>>
>>
>> > Cheers,
>> > gsw
>
> Hi John,
> and hello sage-devel (all possible help needed here),
>
> that's a pretty cool bug we're hunting
> (and a pretty cool elliptic curve, too)!
>
> The following line works in sage 3.1.3.alpha0 on my Intel MacBook (one
> always has to hit "return" twice):
>
> sage: for p in prime_range(32768, 100000): EllipticCurve(GF(p),
> [0,1,1,10,13])
>
> On the screen, for all those primes between 2^15 and 10^6, this line
> prints:
>
> Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 13 over
> Finite Field of size 32771
> ...
> Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 13 over
> Finite Field of size 99991
>
> So the bug has nothing to do with physical RAM, or with the virtual
> memory for processes, or anything like that.
> And if I do in a new Sage session, with some arbitrary "a" smaller
> than 32768:
>
> sage: for p in prime_range(a, a + 150): EllipticCurve(GF(p),
> [0,1,1,10,13])
>
> then I get the clean output like this (for a = 32600):
>
> Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 13 over
> Finite Field of size 32603
> Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 13 over
> Finite Field of size 32609
> Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 13 over
> Finite Field of size 32611
> Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 13 over
> Finite Field of size 32621
> Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 13 over
> Finite Field of size 32633
> Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 13 over
> Finite Field of size 32647
> Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 13 over
> Finite Field of size 32653
> Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 13 over
> Finite Field of size 32687
> Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 13 over
> Finite Field of size 32693
> Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 13 over
> Finite Field of size 32707
> Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 13 over
> Finite Field of size 32713
> Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 13 over
> Finite Field of size 32717
> Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 13 over
> Finite Field of size 32719
> Elliptic Curve defined by y^2 + y = x^3 + x^2 + 10*x + 13 over
> Finite Field of size 32749
>
> However, the following line:
>
> sage: for p in prime_range(a, a + 5000): EllipticCurve(GF(p),
> [0,1,1,10,13])
>
> crashes for arbitrary "a" smaller than, say, 30000, whoooops:
>
> error: no more memory
> System 8672k:8672k Appl 8233k/438k Malloc 4030k/33k Valloc 4608k/
> 404k Pages 1071/81 Regions 9:9
>
> halt 14
>
> and the sage session is no more!
> So the bug is not related to some mathematical phenomenon, because the
> absolute value of the range start point does not matter, but instead
> only the size of the interval of primes --- as long as this interval
> contains "enough" small primes below 32768. I tested e.g. with
> prime_range(31300, 32600) and it alreay crashed.
>
> My guess at this point is, that under Mac OS X (I'm using 10.4.11) ---
> other systems didn't show this bug yet --- some stack or cache or heap
> or whatever overflows, which is related to 16-Bit signed integers
> (where INT_MAX is 32767), and which is filled up by consecutive
> calculations. But not by a "single" one, and not related to the actual
> calculations done, but only related to the sequence in which they are
> done and the number of such calculations.
>
> In the modular symbols code (and elsewhere, IIRC) there are comments
> that for small integers, Sage uses python integers, but for large
> integers, Sage uses GMP integers.
>
> Is the break-off point at 32767?
>
> If yes, can it be easily changed e.g. to 0, something close to 0, so I
> can retest this under new conditions?
>
> Or where to look further?
I looked at the code for prime_range() which says:
Use this function when both start and stop are not too large,
since in all cases this function makes a table of primes up to
stop. If both are large, use the primes iterator function
instead.
So can you try replacing prime_range(a,b) with primes(a,b)? If that
works we can change the doctest. When I wrote it I did not realise
the bif difference between the two,
John
>
> Cheers,
> gsw
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
