Differences between revisions 1 and 51 (spanning 50 versions)
 ⇤ ← Revision 1 as of 2009-04-09 02:57:07 → Size: 639 Editor: was Comment: ← Revision 51 as of 2009-06-07 16:21:32 → ⇥ Size: 15008 Editor: WilliamHart Comment: Deletions are marked like this. Additions are marked like this. Line 1: Line 1: = List of Computations where Sage is Noticeably Faster than Magma =* Large degree polynomial multiplication modulo n{{{ = List of Computations where Sage is Noticeably Faster than Magma.... =A binary of Sage 4.0.1-rc1 is available at /home/wbhart/sage-4.0.1.rc1/sage on enoA binary of Magma is available in /usr/local/magma-2.15/bin== Machines used ==eno: (a script to stop background processes for benchmarking purposes is available at /home/wbhart/script - but please stop it when done){{{4-core: model name : Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz}}}== Benchmarks ==* Sage is faster at factoring large numbers{{{sage: n=ZZ.random_element(10^29).next_prime()*ZZ.random_element(10^31).next_prime()sage: n16930046570310043023762335280694777006455061519242383863661sage: time qsieve(n)CPU times: user 0.00 s, sys: 0.00 s, total: 0.01 sWall time: 10.05 s([9594859962293488319946733153, 1764491262701368590074626129037], '')sage: n=ZZ.random_element(10^34).next_prime()*ZZ.random_element(10^36).next_prime()sage: n875905585594859559501188824768701936589874544145799136043283226938267sage: time qsieve(n)CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 sWall time: 82.13 s([1763643785109465131425492782015799, 496645407077197397173724652476563133], '')}}}{{{> n:=16930046570310043023762335280694777006455061519242383863661;> time Factorization(n);[ <9594859962293488319946733153, 1>, <1764491262701368590074626129037, 1> ]Time: 30.640> n:=875905585594859559501188824768701936589874544145799136043283226938267;> time Factorization(n);[ <1763643785109465131425492782015799, 1>,<496645407077197397173724652476563133, 1> ]Time: 284.390}}}* Sage is a tad faster at computing partitions{{{sage: time z=number_of_partitions(1000000)CPU times: user 0.05 s, sys: 0.00 s, total: 0.05 sWall time: 0.05 ssage: magma.eval('time z:=NumberOfPartitions(1000000)')'Time: 233.960'sage: 233.96/0.054679.20000000000}}}* .... and Bernoulli numbers{{{sage: time z=bernoulli(10000);CPU times: user 0.04 s, sys: 0.00 s, total: 0.04 sWall time: 0.04 s}}}{{{> time z:=BernoulliNumber(10000);Time: 464.250}}}{{{464.25/0.04 = 11606.25}}}* Computing factorials (Sage is more than twice the speed).{{{[[email protected] sage-4.0.1.rc1]\$ ./sage----------------------------------------------------------------------| Sage Version 4.0.1.rc1, Release Date: 2009-06-04 || Type notebook() for the GUI, and license() for information. |----------------------------------------------------------------------sage: magma.version()((2, 15, 8), 'V2.15-8')sage: time n = factorial(10^6)CPU times: user 0.57 s, sys: 0.01 s, total: 0.58 sWall time: 0.59 ssage: time magma.eval('time n := Factorial(10^6);')CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 sWall time: 1.45 s'Time: 1.440'sage: time magma.eval('time n := Factorial(10^7);')CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 sWall time: 27.33 s'Time: 27.300'sage: time n = factorial(10^7)CPU times: user 11.50 s, sys: 0.25 s, total: 11.75 sWall time: 11.75 ssage: 27.30/11.752.32340425531915}}}* Large degree polynomial multiplication modulo n (Sage is three times as fast).{{{[[email protected] sage-4.0.1.rc1]\$ ./sage----------------------------------------------------------------------| Sage Version 4.0.1.rc1, Release Date: 2009-06-04 || Type notebook() for the GUI, and license() for information. |----------------------------------------------------------------------sage: magma.version()((2, 15, 8), 'V2.15-8') Line 8: Line 124: CPU times: user 0.19 s, sys: 0.00 s, total: 0.19 sWall time: 0.19 s}}}In my initial tests this seems to be nearly 10 times faster in Sage than in Magma!{{{ CPU times: user 0.18 s, sys: 0.00 s, total: 0.18 sWall time: 0.18 s Line 15: Line 127: sage: f = magma('%s![Random(0,10000000) : i in [1..3200]]'%S.name()) sage: f = magma(ff) Line 17: Line 129: 'Time: 1.690'sage: 1.69/0.198.89473684210526}}} 'Time: 0.530'}}}* Large degree polynomial multiplication over ZZ (Sage is five times as fast).{{{----------------------------------------------------------------------| Sage Version 4.0.1.rc1, Release Date: 2009-06-04 || Type notebook() for the GUI, and license() for information. |----------------------------------------------------------------------sage: R.=ZZ['x']sage: ff = R.random_element(degree=3200)sage: gg = R.random_element(degree=3200)sage: time v = [ff*gg^i for i in [1..40]]CPU times: user 22.29 s, sys: 0.22 s, total: 22.50 sWall time: 22.51 ssage: S = magma(R)sage: f = magma(ff)sage: g = magma(gg)sage: magma.eval('time z:=[%s*%s^i : i in [1..40]]'%(f.name(), g.name()))'Time: 112.820'}}}* Application of polynomial multiplication to modular forms -- Computing the q-expansion of the Delta function:{{{sage: time d = delta_qexp(10^6)CPU times: user 8.41 s, sys: 0.25 s, total: 8.65 ssage: magma.eval('R := PowerSeriesRing(IntegerRing());')sage: magma.eval('time d := Delta(q + O(q^(10^6)));')'Time: 31.700'sage: 31.7/8.63.68604651162791}}}* Division of a polynomial by an integer is faster in Sage{{{sage: R=ZZ['x']sage: f = 3876877658987687 * R.random_element(10000)sage: timeit("f//3876877658987687")625 loops, best of 3: 294 Âµs per loopsage: ff = magma(f)sage: magma.eval('time z:=[%s div 3876877658987687 : i in [1..1000]]'%(ff.name()))'Time: 1.010'sage: 0.00101/0.0002943.43537414965986}}}* Sage is asymptotically faster for Quotrem over ZZ (used in computation of Sturm sequences){{{sage: R.=ZZ['x']sage: ff = R.random_element(degree=10000)sage: gg = R.random_element(degree=5000)sage: time v=ff.quo_rem(gg)CPU times: user 0.17 s, sys: 0.02 s, total: 0.18 sWall time: 0.18 ssage: f=magma(ff)sage: g=magma(gg)sage: magma.eval('time z:=Quotrem(%s,%s)'%(f.name(), g.name()))'Time: 1.970'}}}* Polynomial GCD over ZZ is faster in Sage{{{sage: R=ZZ['x']sage: f=R.random_element(100)sage: g=R.random_element(100)sage: h=R.random_element(100)sage: s=f*gsage: t=f*hsage: time v = [s.gcd(t) for i in [1..1000]]CPU times: user 0.15 s, sys: 0.00 s, total: 0.16 sWall time: 0.16 ssage: ss=magma(s)sage: tt=magma(t)sage: magma.eval('time u:=[Gcd(%s,%s) : i in [1..1000]]'%(ss.name(), tt.name()))'Time: 1.230'}}}* Exact logarithm of integers is faster in Sage.{{{sage: def zlog(m, n, k):....: for i in range(0, m/1000):....: a = ZZ.random_element(n)+2....: b = ZZ.random_element(k)....: c = a^b....: for j in range (0, 1000):....: c.exact_log(a)....:sage: time zlog(1000000, 100, 100)CPU times: user 0.62 s, sys: 0.23 s, total: 0.85 sWall time: 0.85 ssage: time zlog(1000000, 2^50, 100)CPU times: user 2.10 s, sys: 0.27 s, total: 2.36 sWall time: 2.36 ssage: time zlog(1000000, 100, 2^10)CPU times: user 1.75 s, sys: 0.26 s, total: 2.01 sWall time: 2.01 s}}}{{{> procedure z_log(m, n, k)procedure> for i := 0 to (m div 1000) doprocedure|for> a := Random(n) + 2;procedure|for> b := Random(k);procedure|for> c := a^b;procedure|for> for j := 1 to 1000 doprocedure|for|for> d := Ilog(a, c);procedure|for|for> end for;procedure|for> end for;procedure> end procedure;> time z_log(1000000, 100, 100);Time: 1.180> time z_log(1000000, 2^50, 100);Time: 5.830> time z_log(1000000, 100, 2^10);Time: 6.450}}}* Multivariate polynomial multiplication over a finite field (Sage is more than twice as fast at this "Fateman benchmark"):{{{sage: R. = GF(389)[]sage: f = (x+y+z+1)^20sage: time g = f*(f+1)CPU times: user 0.12 s, sys: 0.00 s, total: 0.12 sWall time: 0.12 ssage: ff = magma(f)sage: time magma.eval('time g := %s*(%s+1);'%(ff.name(),ff.name()))CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 sWall time: 0.27 s'Time: 0.250'}}}* Rank of random dense matrices over GF(2) (Sage is more than twice the speed).{{{----------------------------------------------------------------------| Sage Version 4.0.1.rc1, Release Date: 2009-06-04 || Type notebook() for the GUI, and license() for information. |----------------------------------------------------------------------sage: A = random_matrix(GF(2),10^4,10^4)sage: %time A.rank()CPU times: user 1.20 s, sys: 0.01 s, total: 1.20 sWall time: 1.20 s9999sage: A = random_matrix(GF(2),2*10^4,2*10^4)sage: %time A.rank()CPU times: user 9.34 s, sys: 0.02 s, total: 9.36 sWall time: 9.36 s19937sage: A = random_matrix(GF(2),2*10^4,2*10^4)sage: %time A.echelonize(algorithm='pluq')CPU times: user 6.79 s, sys: 0.01 s, total: 6.80 sWall time: 6.80 ssage: A = random_matrix(GF(2),3.2*10^4,3.2*10^4)sage: %time A.rank()CPU times: user 31.57 s, sys: 0.05 s, total: 31.62 sWall time: 31.63 s19937sage: %time A.echelonize(algorithm='pluq')CPU times: user 27.10 s, sys: 0.04 s, total: 27.14 sWall time: 27.15 s}}}{{{Magma V2.15-8 Thu Jun 4 2009 21:58:05 on eno [Seed = 3168701748]Type ? for help. Type -D to quit.> A:=RandomMatrix(GF(2),10^4,10^4);> time Rank(A);9999Time: 3.040> A:=RandomMatrix(GF(2),2*10^4,2*10^4);> time Rank(A);19999Time: 17.750> A:=RandomMatrix(GF(2),32*10^3,32*10^3);> time Rank(A);31999Time: 62.980}}}* Fast HNF and determinant for integer matrices, especially as the entries get large.{{{[[email protected] sage-4.0.1]\$ ./sage----------------------------------------------------------------------| Sage Version 4.0.1, Release Date: 2009-06-06 || Type notebook() for the GUI, and license() for information. |----------------------------------------------------------------------sage: a = random_matrix(ZZ,300,x=-2^128,y=2^128)sage: time d = a.det()CPU times: user 5.97 s, sys: 0.02 s, total: 5.98 sWall time: 5.99 ssage: b = magma(a)sage: time magma.eval('time d := Determinant(%s);'%b.name())CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 sWall time: 35.59 s'Time: 35.500'sage: time h = a.hermite_form()CPU times: user 23.99 s, sys: 0.10 s, total: 24.09 sWall time: 24.17 ssage: time magma.eval('time h := HermiteForm(%s);'%b.name())CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 sWall time: 90.31 s'Time: 90.200'}}}A bigger det where Sage is *ten* times faster:{{{sage: a = random_matrix(ZZ,1000,x=-2^128,y=2^128)sage: time d = a.det()CPU times: user 122.57 s, sys: 0.25 s, total: 122.82 sWall time: 122.90 ssage: b = magma(a)sage: time magma.eval('time d := Determinant(%s);'%b.name())CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 sWall time: 1262.36 s'Time: 1261.980'}}}* Characteristic polynomials of integer matrices with ''large entries'' (here Sage is over 4 times faster):{{{sage: a = random_matrix(ZZ,100,x=-2^512,y=2^512)sage: time f = a.charpoly()CPU times: user 16.76 s, sys: 0.00 s, total: 16.76 sWall time: 16.76 ssage: b = magma(a)sage: time magma.eval('time f := CharacteristicPolynomial(%s)'%b.name())CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 sWall time: 71.27 s'Time: 71.120'sage: 71.120/16.764.24343675417661}}}* Modular composition over GF(2){{{sage: P. = GF(2)[] sage: d = 5*10^4; f,g,h = P.random_element(d),P.random_element(d),P.random_element(d)sage: %time r = f.modular_composition(g,h) CPU times: user 2.69 s, sys: 0.01 s, total: 2.69 s Wall time: 2.70 s }}}{{{sage: fM,gM,hM = magma(f),magma(g),magma(h)sage: t = magma.cputime(); rM = fM.ModularComposition(gM,hM); magma.cputime(t)13.44sage: rM == magma(r)True}}}{{{sage: d = 5*10^5; f,g,h = P.random_element(d),P.random_element(d),P.random_element(d)sage: %time r = f.modular_composition(g,h)^ACPU times: user 288.13 s, sys: 0.14 s, total: 288.26 sWall time: 288.34 ssage: %time r = f.modular_composition(g,h,algorithm='ntl')CPU times: user 303.45 s, sys: 0.04 s, total: 303.49 sWall time: 303.60 ssage: fM,gM,hM = magma(f),magma(g),magma(h)sage: t = magma.cputime(); rM = fM.ModularComposition(gM,hM); magma.cputime(t)832.03999999999996}}}* Sage computes ranks of elliptic curves and generators, fast... and correctly (see Rogers, N.F., Rank Computations for the congruent number elliptic curves, Experimental Mathematics, 9 (2000), 591-594.){{{sage: D=6611719866sage: E=EllipticCurve([0,0,0,-D^2,0])sage: time E.rank()CPU times: user 0.01 s, sys: 0.01 s, total: 0.02 sWall time: 3.20 s6sage: time E.gens()CPU times: user 0.07 s, sys: 0.06 s, total: 0.13 sWall time: 5.89 s[(247424194842066/37249 : 373863724821481185720/7189057 : 1), (165541824817/16 : 51806810701954601/64 : 1), (15062000442 : 1660900534642656 : 1), (548503784857/36 : -365985935192610019/216 : 1), (11638545941238203281/246490000 : 39314069377271931544287972679/3869893000000 : 1), (514136077885092448181278/169697035249 : -368651568597676351513664298941602072/69905505791578807 : 1)]}}}{{{> D:=6611719866;> E:=EllipticCurve([0,0,0,-D^2,0]);> time Rank(E);Warning: rank computed (2) is only a lower bound(It may still be correct, though)2Time: 9.640> time Generators(E);Height bound (50.6331) on point search is too large -- reducing to 15.0000This means that the computed group may only generate a group of finiteindex in the actual group.[ (-6611719866 : 0 : 1), (0 : 0 : 1), (-156630507 : -82723846945707 : 1),(213545146551959209/902500 : -98642697824946986013197323/857375000 : 1) ]Time: 57.970}}}* Computation with Brandt modules, i.e., using quaternion algebras to compute Hecke module isomorphic to free abelian group on enhanced supersingular elliptic curves in characteristic p (in the example below, Sage is over 4 times faster):{{{sage: time B = BrandtModule(59,15)CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 sWall time: 0.00 ssage: time B.hecke_matrix(2)CPU times: user 9.29 s, sys: 0.27 s, total: 9.56 sWall time: 9.57 s116 x 116 dense matrix over Rational Fieldsage: time B.hecke_matrix(3)CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 sWall time: 0.03 s116 x 116 dense matrix over Rational Fieldsage: time B.hecke_matrix(5)CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 sWall time: 0.02 s116 x 116 dense matrix over Rational Fieldsage: time B.hecke_matrix(7)CPU times: user 0.02 s, sys: 0.00 s, total: 0.03 sWall time: 0.03 s116 x 116 dense matrix over Rational Fieldsage: magma.eval('time B := BrandtModule(59,15);')'Time: 40.820'sage: magma.eval('time T2 := HeckeOperator(B,2);')'Time: 0.330'sage: magma.eval('time T3 := HeckeOperator(B,3);')'Time: 0.360'sage: magma.eval('time T5 := HeckeOperator(B,5);')'Time: 0.390'sage: magma.eval('time T7 := HeckeOperator(B,7);')'Time: 0.400'}}}

