On Wednesday 14 January 2009, Bill Hart wrote: > I checked back through the correspondence I had and the timing I am > thinking of is for a 40 bit modulus at length 1,000,000. David and I > compared at the time and zn_poly version 0.4.1 took 2.06s compared to > FLINT at 2.37s, at that stage, on the old sage.math. > > The zn_poly changelog shows that David implemented the Schonhage/ > Nussbaumer FFT in zn_poly shortly after that point. After zn_poly > 0.7.0 David reported that the same multiplication took zn_poly 4.3 > billion cycles on sage.math, i.e. 2.39s which is actually slower than > the current FLINT. > > There's no indication in the changelog of any changes to the > multiplication code (though the tuning code was revamped) since that > time. > > Can I ask what architecture you got the above timings on Martin.
That's my Core2Duo 2.33Ghz Macbook Pro. You can try it on sage.math: sage: def f(p,n): ....: P = PolynomialRing(GF(next_prime(p)),'x') ....: f = P.random_element(n) ....: g = P.random_element(n) ....: t0 = cputime() ....: r0 = f*g ....: t0 = cputime(t0) ....: t1 = cputime() ....: r1 = f._mul_zn_poly(g) ....: t1 = cputime(t1) ....: assert(r0 == r1) ....: return p,n,t0,t1 ....: sage: for i in range(21): ....: f(2**47,2**i) ....: (140737488355328, 1, 0.0, 0.0) (140737488355328, 2, 0.0, 0.0) (140737488355328, 4, 0.0, 0.0) (140737488355328, 8, 0.0, 0.0) (140737488355328, 16, 0.0, 0.0) (140737488355328, 32, 0.0, 0.0) (140737488355328, 64, 0.0, 0.0) (140737488355328, 128, 0.0, 0.0) (140737488355328, 256, 0.0, 0.0) (140737488355328, 512, 0.0, 0.0) (140737488355328, 1024, 0.0, 0.0) (140737488355328, 2048, 0.0, 0.0) (140737488355328, 4096, 0.010000000000000009, 0.0) (140737488355328, 8192, 0.0099999999999997868, 0.010000000000000231) (140737488355328, 16384, 0.020000000000000018, 0.020000000000000018) (140737488355328, 32768, 0.049999999999999822, 0.050000000000000266) (140737488355328, 65536, 0.099999999999999645, 0.099999999999999645) (140737488355328, 131072, 0.28000000000000114, 0.19999999999999929) (140737488355328, 262144, 0.63000000000000256, 0.44000000000000128) (140737488355328, 524288, 1.5300000000000011, 1.0600000000000023) (140737488355328, 1048576, 3.0999999999999943, 2.1500000000000057) use my sage install (/home/malb/sage-3.2.2) for that. > It'll be interesting for both David and I if his Schonhage/Nussbaumer FFT is > that much better than the FLINT large integer FFT on certain > architectures. Cheers, Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF _www: http://www.informatik.uni-bremen.de/~malb _jab: martinralbre...@jabber.ccc.de --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
