Everybody knows the Lenstra-Lenstra-Lovász lattice basis reduction algorithm (LLL), which has proved invaluable in public-key cryptanalysis and in many other fields. Given an integer $d$-dimensional lattice basis which vectors have norms smaller than $B$, LLL outputs a so-called LLL-reduced basis in time $O(d^6 log^3 B)$, using arithmetic operations on integers of bit-length $O(d$ log $B)$. This worst-case complexity is problematic for lattices arising in cryptanalysis where $d$ or/and log $B$ are often large. As a result, the original LLL is almost never used in practice. Instead, one applies floating-point variants of LLL, where the long-integer arithmetic required by Gram-Schmidt orthogonalisation (central in LLL) is replaced by floating-point arithmetic. Unfortunately, this is known to be unstable in the worst-case: the usual floating-point LLL is not even guaranteed to terminate, and the output basis may not be LLL-reduced at all. In this article, we introduce the LLL$^2$ algorithm, a new and natural floating-point variant of LLL which provably outputs LLL-reduced bases in polynomial time $O(d^5(d$ + log $B$) log $B)$. This is the first LLL algorithm which running time provably grows only quadratically with respect to log $B$ without fast integer arithmetic, like the famous Gaussian and Euclidean algorithms. The growth is cubic for all other LLL algorithms known.