module Math.Lattices.CloseVector (
closeVector
) where
import Prelude hiding ((*>))
import Data.Array
import Data.Ratio
import Math.Algebra.LinearAlgebra hiding ((!))
import Math.Lattices.Internal
import Math.Lattices.LLL
import Math.LinearAlgebra.GramSchmidt
closeVector :: [[Rational]] -> [Ratio Integer] -> [Rational]
closeVector basis x = foldl1 (<+>) $ babaiNP (reverse $ [0..d]) basis' b' x
where
d = length basis - 1
b' = listArray (0, d) $ gramSchmidtBasis basis
basis' = listArray (0, d) basis
projectTo v b = (v <.> b) / (norm2 b)
vsum zero = foldl (<+>) zero
babaiNP [] _ _ _ = []
babaiNP (i:is) b b' w = y_i : recurse
where
l_i = projectTo w $ b' ! i
delta = toRational $ rnd $ l_i
y_i = delta *> b ! i
w_i1 = w <-> (l_i - delta) *> (b' ! i) <-> y_i
recurse = babaiNP is b b' w_i1