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. 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. Bill. On 14 Jan, 15:31, Bill Hart <goodwillh...@googlemail.com> wrote: > On 13 Jan, 12:17, Martin Albrecht <m...@informatik.uni-bremen.de> > wrote: > > > The following is multiplication of two random polynomials over > > GF(140737488355328) of length n > > > n FLINT zn_poly > > 131072 0.292 0.220 > > 262144 0.612 0.454 > > 524288 1.522 1.028 > > 1048576 3.136 2.096 > > These are unexpected figures. > > Just out of interest, did you compile zn_poly with or without the > USE_FLINT option. > > I'm scratching my head a little, as last I heard, zn_poly was about > the same speed as FLINT for length 1,000,000. I suspect there has > either been a speed regression in FLINT which needs fixing, or David > has once again done something special!! > > BTW you will definitely find that for smaller moduli zn_poly is > considerably faster for the short to medium lengths. > > Bill. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