List of Computations where Sage is Noticeably Faster than Magma....

A binary of Sage 4.0.1-rc1 is available at /home/wbhart/sage-4.0.1.rc1/sage on eno

A binary of Magma is available in /usr/local/magma-2.15/bin

Machines used

eno: (a script to stop background processes for benchmarking purposes is available at /home/wbhart/script - but please stop it when done)

4-core: model name      : Intel(R) Core(TM)2 Quad CPU    Q6600  @ 2.40GHz

Benchmarks

* Sage is faster at factoring large numbers

sage: n=ZZ.random_element(10^29).next_prime()*ZZ.random_element(10^31).next_prime()
sage: n
16930046570310043023762335280694777006455061519242383863661
sage: time qsieve(n)
CPU times: user 0.00 s, sys: 0.00 s, total: 0.01 s
Wall time: 10.05 s
([9594859962293488319946733153, 1764491262701368590074626129037], '')

sage: n=ZZ.random_element(10^34).next_prime()*ZZ.random_element(10^36).next_prime()
sage: n
875905585594859559501188824768701936589874544145799136043283226938267
sage: time qsieve(n)
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 82.13 s

([1763643785109465131425492782015799, 496645407077197397173724652476563133],
'')

> n:=16930046570310043023762335280694777006455061519242383863661;
> time Factorization(n);
[ <9594859962293488319946733153, 1>, <1764491262701368590074626129037, 1> ]
Time: 30.640

