像维基百科上所说的那样实现LLLalgorithm，但却陷入严重的问题

我不确定我的问题与编程有关，或与LLLalgorithm的概念有关，以及维基百科上提及的内容。

我决定实施LLLalgorithm，因为它已经写在维基百科上 （逐行/逐行）实际学习algorithm，并确保它是真正的工作，但我得到意想不到或无效的结果。

所以，我使用JavaScript（编程语言）和node.js（JavaScript引擎）来实现它， 这是获取完整代码的git存储库 。

长话短说，K的值超出范围，例如当我们只有3个向量（数组大小为3，因此索引的最大值将是2）时，K的值将超出范围，但是k变为3并且是无意义的。

我的代码是维基百科上提到的algorithm的一步一步（逐行）实现，我所做的只是实现它。 所以我不是什么问题。

// ** important // {b} set of vectors are denoted by this.matrix_before // {b*} set of vectors are denoted by this.matrix_after calculate_LLL() { this.matrix_after = new gs(this.matrix_before, false).matrix; // initialize after vectors: perform Gram-Schmidt, but do not normalize var flag = false; // invariant var k = 1; while (k <= this.dimensions && !flag) { for (var j = k - 1; j >= 0; j--) { if (Math.abs(this.mu(k, j)) > 0.5) { var to_subtract = tools.multiply(Math.round(this.mu(k, j)), this.matrix_before[j], this.dimensions); this.matrix_before[k] = tools.subtract(this.matrix_before[k], to_subtract, this.dimensions); this.matrix_after = new gs(this.matrix_before, false).matrix; // update after vectors: perform Gram-Schmidt, but do not normalize } } if (tools.dot_product(this.matrix_after[k], this.matrix_after[k], this.dimensions) >= (this.delta - Math.pow(this.mu(k, k - 1), 2)) * tools.dot_product(this.matrix_after[k - 1], this.matrix_after[k - 1], this.dimensions)) { if (k + 1 >= this.dimensions) { // invariant: there is some issue, something is wrong flag = true; // invariant is broken console.log("something bad happened ! (1)"); } k++; // console.log("if; k, j"); // console.log(k + ", " + j); } else { var temp_matrix = this.matrix_before[k]; this.matrix_before[k] = this.matrix_before[k - 1]; this.matrix_before[k - 1] = temp_matrix; this.matrix_after = new gs(this.matrix_before, false).matrix; // update after vectors: perform Gram-Schmidt, but do not normalize if (k === Math.max(k - 1, 1) || k >= this.dimensions || Math.max(k - 1, 1) >= this.dimensions) { // invariant: there is some issue, something is wrong flag = true; // invariant is broken console.log("something bad happened ! (2)"); } k = Math.max(k - 1, 1); // console.log("else; k, j"); // console.log(k + ", " + j); } console.log(this.matrix_before); console.log("\n"); } // I added this flag variable to prevent getting exceptions and terminate the loop gracefully console.log("final: "); console.log(this.matrix_before); } // calculated mu as been mentioned on Wikipedia // mu(i, j) = <b_i, b*_j> / <b*_j, b*_j> mu(i, j) { var top = tools.dot_product(this.matrix_before[i], this.matrix_after[j], this.dimensions); var bottom = tools.dot_product(this.matrix_after[j], this.matrix_after[j], this.dimensions); return top / bottom; } 

以下是Wikipedia上的algorithm的屏幕截图：

---

更新＃1 ：我在代码中添加了更多的评论来澄清希望有人会帮助的问题。

为了防止你对代码已经可用的实现感到疑惑，你可以input： LatticeReduce[{{0,1},{2,0}}] wolfram alpha来看看这个代码是如何运行的。

更新＃2 ：我更清理了代码，并添加了一个validation函数，使Gram Schmidt代码工作正常，但仍然代码失败，k的值超过维数（或向量数），这是没有道理的。

Answer 1

维基百科中的algorithm描述使用相当奇怪的符号 – vector编号为0..n（而不是0..n-1或1..n），所以vector的总数为n + 1。

你在这里发布的代码将this.dimensions视为在Wikipedia描述中对应于n。 到目前为止没有什么错。

但是，GitHub上的完整源代码文件中的构造函数会设置this.dimensions = matrix[0].length 。 关于这个看起来有两点是错误的 首先是matrix[0].length更像m （空间的维数），而不是n （vector的数量，因为不清楚的原因减去1）。 第二个是，如果它的意思是n，那么你需要减1，因为vector的数量是n + 1，而不是n。

所以如果你想使用this.dimensions来表示n，我想你需要把它初始化为matrix.length-1 。 在你的testing用例中使用matrix[0].length-1 ，使用matrix[0].length-1将会起作用，但是当你input一个非方形matrix时，我认为这个代码会中断。 名称dimensions也有点误导。 也许只是n匹配维基百科的描述？

或者你可以把它nVectors ，让它等于matrix.length ，并且适当地改变其余的代码，这只是意味着在主循环的终止条件中进行调整。