I have finally managed to implement the truncated sqrt2 transforms and
the matrix fourier sqrt2 transforms. This enables me to get actual
timings vs mpir. These times for multiplying two integers of the given
numbers of bits.
On my machine the mpir FFT starts beating toom algorithms at about
160000 bits, so I start the comparison just above that point. There
are timings missing because I do not yet have the truncated matrix
fourier sqrt2 transforms implemented. Also, the latter timings make
use of the mpir Nussbaumer convolution as I do not have this
implemented yet.
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
....
536608768 9.841s 9.428s
....
1073217536 21.17s 19.33s
....
2146959360 43.25s 39.17s
....
4293787648 96.00s 80.15s
....
8588754944 208.4s 183.3s
....
17177509888 485.0s 382.2s
If anyone is interested in helping with the implementation, one thing
we need is a fast naive acyclic convolution for 1 and 2 limb
coefficients.
So if [a0, a1, ...., a{n-1}], [b0, b1, ..., b{n-1}] is a pair of
vectors with entries that are one limb (or resp. two limbs) then the
convolution is simply the vector
[c0, c1, ...., c{n-1}] where
ci = sum_{k + j = i mod n} (-1)^{(k+j)/n} ak.bj mod B^s
where s = 1 (resp. 2) and B = 2^GMP_LIMB_BITS
If anyone would like to implement this (we need a 1 limb and a 2 limb
version) that would go a long way towards getting the Nussbaumer
convolution implemented.
Bill.
--
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.