> n:=875905585594859559501188824768701936589874544145799136043283226938267;
> time Factorization(n);
[ <1763643785109465131425492782015799, 1>,
<496645407077197397173724652476563133, 1> ]
Time: 284.390

* Sage is a tad faster at computing partitions

sage: time z=number_of_partitions(1000000)
CPU times: user 0.05 s, sys: 0.00 s, total: 0.05 s
Wall time: 0.05 s

sage: magma.eval('time z:=NumberOfPartitions(1000000)')
'Time: 233.960'

sage: 233.96/0.05
4679.20000000000

* .... and Bernoulli numbers

sage: time z=bernoulli(10000);
CPU times: user 0.04 s, sys: 0.00 s, total: 0.04 s
Wall time: 0.04 s

> time z:=BernoulliNumber(10000);
Time: 464.250

464.25/0.04 = 11606.25

* Computing factorials (Sage is more than twice the speed).

[[email protected] sage-4.0.1.rc1]\$ ./sage
----------------------------------------------------------------------
| Sage Version 4.0.1.rc1, Release Date: 2009-06-04                   |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: magma.version()
((2, 15, 8), 'V2.15-8')
sage: time n = factorial(10^6)
CPU times: user 0.57 s, sys: 0.01 s, total: 0.58 s
Wall time: 0.59 s
sage: time magma.eval('time n := Factorial(10^6);')
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 1.45 s
'Time: 1.440'
sage: time magma.eval('time n := Factorial(10^7);')
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 27.33 s
'Time: 27.300'
sage: time n = factorial(10^7)
CPU times: user 11.50 s, sys: 0.25 s, total: 11.75 s
Wall time: 11.75 s
sage: 27.30/11.75
2.32340425531915

