Happy New Year! I've written a new FFT for integer multiplication for MPIR. I'll write a series of posts over the next couple of days describing the strategy, what remains to be done, etc.
To whet your appetite, I include some timings for multiplying various sized integers. There is a trick called the square root 2 trick which I haven't implemented yet, so many of my timings are behind by 5-10% from what they will eventually be. It's also completely untuned at present! I also have not got an efficient negacyclic convolution yet, so the times for extremely large integers are still a little slow at this point too. Multiplication (new / mpir): iters 100 8364032: 6.8s / 8.0s 9409536: 9.8s / 8.7s 10455040: 10.8s / 9.6s 11500544: 12.3s / 12.6s 12546048: 14.7s / 15.3s 13591552: 14.0s / 14.2s 14637056: 14.9s / 15.3s 15682560: 16.0s / 14.5s 16728064: 16.8s / 19.5s 20910080: 24.3s / 23.2s 25092096: 28.5s / 33.1s 29274112: 33.1s / 31.8s 33456128: 37.4s / 46.0s 519168: iters 10000: 30.7s / 32.2s 2084864: iters 1000: 13.9s / 15.2s 134103040: iters 10: 17.0s / 24.8s 536608768: iters 1: 8.6s / 9.4s 2146959360: iters 1: 42.3s / 40.3s Apologies for the lack of data points and not doing a fantastic job of benchmarketing at this point. I'm about to go out with friends for New Years celebrations, so more later. Bill. -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to mpir-de...@googlegroups.com. To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.
