像维基百科上所说的那样实现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的值超过维数(或向量数),这是没有道理的。

       

网上收集的解决方案 "像维基百科上所说的那样实现LLLalgorithm,但却陷入严重的问题"

维基百科中的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 ,并且适当地改变其余的代码,这只是意味着在主循环的终止条件中进行调整。