* Large degree polynomial multiplication modulo n (Sage is three times as fast).

[[email protected] sage-4.0.1.rc1]\$ ./sage
----------------------------------------------------------------------
| Sage Version 4.0.1.rc1, Release Date: 2009-06-04                   |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: magma.version()
((2, 15, 8), 'V2.15-8')
sage: R.<t> = Zmod(next_prime(8000^3))[]
sage: ff = R.random_element(degree=3200)
sage: time v = [ff*ff for i in [1..100]]
CPU times: user 0.18 s, sys: 0.00 s, total: 0.18 s
Wall time: 0.18 s
sage: S = magma(R)
sage: f = magma(ff)
sage: magma.eval('time z:=[%s*%s : i in [1..100]]'%(f.name(), f.name()))
'Time: 0.530'

* Large degree polynomial multiplication over ZZ (Sage is five times as fast).

----------------------------------------------------------------------
| Sage Version 4.0.1.rc1, Release Date: 2009-06-04                   |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: R.<x>=ZZ['x']
sage: ff = R.random_element(degree=3200)
sage: gg = R.random_element(degree=3200)
sage: time v = [ff*gg^i for i in [1..40]]
CPU times: user 22.29 s, sys: 0.22 s, total: 22.50 s
Wall time: 22.51 s
sage: S = magma(R)
sage: f = magma(ff)
sage: g = magma(gg)
sage: magma.eval('time z:=[%s*%s^i : i in [1..40]]'%(f.name(), g.name()))
'Time: 112.820'

