<commit_before>FLINT 2 Roadmap
===============

This documents sets out a list of functions which have been implemented in flint2 which are
not intended to be optimal implementations, and thus can be significantly improved in future
and also lists functions which have not been added, which would improve performance and
functionality were they added. 

Thus this document serves as a roadmap. Functions listed here are candidates for contributors
to consider working on to improve flint2.

fmpz_poly
---------

fmpz_poly_mul_SS (mul_SS) - missing
   Schoenhage-Strassen algorithm (SSA) for multiplying polynomials. Note SSA relies on a very 
   sophisticated FFT such as the one developed for MPIR, (but not used by MPIR yet), written by 
   <NAME>.

fmpz_poly_mullow_SS_n (mullow_SS_n.c) - missing
   Computes the low n coefficients of an n x n multiplication. Relies on an FFT capable of 
   outputting only the low coefficients. Assumes the input polynomials (zero padded if
   necessary) are of the given length.

fmpz_poly_mulhigh_SS_n (mulhigh_SS_n.c) - missing
   Computes the high n coefficients of an n x n multiplication. Relies on an FFT capable of 
   outputting only the low coefficients. Assumes the input polynomials (zero padded if
   necessary) are of the given length.

fmpz_poly_mulmid_SS_n (mulmid_SS_n.c) - missing
   Use the FFT wraparound trick to obtain the middle product directly with the FFT.

fmpz_poly_mulmid_karatsuba (mulmid_karatsuba.c) - missing
   Implement a toom42 middle product for polynomials. This should be a transposition of the
   karatsuba algorithm as per Tellegen's principle.

fmpz_poly_mullow_KS_n (mullow_KS_n.c) - missing
   Computes the low n coefficients of an n x n multiplication. Relies on an FFT capable of 
   outputting only the low coefficients. Assumes the input polynomials (zero padded if
   necessary) are of the given length.

fmpz_poly_mulhigh_KS_n (mulhigh_KS_n.c) - missing
   Computes the high n coefficients of an n x n multiplication. Relies on an FFT capable of 
   outputting only the low coefficients. Assumes the input polynomials (zero padded if
   necessary) are of the given length.

fmpz_poly_mulmid_KS_n (mulmid_KS_n.c) - missing
   Use the FFT wraparound trick to obtain the middle product using Kronecker Segmentation.

fmpz_poly_mul_KS2 (mul_KS2.c) - missing
   Implement David Harvey's KS2 algorithm when coefficients have small coefficients.

fmpz_poly_mul_KS4 (mul_KS4.c) - missing
   Implement David Harvey's KS4 algorithm when coefficients have small coefficients.

fmpz_poly_mul (mul.c) 
   currently only uses classical, karatsuba and KS multiplication. When Schoenhage-Strassen
   algorithm (SSA) is added, it should be used. Also need cutoffs to be tuned per architecture.
   
fmpz_poly_mullow_n (mullow_n.c) 
   Computes the low n coefficients of an n x n multiplication. Use tuned cutoffs to select
   the other implemented algorithms for this. Also use other algorithms for this when they
   become available.

fmpz_poly_mulhigh_n (mulhigh_n.c)
   Computes the high n coefficients of an n x n multiplication. Use tuned cutoffs to select
   the other implemented algorithms for this. Also use other algorithms for this when they
   become available.


<commit_msg>Added a roadmap.txt file. Signed-off-by: <NAME> <<EMAIL>><commit_after>FLINT 2 Roadmap
===============

This documents sets out a list of functions which have been implemented in flint2 which are
not intended to be optimal implementations, and thus can be significantly improved in future
and also lists functions which have not been added, which would improve performance and
functionality were they added. 

Thus this document serves as a roadmap. Functions listed here are candidates for contributors
to consider working on to improve flint2.

fmpz_poly
---------

fmpz_poly_mul_SS (mul_SS) - missing
   Schoenhage-Strassen algorithm (SSA) for multiplying polynomials. Note SSA relies on a very 
   sophisticated FFT such as the one developed for MPIR, (but not used by MPIR yet), written by 
   <NAME>.

fmpz_poly_mullow_SS_n (mullow_SS_n.c) - missing
   Computes the low n coefficients of an n x n multiplication. Relies on an FFT capable of 
   outputting only the low coefficients. Assumes the input polynomials (zero padded if
   necessary) are of the given length.

fmpz_poly_mulhigh_SS_n (mulhigh_SS_n.c) - missing
   Computes the high n coefficients of an n x n multiplication. Relies on an FFT capable of 
   outputting only the low coefficients. Assumes the input polynomials (zero padded if
   necessary) are of the given length.

fmpz_poly_mulmid_SS_n (mulmid_SS_n.c) - missing
   Use the FFT wraparound trick to obtain the middle product directly with the FFT.

fmpz_poly_mulmid_karatsuba (mulmid_karatsuba.c) - missing
   Implement a toom42 middle product for polynomials. This should be a transposition of the
   karatsuba algorithm as per Tellegen's principle.

fmpz_poly_mullow_KS_n (mullow_KS_n.c) - missing
   Computes the low n coefficients of an n x n multiplication. Relies on an FFT capable of 
   outputting only the low coefficients. Assumes the input polynomials (zero padded if
   necessary) are of the given length.

fmpz_poly_mulhigh_KS_n (mulhigh_KS_n.c) - missing
   Computes the high n coefficients of an n x n multiplication. Relies on an FFT capable of 
   outputting only the low coefficients. Assumes the input polynomials (zero padded if
   necessary) are of the given length.

fmpz_poly_mulmid_KS_n (mulmid_KS_n.c) - missing
   Use the FFT wraparound trick to obtain the middle product using Kronecker Segmentation.

fmpz_poly_mul_KS2 (mul_KS2.c) - missing
   Implement David Harvey's KS2 algorithm when coefficients have small coefficients.

fmpz_poly_mul_KS4 (mul_KS4.c) - missing
   Implement David Harvey's KS4 algorithm when coefficients have small coefficients.

fmpz_poly_mul (mul.c) 
   Currently only uses classical, karatsuba and KS multiplication. When Schoenhage-Strassen
   algorithm (SSA) is added, it should be used. Also need cutoffs to be tuned per architecture.
   
fmpz_poly_mullow_n (mullow_n.c) 
   Computes the low n coefficients of an n x n multiplication. Use tuned cutoffs to select
   the other implemented algorithms for this. Also use other algorithms for this when they
   become available.

fmpz_poly_mulhigh_n (mulhigh_n.c)
   Computes the high n coefficients of an n x n multiplication. Use tuned cutoffs to select
   the other implemented algorithms for this. Also use other algorithms for this when they
   become available.


nmod_poly
---------

nmod_poly_mul_classical (mul_classical.c)
   Currently two cases are distinguished: a) where the entire multiplication can be done with
   everything accumulating in a single limb and a single final reduction, b) where reduction
   is performed every operation. In case (b) the addmul code distinguishes the cases where 
   the addmul will fit in a single limb and where it will not. At the very least mul_classical
   should accumulate into 2 or 3 limbs where necessary and do a final reduction at the end.
   Probably it makes sense to accumulate into 2 limbs and always keep the top limb reduced mod
   n, which is less expensive. 
{'fraction_non_alphanumeric': 0.04185724185724186, 'fraction_numerical': 0.003465003465003465, 'mean_word_length': 4.114103472714387, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3651553', 'n_tokens_mistral': 2117, 'n_tokens_neox': 2021, 'n_words': 980}