search

flintlib / flint

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

Optimise double operations in LLL #701

Open fredrik-johansson opened 4 years ago

fredrik-johansson commented 4 years ago

LLL will (at least in some cases) spend a significant portion of its time in ldexp() calls appearing in check_babai, _fmpz_vec_get_d_vec_2exp and maybe elsewhere. We could speed this up by precomputing a big table of power-of-two doubles and multiplying. (In check_babai, we could just pull the ldexp calls out of the loops, but this would not work in _fmpz_vec_get_d_vec_2exp.)

This just needs to be done carefully to make sure we don't violate any assumptions about the range of the doubles that are used in LLL.

fredrik-johansson commented 4 years ago

Also d_vec_dot and _d_vec_norm could be optimised by unrolling to enable more parallel multiplications. However, before implementing such a change we should verify that it doesn't slow down for short vectors.