I finished implementing the truncated matrix fourier square root two transforms and I can finally multiply integers of all sizes. (Note that I'm still using the mpir Nussbaumer convolution for pointwise multiplications when the products get huge. Times will drop further when at some point in the future this is implemented independently.)
bits mpir new_fft 195840 1.149s 1.105s 261120 1.483s 1.415s 391296 0.261s 0.248s 521728 0.344s 0.315s 782592 0.577s 0.539s 1043456 0.706s 0.688s 1569024 1.229s 1.153s 2092032 1.543s 1.462s 3127296 0.283s 0.286s 4169728 0.357s 0.350s 6273024 0.621s 0.615s 8364032 0.831s 0.799s 12539904 1.441s 1.471s 16719872 0.230s 0.209s 25122816 0.379s 0.357s 33497088 0.524s 0.462s 50245632 0.833s 0.782s 66994176 1.596s 0.967s 100577280 1.906s 1.704s 134103040 2.784s 2.162s 201129984 3.971s 3.524s 268173312 5.146s 4.572s 402456576 7.548s 7.041s 536608768 9.841s 9.428s 804913152 15.48s 14.18s 1073217536 21.17s 19.33s 1610219520 31.64s 30.83s 2146959360 43.25s 39.17s 3220340736 70.14s 61.39s 4293787648 96.00s 80.15s 6441566208 150.2s 136.9s 8588754944 208.4s 183.3s 12883132416 327.4s 290.2s 17177509888 485.0s 382.2s Times for larger multiplications will drop further when I combine pointwise multiplications with the inverse matrix fourier transforms. There's a vast number of other things that could be done to speed it up. Here are some features of the new fft: * No tuning required for multiplications beyond about 3 million bits * Tuning is easy and should be exceeding fast * Works well for unbalanced multiplications * Relies on very few low level functions and butterflies which are candidates for assembly optimisation * Can be used easily for multiplying polynomials over the integers * heaps of test code (nearly half the code base) Disadvantages: * 5300 lines of code including test code, and not so many ways to reduce this -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.
