Hi all, I have written some mpn and mpz level functions for division with precomputed inverse.
The functions are faster for divisors above about 100 limbs. With a lot of work on mpir's mullow and mulhigh functions, it might be possible to lower this threshold considerably. Here is the function for computing an mpn level precomputed inverse: https://github.com/wbhart/flint2/blob/trunk/mpn_extras/preinvn.c Here are some various mpn level functions which use such a precomputed inverse: https://github.com/wbhart/flint2/blob/trunk/mpn_extras/mod_preinvn.c https://github.com/wbhart/flint2/blob/trunk/mpn_extras/divrem_preinvn.c https://github.com/wbhart/flint2/blob/trunk/mpn_extras/mulmod_preinvn.c The function for computing a precomputed inverse at the mpz level is basically the final case in this function: https://github.com/wbhart/flint2/blob/trunk/fmpz/preinvn_init.c The top two functions in the following file are mpz level functions which use such a precomputed inverse: https://github.com/wbhart/flint2/blob/trunk/fmpz/fdiv_qr_preinvn.c They are derived from the equivalent GMP function implementations. The speedup maxes out at some few thousands of limbs, where you get about an 80% speedup, assuming you are doing many divisions for each precomputed inverse. I didn't find a maximum size for which it is faster, only a minimum size (100 limb divisors). Bill. -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to mpir-devel+unsubscr...@googlegroups.com. To post to this group, send email to mpir-devel@googlegroups.com. Visit this group at http://groups.google.com/group/mpir-devel. For more options, visit https://groups.google.com/groups/opt_out.