* Application of polynomial multiplication to modular forms -- Computing the q-expansion of the Delta function:

sage: time d = delta_qexp(10^6)
CPU times: user 8.41 s, sys: 0.25 s, total: 8.65 s
sage: magma.eval('R<q> := PowerSeriesRing(IntegerRing());')
sage: magma.eval('time d := Delta(q + O(q^(10^6)));')
'Time: 31.700'
sage: 31.7/8.6
3.68604651162791

* Division of a polynomial by an integer is faster in Sage

sage: R=ZZ['x']
sage: f = 3876877658987687 * R.random_element(10000)
sage: timeit("f//3876877658987687")
625 loops, best of 3: 294 Âµs per loop
sage: ff = magma(f)
sage: magma.eval('time z:=[%s div 3876877658987687 : i in [1..1000]]'%(ff.name()))
'Time: 1.010'
sage: 0.00101/0.000294
3.43537414965986

* Sage is asymptotically faster for Quotrem over ZZ (used in computation of Sturm sequences)

sage: R.<x>=ZZ['x']
sage: ff = R.random_element(degree=10000)
sage: gg = R.random_element(degree=5000)
sage: time v=ff.quo_rem(gg)
CPU times: user 0.17 s, sys: 0.02 s, total: 0.18 s
Wall time: 0.18 s

