1077
Comment:

← Revision 9 as of 20081114 13:42:00 ⇥
1087
converted to 1.6 markup

Deletions are marked like this.  Additions are marked like this. 
Line 11:  Line 11: 
'''Challenge''': On sage.math.washington.edu, compute all $a_p$ for p < 10^6 in less than 1 second wall time.  '''Challenge''': On sage.math.washington.edu, make a list of all $a_n$ for $n < 10^6$ in less than 1 second wall time. 
Line 13:  Line 13: 
See [:msri07/threadsafety: Thread Safety of the SAGE Libraries] for information about PARI thread safety.  See [[msri07/threadsafety Thread Safety of the SAGE Libraries]] for information about PARI thread safety. 
Problem: Implementation in SAGE parallel computation of elliptic curve a_p for all p up to some bound
In the abstract the problem of point counting modulo p, for lots of different p, is an "embarassingly parallelize  just do each p separately. The challenge here is *not* coming up with an algorithm, but figuring out how to implement something very efficient in SAGE that uses the PARI C library. In other words, you should make this session below run nearly n times as fast, on a machine with n cores:
sage: E = EllipticCurve('37a') sage: time v=E.anlist(10^6, pari_ints=True) CPU times: user 7.24 s, sys: 0.06 s, total: 7.30 s Wall time: 12.16
Challenge: On sage.math.washington.edu, make a list of all a_n for n < 10^6 in less than 1 second wall time.
See Thread Safety of the SAGE Libraries for information about PARI thread safety.
MAGMA times, by the way:
sage: magma.version() sage: F = magma(E) sage: t = magma.cputime() sage: time v=F.TracesOfFrobenius(10^6) sage: magma.cputime(t) 6.5