I am now absolutely certain MAGMA uses the FFT for multiplying polynomials over ZZ right down to degree 16 (when the bit length is 1000). This is a **much** lower cutoff than NTL uses, which is indicative of the fact that MAGMA's FFT is way better implemented.
I determined that MAGMA definitely uses FFT by doing a series of timings and plotting them on a graph. The characteristic FFT step-function timing graph was quite recognizable. They have definitely missed one major trick though, so if I can figure out how to get an implementation anywhere near as efficient as theirs, I will be able to beat it. Anyhow, I implemented the algorithm that Victor calls HomMul. I think he hardly uses it any more. I think I know why. It is as slow as a wet week. And there is very little that can be done to speed it up. As I suspected, it is a completely out of date and pretty much useless algorithm these days. It is completely dominated by the time taken to do modular reductions for large coefficients and the time taken to do Karatsuba for large degree and medium sized coefficients. It just reduces to Karatsuba for sufficiently small coefficients. The modular reductions could be sped up by working modulo fermat numbers (perhaps a factor of 4), but I've decided not to implement that for now, given that this is clearly not what MAGMA is using, and considering we are talking a factor of 40 too slow overall, which is clearly unattainable. If anyone sees any papers on extremely efficient implementations of Schoenhagen-Strassen, please let me know. Implementing it seems to be fairly simple, but one has to believe that Victor's implementation doesn't use all the known tricks. Bill. --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
