NTL cache-friendly FFT routines

[sagetrac-dmharvey]

I've written a more cache-friendly version of NTL's FFT routines. This may speed up NTL's polynomial arithmetic for polynomials of very high degree (e.g. > 100000) with small coefficients. For example I get a speedup of about 2x on sage.math.

BEFORE INCLUDING IN SAGE, someone needs to write some automatic tuning code, otherwise it might GREATLY SLOW DOWN arithmetic for small polynomials, which would be very stupid. See my website for code and more details:

http://math.harvard.edu/~dmharvey/code/ntl-fft/

CC: @vbraun

Component: basic arithmetic

Reviewer: Jean-Pierre Flori

Issue created by migration from https://trac.sagemath.org/ticket/1169

[sagetrac-mabshoff]

comment:2

David,

what is the status here? It seems that your website does contain the code.

Cheers,

Michael

[sagetrac-dmharvey]

comment:3

Yes it does, but it doesn't have tuning code and I don't have time to work on it now. Without proper tuning it is just as likely to make things slower.

[jpflori]

comment:5

I think this code has been integrated (somehow) into NTL 6.0.
So #14876 should supercede this.

[jpflori]

Reviewer: Jean-Pierre Flori

[jpflori]

comment:6

NTL 6.0.0 is on its way.