flintlib / flint

FLINT (Fast Library for Number Theory)
http://www.flintlib.org
GNU Lesser General Public License v3.0
423 stars 241 forks source link

128-bit arithmetic in LLL #1716

Open fredrik-johansson opened 8 months ago

fredrik-johansson commented 8 months ago

The fmpz_poly_factor benchmark spends something like 15% of the time in fmpz_lll_is_reduced_mpfr_with_removal which does MPFR arithmetic with a precision of 120 bits. For some polynomials this accounts for half the running time. An easy speedup here should be to use a 128-bit floating-point type optimised for speed.

Actually, it's possible that we mostly enter this code due to running out of exponent range for the d variant rather than running out of precision, in which case a 64-bit float type with 64-bit exponent would be enough.

fredrik-johansson commented 8 months ago

Also worth noting that the S9 test takes forever because it falls back on the mpf LLL, but the mpf precision is only 53 bits(!).