Bill Hart wrote: > This page apparently answers the question definitively: > > http://magma.maths.usyd.edu.au/magma/Features/node93.html
And this paper tells me exactly what I want to know: http://www.mathematik.hu-berlin.de/~gaggle/EVENTS/2006/BRENT60/presentations/Allan%20Steel%20-%20Reduce%20everything%20to%20multiplication.pdf So they actually don't use Fourier over the reals. They just use arithmetic modulo a Fermat prime, same as Victor (though in other situations they use the Kronecker-Strassen trick). I looked more closely at Victor's implementation of SS, and there are two things that seem wrong. Firstly, David, I think you are right, it isn't cache friendly. A recursive algorithm is more cache friendly than an iterative algorithm, which I think Victor is using. Secondly, the pointwise multiplications are taking WAAAY too long. There are only 512 or so pointwise multiplications of bitsize 1000 or so to complete. Contrast this with multiplying via Karatsuba instead of SS, where there are around 8560 multiplications of this size to complete. Yet the whole of Karatsuba finishes in just 25 seconds as opposed to 4 seconds for just the multiplications alone in Victor's SS. 8560/25 ~ 342 Victor pointwise multiplications only 512/4 = 128 Karatsuba multiplications + considerable overheads So there is nearly a factor of 3 going missing somewhere here, and I haven't taken into account all the overheads in Karatsuba, which is probably another factor of roughly 2-3 as I measure it (though there are also overheads in Victor's pointwise multiplication segment which may amount to almost as much - though I wonder if these might also be eliminated somehow). So there is a big problem somewhere in Victor's SS. It must be overheads in Victor's multiplication algorithm as he has implemented it over GMP. I will run some tests later in the week to check this. At one stage MAGMA were boasting that their integer multiplication was a lot faster than GMP, but I suspect GMP has caught them up now, and I think it only made a difference to numbers of a million bits or more. MAGMA now seem to claim that they use mpn's to multiply large integers, which suggests they use the GMP algorithm, not their own home brew as they used to. Now I kind of like the idea of doing an FFT implementation over the reals just to see if it is any faster for this application. If MAGMA doesn't use it and it turns out to be faster....... --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
