On 22 Sep., 22:17, "John Cremona" <[EMAIL PROTECTED]> wrote:
> 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
Hi John,
although there is a difference between prime_range() and primes():
susanne-webers-computer:~/Public/sage/sage-3.1.3.alpha0 georgweber$
sage
----------------------------------------------------------------------
| SAGE Version 3.1.3.alpha0, Release Date: 2008-09-19 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: time for p in prime_range(32768, 100000): EllipticCurve(GF(p),
[0,1,1,10,13])
CPU times: user 66.35 s, sys: 14.32 s, total: 80.67 s
Wall time: 80.69 s
sage: exit
Exiting SAGE (CPU time 1m20.73s, Wall time 1m47.53s).
susanne-webers-computer:~/Public/sage/sage-3.1.3.alpha0 georgweber$
sage
----------------------------------------------------------------------
| SAGE Version 3.1.3.alpha0, Release Date: 2008-09-19 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: time for p in primes(32768, 100000): EllipticCurve(GF(p),
[0,1,1,10,13])
CPU times: user 67.46 s, sys: 14.42 s, total: 81.88 s
Wall time: 81.89 s
sage: exit
Exiting SAGE (CPU time 1m21.93s, Wall time 3m17.57s).
the function you originally used is slightly faster in our case, so no
need to change the doctest because of this.
And alas, replacing "prime_range()" with "primes()" does not make the
bug go away, it' still there (I tested it).
No, the answer is somehow related to the bound 32767. I mean, the
interval of width almost 70000 (from 32768 to 100000) working fine,
whereas an interval of width 1300 (from 31300 to 32600) does make
things crash --- there is IMHO no use in trying to make the code
faster or so. It would simply crash faster.
To just make the "ell_finite_field.py" doctest work, coding "around"
the bug we ran into, just change "prime_range(10000)", which is
equivalent to "prime_range(1, 10000)"
to
"prime_range(40000, 50000)"
or
"prime_range(90000, 100000)"
or
"prime_range(32768, 42768)"
or any reasonable range of length 10000 whose startpoint is 32768 or
above.
That does indeed make the doctest pass, I just tested it with
"prime_range(90000, 100000)"!
But come on, would that be satisfactory?
Cheers,
gsw
--~--~---------~--~----~------------~-------~--~----~
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-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
