Howellizing matrix

Question

I am trying to implement the Howellize matrix algorithm as described on page 5 of this article (google docs link ) (pdf link) .

Most of this is pretty obvious to me, I think, but I'm not sure about line 16, does >> mean the right shift? If so, how does it work? Will this really mean that the bits are chopped off? As far as I know, at this moment there is no guarantee that the number that it shifts is shifted by the amount that stores the information.
And if this does not mean a shift to the right, what does it mean?

If someone can save time, I would also like to have a test case (I don't believe myself to come up with one, I don't understand it well enough).

I implemented it like this, right? (I don't have a test case, so how can I find out?)

 int j = 0; for (int i = 0; i < 2 * k + 1; i++) { var R = (from row in rows where leading_index(row) == i orderby rank(row[i]) ascending select row).ToList(); if (R.Count > 0) { uint[] r = R[0]; int p = rank(r[i]); // rank counts the trailing zeroes uint u = r[i] >> p; invert(r, u); // multiplies each element of r by the // multiplicative inverse of u for (int s = 1; s < R.Count; s++) { int t = rank(R[s][i]); uint v = R[s][i] >> t; if (subtract(R[s], r, v << (t - p)) == 0) // subtracts (v<<(tp)) * r from R[s], // removes if all elements are zero rows.Remove(R[s]); } swap(rows, rows.IndexOf(r), j); for (int h = 0; h < j - 1; h++) { uint d = rows[h][i] >> p; subtract(rows[h], r, d); } if (r[i] != 1) // shifted returns r left-shifted by 32-p rows.Add(shifted(r, 32 - p)); j++; } } 

Answer 1

In a test case, this may help you (page number 2). Also try this .

I think you are right in the right shift. To get a Howell form, they want values ​​other than the leading value in the column to be less than the leading value. Correct bias seems fruitful for this.

line 16 says:

  Pick d so that 0 <= G(h,i) - d * ri < ri 

Consider

  G(h,i) - d * ri = 0 G(h,i) = d * ri G(h,i) = d * (2 ^ p) ... as the comment on line 8 says, ri = 2^p. So d = G(h,i) / (2 ^ p) 

The right shift G (h, i) in p-positions is the fastest way to calculate the value of d.