-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathEigenLLL.cpp
More file actions
112 lines (97 loc) · 11.3 KB
/
EigenLLL.cpp
File metadata and controls
112 lines (97 loc) · 11.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <eigen3/Eigen/Dense>
void GSO(const Eigen::MatrixXi b, Eigen::VectorXd& B, Eigen::MatrixXd& mu, const int n, const int m);
void SizeReduce(Eigen::MatrixXi& b, Eigen::MatrixXd& mu, const int i, const int j, const int m);
void LLLReduce(Eigen::MatrixXi& b, const long double d, const int n, const int m);
int main(){
Eigen::MatrixXi b(40, 40);
b << -1 , 3 , 0 , -1 , -1 , 0 , -6 , 0 , -28 , -2 , 0 , -1 , 0 , -1 , 0 , -15 , 0 , -6 , 0 , -1 , -1 , -1 , -1 , -28 , -99 , -2 , 2 , -1 , -1 , -1 , 1 , 11 , 1 , -3 , 0 , 0 , 2 , 1 , -2 , 0
, 1 , -1 , 13 , 1 , -1 , -1 , 3 , -10 , 1 , 1 , -3 , 1 , 1 , 2 , 2 , -1 , -1 , -1 , 1 , 0 , 2 , -2 , -1 , 1 , 1 , 3 , 1 , -1 , 2 , -2 , -9 , -3 , 1 , -3 , 0 , -2 , -1 , -4 , -1 , 1
, -3 , 0 , -3 , 1 , 1 , -3 , -3 , 6 , 2 , -1 , 1 , 0 , 0 , -4 , -1 , -1 , -4 , 1 , 1 , 3 , 0 , 2 , -1 , -1 , -9 , -1 , -1 , -1 , 1 , 0 , 0 , 1 , 0 , -1 , 1 , -1 , 0 , 2 , 13 , 0
, -1 , -1 , 1 , 1 , 0 , 0 , -2 , 0 , -9 , 2 , 1 , -1 , -1 , 1 , 2 , -2 , 1 , 1 , -1 , -20 , 0 , 1 , 0 , -1 , -1 , -1 , -1 , 296 , -3 , -1 , 1 , 2 , -11 , 2 , 8 , 14 , -1 , 0 , -3 , 1
, -2 , 0 , -1 , 1 , -1 , -1 , 1 , -1 , 1 , 6 , -1 , 0 , -1 , 1 , -11 , 1 , 1 , -1 , 1 , 1 , -3 , -1 , -1 , -1 , 4 , 5 , -4 , -1 , 3 , 0 , 1 , -5 , -1 , -2 , 1 , -1 , 1 , -3 , 0 , -5
, 0 , 0 , 6 , 2 , -1 , 1 , 1 , 0 , 1 , 12 , 1 , -6 , 3 , 1 , 0 , -1 , 0 , 0 , 0 , 2 , 0 , 3 , -1 , 0 , 0 , -1 , 1 , 1 , 0 , 12 , -1 , 0 , 119 , -2 , -11 , 29 , 0 , 1 , 2 , -2
, 0 , 1 , 14 , -2 , 1 , 2 , 1 , -3 , -1 , 0 , 1 , 1 , -3 , 0 , 2 , -2 , -1 , -1 , -2 , 0 , 1 , 15 , 14 , -4 , 1 , 0 , -1 , 1 , 1 , 1 , 4 , -1 , 17 , 1 , -2 , 1 , 3 , 0 , 3 , -1
, 1 , -3 , -1 , 0 , -1 , 1 , -3 , 13 , -1 , -1 , 3 , -2 , 1 , 1 , 1 , 1 , -3 , 2 , -6 , -13 , 1 , 0 , 1 , -2 , -1 , 2 , 0 , -1 , -3 , 0 , -1 , 11 , -3 , 11 , -4 , 1 , 1 , -2 , -4 , -3
, 0 , -7 , -1 , 0 , 1 , 0 , -37 , 0 , 0 , 1 , -16 , 0 , 1 , -2 , 0 , -7 , 5 , 2 , 2 , -1 , 1 , 2 , -12 , 0 , 0 , 4 , -1 , -1 , 1 , 17 , 13 , 0 , 2 , 2 , -1 , 0 , 0 , -1 , 5 , -8
, 1 , 1 , -1 , 1 , 3 , 0 , -1 , 2 , -1 , 2 , -1 , -7 , 2 , -1 , 1 , -4 , 3 , 1 , 2 , -1 , 0 , 4 , 1 , -11 , 6 , -144 , 1 , -3 , 0 , -35 , 2 , 3 , 1 , -1 , 1 , 4 , 12 , 3 , 0 , 2
, -1 , -1 , 1 , -1 , 9 , 0 , 1 , 1 , 0 , 2 , 6 , -2 , -2 , 1 , -1 , 142 , 0 , 1 , 0 , 3 , 2 , -1 , 1 , 0 , -1 , -2 , -12 , -13 , -1 , 3 , 5 , 2 , -4 , -1 , -2 , -2 , -3 , 0 , 0 , 1
, 0 , 17 , 0 , 2 , -16 , -3 , 0 , 0 , 1 , 26 , 1 , -3 , 3 , -2 , -4 , 0 , -2 , 0 , 1 , 1 , -1 , -6 , 1 , -5 , 1 , 1 , 1 , 0 , -1 , -3 , 18 , 4 , 2 , -3 , -107 , -5 , -6 , 0 , -3 , 1
, 2 , -2 , 3 , 1 , 3 , -7 , -1 , 1 , 1 , 0 , 7 , -5 , 0 , -1 , 0 , 68 , 2 , 1 , -1 , 4 , 0 , 7 , 0 , 3 , 11 , 1 , -1 , -2 , 0 , 0 , 26 , -1 , 5 , -4 , -1 , 4 , -1 , -3 , 1 , -1
, 1 , 1 , -5 , 1 , -1 , -1 , 0 , 1 , -40 , 1 , -1 , -1 , 1 , 1 , 2 , 1 , 0 , -30 , 1 , -1 , 0 , 2 , 1 , 0 , -2 , -1 , 0 , -6 , 1 , 2 , 1 , 2 , 1 , -1 , 0 , 0 , 1 , -2 , 1 , 3
, -7 , 5 , -2 , 2 , 3 , 0 , -1 , 1 , 1 , -218 , 2 , -1 , -1 , 2 , -2 , -1 , 0 , -1 , 0 , 5 , 1 , -1 , -1 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , -3 , 3 , -1 , 1 , -1 , 0 , 1 , -2 , 1
, 0 , 0 , -3 , -4 , 1 , -1 , -12 , -3 , 9 , 2 , 0 , -1 , -15 , -1 , -1 , 1 , -1 , -3 , 0 , -1 , -1 , 0 , 1 , 0 , 1 , 0 , -9 , 0 , 0 , 6 , 0 , 1 , -1 , -1 , -10 , -1 , 23 , 8 , 0 , 5
, 2 , 1 , -4 , 0 , 0 , 1 , 1 , -1 , 2 , 6 , 1 , 2 , 4 , 0 , 2 , -1 , 22 , -1 , 0 , 1 , -3 , 2 , 1 , 0 , 1 , 0 , -3 , -2 , 0 , 4 , 0 , -2 , 1 , 3 , 1 , 1 , 0 , 1 , 1 , 0
, -12 , -1 , 0 , 1 , 0 , 1 , 1 , -1 , 1 , -27 , -1 , 2 , 1 , 1 , 1 , 5 , -1 , 2 , 1 , 0 , 2 , -8 , 0 , 0 , 11 , 95 , 2 , 1 , -1 , 1 , -1 , -2 , -3 , 0 , -2 , -2 , 2 , -1 , -3 , -2
, 9 , -1 , -1 , 1 , -1 , 4 , -1 , -1 , 1 , 0 , -3 , 1 , 1 , 6 , 1 , -1 , -1 , 1 , 1 , 0 , 0 , 0 , 0 , -1 , 3 , 2 , 0 , -1 , -1 , -1 , 3 , 1 , 0 , -1 , 0 , -1 , -1 , -3 , 1 , -1
, -5 , -4 , -7 , -2 , 1 , -1 , 3 , 2 , -3 , -1 , 1 , 0 , 14 , 1 , 0 , 0 , 0 , 1 , -1 , 3 , -1 , -1 , 2 , -1 , -4 , 1 , -4 , 1 , 0 , 0 , 142 , -1 , 2 , -1 , 0 , -10 , 3 , -4 , 1 , -2
, 0 , 1 , 0 , 1 , -2 , -1 , 0 , 0 , 1 , 0 , -1 , 1 , 2 , 0 , 0 , 3 , -1 , 1 , -1 , 0 , -1 , 0 , 156 , 5 , 0 , -3 , -3 , 7 , 1 , 184 , 4 , 1 , -33 , 1 , -5 , 0 , 8 , 0 , 1 , 0
, -1 , -1 , 1 , -1 , 2 , 0 , 0 , 1 , 1 , 5 , -47 , 1 , 1 , -3 , -15 , 0 , 3 , 1 , 2 , 3 , 1 , -2 , -9 , -15 , 49 , -3 , 0 , -16 , -1 , 0 , -1 , 1 , 0 , -1 , 3 , 1 , -1 , 6 , -29 , -1
, 0 , -7 , -1 , -1 , -3 , 2 , -2 , 20 , 0 , -1 , 170 , 30 , 0 , -1 , 1 , 1 , -1 , 3 , 1 , 2 , -1 , 2 , 4 , 1 , -2 , 3 , -1 , 0 , 1 , 0 , -7 , 1 , -1 , 323 , -1 , -1 , 0 , 0 , 8 , -22
, -1 , -18 , 1 , -2 , -4 , -1 , 1 , 0 , 1 , -2 , 1 , -1 , 7 , -1 , 1 , -1 , 3 , -1 , -3 , 0 , 3 , 2 , 3 , -1 , -1 , 1 , 0 , -1 , 1 , 3 , -1 , 0 , -12 , -1 , 4 , 0 , -3 , 1 , -1 , 0
, 1 , 1 , -17 , 0 , -1 , 3 , 4 , -1 , -4 , -1 , 2 , 1 , -2 , 2 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , 2 , 3 , 5 , 1 , 2 , -1 , 2 , 1 , -4 , 0 , 0 , 4 , 1 , 24 , 0 , -1 , 2
, 0 , -2 , 8 , 2 , -1 , 4 , 1 , -1 , 10 , 1 , -1 , 2 , 3 , 0 , 7 , -1 , 8 , -1 , -6 , 5 , -1 , 1 , -123 , -1 , 1 , 3 , -1 , -2 , 0 , 1 , 0 , 0 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , -1
, 3 , 1 , 7 , -1 , -3 , -1 , 3 , -1 , 3 , -1 , -65154 , -1 , 1 , 2 , -2 , 3 , 1 , -23 , 10 , -2 , 0 , 0 , 0 , 3 , -1 , 2 , 0 , -1 , -1 , 8 , -5 , 1 , 0 , -2 , 0 , 0 , 0 , 1 , -1 , 3
, 0 , -1 , -4 , 2 , 4 , 19 , 3 , 0 , -1 , 1 , -2 , -2 , 2 , -1 , 0 , -1 , 0 , -1 , -1 , 0 , 1 , -1 , -1 , -2 , 0 , 8 , 0 , 0 , 0 , -8 , -1 , -1 , 1 , 2 , 1 , 3 , -1 , 9 , -2 , 1
, 1 , -1 , 1 , 1 , 25 , 2 , -2 , 0 , 4 , 1 , 1 , 0 , -1 , 0 , 1 , -6 , 0 , 1 , -1 , -1 , -3 , 0 , 1 , -2 , 59 , 0 , 1 , -2 , 1 , 1 , -1 , -1 , 0 , 2 , 1 , -1 , 1 , 0 , 1 , -3
, 1 , 4 , 1 , 4 , 1 , -2 , -58 , 0 , -9 , -1 , -1 , -1 , -1 , 0 , -20 , 0 , -1 , 0 , -2 , 0 , 1 , 4 , 2 , 5 , 19 , -1 , -3 , 1 , 140 , 1 , -2 , -1 , 0 , -1 , 3 , 2 , -1 , 0 , -2 , -1
, 18 , -1 , 1 , -3 , -1 , -1 , 0 , 2 , 14 , -2 , -1 , 1 , 0 , -1 , 2 , -1 , -1 , 0 , -4 , 1 , 1 , -7 , -2 , -1 , -4 , 2 , 3 , -1 , -2 , -1 , -6 , -1 , -1 , 0 , -39 , 3 , 0 , 0 , -2 , 40
, -5 , 1 , 0 , -1 , 2 , 0 , 3 , 0 , 1 , 6 , 1 , 0 , 2 , 0 , -3 , -4 , -1270 , 1 , -1 , 1 , -2 , 2 , -2 , -1 , -4 , 1 , -1 , -2 , 1 , -2 , 2 , 0 , -3 , 2 , 0 , 1 , -1 , 0 , -1 , 1
, -49 , 0 , 0 , -1 , 1 , 1 , -3 , -9 , 0 , 0 , 0 , -2 , 1 , 1 , -47 , 0 , 0 , 0 , 4 , 6 , -2 , -2 , 0 , 2 , 1 , 2 , 1 , -1 , 1 , 4 , 7 , 0 , 1 , -1 , 0 , -1 , -1 , 1 , 0 , -1
, -2 , -1 , -2 , 1 , 17 , 1 , 10 , 6 , 0 , -1 , -1 , -2 , -3 , 1 , 1 , 1 , 5 , 18 , 1 , 0 , 49 , 7 , 0 , 2 , 0 , 0 , -1 , 0 , 0 , 0 , 2 , -2 , 1 , 0 , 0 , -1 , 0 , 0 , -2 , 3
, -1 , -1 , 166 , 0 , -46 , 0 , -2 , 0 , 1 , 1 , 15 , -2 , 1 , 12 , 1 , 4 , 0 , -2 , 1 , -1 , 0 , -1 , 0 , 0 , -25 , -6 , 0 , -1 , -4 , 0 , 1 , 2 , 78 , -15 , 2 , 0 , 0 , -1 , 17 , 17
, -13 , 4 , -16 , -1 , 0 , 1 , 0 , 1222 , 1 , -1 , 1 , 0 , 0 , 1 , 1 , 1 , 0 , 0 , -1 , 1 , 0 , 0 , 0 , 0 , -1 , 0 , -5 , 3 , 1 , 1 , -1 , -1 , -1 , -1 , 3 , 0 , 0 , -4 , 2 , -1
, 1 , 2 , -2 , 0 , 0 , -4 , 1 , -1 , 9 , -1 , -1 , -13 , 24 , -1 , -1 , -8 , 1 , -1 , -29 , 0 , 1 , 0 , -1 , 1 , 1 , 1 , 1 , 4 , 9 , -1 , -1 , 0 , -18 , -1 , -1 , 1 , 6 , -1 , -4 , 0
, 6 , -13 , 0 , 0 , 0 , 15 , 0 , -3 , 0 , -2 , 0 , -2 , 1 , -1 , -2 , -1 , 0 , 1 , -2 , 0 , 1 , -1 , 1 , -1 , -9 , 1 , 6 , -5 , -9 , 0 , 1 , -2 , -1 , -2 , 9 , 1 , 1 , 3 , 0 , 1
, 1 , 3 , -2 , -1 , -3 , 1 , -2 , -1 , -1 , -2 , 460 , 1 , 2 , -8 , 0 , 2 , 0 , 4 , 0 , 1 , -1 , 0 , 0 , -1 , -1 , 4 , 23 , -1 , -1 , -1 , -1 , -4 , 2 , 15 , -2 , 3 , 0 , -1 , 2 , -1
, 0 , 0 , -1 , 1 , 69 , 4 , 0 , -2 , 0 , 8 , 1 , 4 , 1 , 2 , -2 , 0 , -2 , -1 , 8 , -4 , 1 , -11 , 0 , -1 , -1 , 0 , -1 , 0 , 1 , -1 , -11 , 0 , 505 , 3 , 8 , -1 , -1 , 1 , -3 , 1;
LLLReduce(b, 0.99, 40, 40);
std::cout << b << std::endl;
printf("norm = %f\n", sqrt(b.row(0).dot(b.row(0))));
return 0;
}
/* Gram-Schmidtの直交化 */
void GSO(const Eigen::MatrixXi b, Eigen::VectorXd& B, Eigen::MatrixXd& mu, const int n, const int m){
int j;
Eigen::MatrixXd GSOb(n, m);
for(int i = 0; i < n; ++i){
mu.coeffRef(i, i) = 1.0;
GSOb.row(i) = b.row(i).cast<double>();
for(j = 0; j < i; ++j){
mu.coeffRef(i, j) = b.row(i).cast<double>().dot(GSOb.row(j)) / GSOb.row(j).dot(GSOb.row(j));
GSOb.row(i) -= mu.coeff(i, j) * GSOb.row(j);
}
B.coeffRef(i) = GSOb.row(i).dot(GSOb.row(i));
}
}
/* サイズ基底簡約 */
void SizeReduce(Eigen::MatrixXi& b, Eigen::MatrixXd& mu, const int i, const int j, const int m){
if(mu.coeff(i, j) > 0.5 || mu.coeff(i, j) < -0.5){
const int q = round(mu.coeff(i, j));
b.row(i) -= q * b.row(j);
mu.row(i).head(j + 1) -= (double)q * mu.row(j).head(j + 1);
}
}
/* LLL簡約 */
void LLLReduce(Eigen::MatrixXi& b, const long double d, const int n, const int m){
double nu, BB, C, t;
Eigen::VectorXd B(n), logB(n);
Eigen::MatrixXd mu(n, n);
GSO(b, B, mu, n, m);
for(int k = 1, j, i, k1; k < n;){
k1 = k - 1;
for(j = k1; j > -1; --j) SizeReduce(b, mu, k, j, m);
if(k > 0 && B.coeff(k) < (d - mu.coeff(k, k1) * mu.coeff(k, k1)) * B.coeff(k1)){
b.row(k).swap(b.row(k1));
nu = mu.coeff(k, k1); BB = B.coeff(k) + nu * nu * B.coeff(k1); C = 1.0 / BB;
mu.coeffRef(k, k1) = nu * B.coeff(k1) * C;
B.coeffRef(k) *= B.coeff(k1) * C; B.coeffRef(k1) = BB;
mu.row(k1).head(k - 1).swap(mu.row(k).head(k - 1));
for(i = k + 1; i < n; ++i){
t = mu.coeff(i, k); mu.coeffRef(i, k) = mu.coeff(i, k1) - nu * t;
mu.coeffRef(i, k1) = t + mu.coeff(k, k1) * mu.coeff(i, k);
}
k = k1;
}else ++k;
}
}