> 1d: 0.00168s, 0.01692s and 0.0453s > mod-1d: 0.00067s, 0.00981s, 0.0244s > > Your timings (on a 2.2 Ghz Opteron!!) > > 1-d:0.00018, 0.009, 0.034 > mod 1-d: 7.5e-5, 0.0022, 0.007 > > So you look to be well ahead of Magma! Did you do something special > for small moduli, such as packing multiple coefficients into a limb? >
No. I'm using int * as data structure for polynomial in the modular gcd algorithm, and it should work with modulo < 2^31 (there is a small asm inline code for multiplication + addition followed by mod reduction but it is mainly intended for 32 bits i386 processors to avoid using long long which is somewhat stupid since the processor has an imul and idiv instructions that can handle signed 32 bit multiplication to 2 register over 64 bits). Since division inside the gcd algorithm involves most of the time a polynomial of degree n by a polynomial of degree n-1, I have also implemented a special case for handling such divisions (this spares one mod reduction over 2 and compute the remainder in one loop instead of 2). I also hope that my time is accurate... If you have the opportunity of running 2-d to 4-d fermat tests, I'd be very interested to get the results (I don't know if inputs are available for magma somewhere). Thanks! --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