sage: f=magma(ff)
sage: g=magma(gg)
sage: magma.eval('time z:=Quotrem(%s,%s)'%(f.name(), g.name()))
'Time: 1.970'

* Polynomial GCD over ZZ is faster in Sage

sage: R=ZZ['x']
sage: f=R.random_element(100)
sage: g=R.random_element(100)
sage: h=R.random_element(100)
sage: s=f*g
sage: t=f*h
sage: time v = [s.gcd(t) for i in [1..1000]]
CPU times: user 0.15 s, sys: 0.00 s, total: 0.16 s
Wall time: 0.16 s

sage: ss=magma(s)
sage: tt=magma(t)
sage: magma.eval('time u:=[Gcd(%s,%s) : i in [1..1000]]'%(ss.name(), tt.name()))
'Time: 1.230'

* Exact logarithm of integers is faster in Sage.

sage: def zlog(m, n, k):
....:         for i in range(0, m/1000):
....:             a = ZZ.random_element(n)+2
....:             b = ZZ.random_element(k)
....:             c = a^b
....:             for j in range (0, 1000):
....:                 c.exact_log(a)
....:
sage: time zlog(1000000, 100, 100)
CPU times: user 0.62 s, sys: 0.23 s, total: 0.85 s
Wall time: 0.85 s
sage: time zlog(1000000, 2^50, 100)
CPU times: user 2.10 s, sys: 0.27 s, total: 2.36 s
Wall time: 2.36 s
sage: time zlog(1000000, 100, 2^10)
CPU times: user 1.75 s, sys: 0.26 s, total: 2.01 s
Wall time: 2.01 s

> procedure z_log(m, n, k)
procedure> for i := 0 to (m div 1000) do
procedure|for> a := Random(n) + 2;
procedure|for> b := Random(k);
procedure|for> c := a^b;
procedure|for> for j := 1 to 1000 do
procedure|for|for> d := Ilog(a, c);
procedure|for|for> end for;
procedure|for> end for;
procedure> end procedure;
> time z_log(1000000, 100, 100);
Time: 1.180
> time z_log(1000000, 2^50, 100);
Time: 5.830
> time z_log(1000000, 100, 2^10);
Time: 6.450

* Multivariate polynomial multiplication over a finite field (Sage is more than twice as fast at this "Fateman benchmark"):

sage: R.<x,y,z> = GF(389)[]
sage: f = (x+y+z+1)^20
sage: time g = f*(f+1)
CPU times: user 0.12 s, sys: 0.00 s, total: 0.12 s
Wall time: 0.12 s
sage: ff = magma(f)
sage: time magma.eval('time g := %s*(%s+1);'%(ff.name(),ff.name()))
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.27 s
'Time: 0.250'

* Rank of random dense matrices over GF(2) (Sage is more than twice the speed).

----------------------------------------------------------------------
| Sage Version 4.0.1.rc1, Release Date: 2009-06-04                   |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: A = random_matrix(GF(2),10^4,10^4)
sage: %time A.rank()
CPU times: user 1.20 s, sys: 0.01 s, total: 1.20 s
Wall time: 1.20 s
9999

sage: A = random_matrix(GF(2),2*10^4,2*10^4)
sage: %time A.rank()
CPU times: user 9.34 s, sys: 0.02 s, total: 9.36 s
Wall time: 9.36 s
19937

sage: A = random_matrix(GF(2),2*10^4,2*10^4)
sage: %time A.echelonize(algorithm='pluq')
CPU times: user 6.79 s, sys: 0.01 s, total: 6.80 s
Wall time: 6.80 s

sage: A = random_matrix(GF(2),3.2*10^4,3.2*10^4)
sage: %time A.rank()
CPU times: user 31.57 s, sys: 0.05 s, total: 31.62 s
Wall time: 31.63 s
19937

sage: %time A.echelonize(algorithm='pluq')
CPU times: user 27.10 s, sys: 0.04 s, total: 27.14 s
Wall time: 27.15 s

Magma V2.15-8     Thu Jun  4 2009 21:58:05 on eno      [Seed = 3168701748]
Type ? for help.  Type <Ctrl>-D to quit.
> A:=RandomMatrix(GF(2),10^4,10^4);
> time Rank(A);
9999
Time: 3.040

> A:=RandomMatrix(GF(2),2*10^4,2*10^4);
> time Rank(A);
19999
Time: 17.750

> A:=RandomMatrix(GF(2),32*10^3,32*10^3);
> time Rank(A);
31999
Time: 62.980

* Fast HNF and determinant for integer matrices, especially as the entries get large.

[[email protected] sage-4.0.1]\$ ./sage
----------------------------------------------------------------------
| Sage Version 4.0.1, Release Date: 2009-06-06                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: a = random_matrix(ZZ,300,x=-2^128,y=2^128)
sage: time d = a.det()
CPU times: user 5.97 s, sys: 0.02 s, total: 5.98 s
Wall time: 5.99 s
sage: b = magma(a)
sage: time magma.eval('time d := Determinant(%s);'%b.name())
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 35.59 s
'Time: 35.500'
sage: time h = a.hermite_form()
CPU times: user 23.99 s, sys: 0.10 s, total: 24.09 s
Wall time: 24.17 s
sage: time magma.eval('time h := HermiteForm(%s);'%b.name())
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 90.31 s
'Time: 90.200'

A bigger det where Sage is *ten* times faster:

sage: a = random_matrix(ZZ,1000,x=-2^128,y=2^128)
sage: time d = a.det()
CPU times: user 122.57 s, sys: 0.25 s, total: 122.82 s
Wall time: 122.90 s
sage: b = magma(a)
sage: time magma.eval('time d := Determinant(%s);'%b.name())
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 1262.36 s
'Time: 1261.980'

* Characteristic polynomials of integer matrices with large entries (here Sage is over 4 times faster):

sage: a = random_matrix(ZZ,100,x=-2^512,y=2^512)
sage: time f = a.charpoly()
CPU times: user 16.76 s, sys: 0.00 s, total: 16.76 s
Wall time: 16.76 s
sage: b = magma(a)
sage: time magma.eval('time f := CharacteristicPolynomial(%s)'%b.name())
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 71.27 s
'Time: 71.120'
sage: 71.120/16.76
4.24343675417661

* Modular composition over GF(2)

sage: P.<x> = GF(2)[]
sage: d = 5*10^4; f,g,h = P.random_element(d),P.random_element(d),P.random_element(d)
sage: %time r = f.modular_composition(g,h)
CPU times: user 2.69 s, sys: 0.01 s, total: 2.69 s
Wall time: 2.70 s

sage: fM,gM,hM = magma(f),magma(g),magma(h)
sage: t = magma.cputime(); rM = fM.ModularComposition(gM,hM); magma.cputime(t)
13.44
sage: rM == magma(r)
True

sage: d = 5*10^5; f,g,h = P.random_element(d),P.random_element(d),P.random_element(d)
sage: %time r = f.modular_composition(g,h)
^ACPU times: user 288.13 s, sys: 0.14 s, total: 288.26 s
Wall time: 288.34 s

sage: %time r = f.modular_composition(g,h,algorithm='ntl')
CPU times: user 303.45 s, sys: 0.04 s, total: 303.49 s
Wall time: 303.60 s

sage: fM,gM,hM = magma(f),magma(g),magma(h)
sage: t = magma.cputime(); rM = fM.ModularComposition(gM,hM); magma.cputime(t)
832.03999999999996

* Sage computes ranks of elliptic curves and generators, fast... and correctly (see Rogers, N.F., Rank Computations for the congruent number elliptic curves, Experimental Mathematics, 9 (2000), 591-594.)

sage: D=6611719866
sage: E=EllipticCurve([0,0,0,-D^2,0])
sage:  time E.rank()
CPU times: user 0.01 s, sys: 0.01 s, total: 0.02 s
Wall time: 3.20 s
6
sage:  time E.gens()
CPU times: user 0.07 s, sys: 0.06 s, total: 0.13 s
Wall time: 5.89 s

[(247424194842066/37249 : 373863724821481185720/7189057 : 1),
(165541824817/16 : 51806810701954601/64 : 1),
(15062000442 : 1660900534642656 : 1),
(548503784857/36 : -365985935192610019/216 : 1),
(11638545941238203281/246490000 : 39314069377271931544287972679/3869893000000 : 1),
(514136077885092448181278/169697035249 : -368651568597676351513664298941602072/69905505791578807 : 1)]

> D:=6611719866;
> E:=EllipticCurve([0,0,0,-D^2,0]);
> time Rank(E);
Warning: rank computed (2) is only a lower bound
(It may still be correct, though)
2
Time: 9.640
> time Generators(E);
Height bound (50.6331) on point search is too large -- reducing to 15.0000
This means that the computed group may only generate a group of finite
index in the actual group.
[ (-6611719866 : 0 : 1), (0 : 0 : 1), (-156630507 : -82723846945707 : 1),
(213545146551959209/902500 : -98642697824946986013197323/857375000 : 1) ]
Time: 57.970

* Computation with Brandt modules, i.e., using quaternion algebras to compute Hecke module isomorphic to free abelian group on enhanced supersingular elliptic curves in characteristic p (in the example below, Sage is over 4 times faster):

sage: time B = BrandtModule(59,15)
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
sage: time B.hecke_matrix(2)
CPU times: user 9.29 s, sys: 0.27 s, total: 9.56 s
Wall time: 9.57 s
116 x 116 dense matrix over Rational Field
sage: time B.hecke_matrix(3)
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.03 s
116 x 116 dense matrix over Rational Field
sage: time B.hecke_matrix(5)
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s
116 x 116 dense matrix over Rational Field
sage: time B.hecke_matrix(7)
CPU times: user 0.02 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.03 s
116 x 116 dense matrix over Rational Field

sage: magma.eval('time B := BrandtModule(59,15);')
'Time: 40.820'
sage: magma.eval('time T2 := HeckeOperator(B,2);')
'Time: 0.330'
sage: magma.eval('time T3 := HeckeOperator(B,3);')
'Time: 0.360'
sage: magma.eval('time T5 := HeckeOperator(B,5);')
'Time: 0.390'
sage: magma.eval('time T7 := HeckeOperator(B,7);')
'Time: 0.400'

sagebeatsmagma (last edited 2009-06-12 09:39:03 by was)