12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182 |
- #!/usr/bin/ruby
- # Perform Gauss elimination on a bit-matrix, where rows are integers.
- # Code inspired from:
- # https://github.com/martani/Quadratic-Sieve/blob/master/matrix.c
- func display_bitMatrix(A, n) {
- A.each { |r|
- var d = r.digits(2)
- d += (n-d.len + 1 -> of(0))
- say d.join(' ')
- }
- say ''
- }
- func gauss_elimination(A, n) {
- var m = A.end
- var I = (m+1).of {|i| 1 << i }
- var nrow = -1
- for col in (0 .. min(m, n)) {
- var npivot = -1
- for row in (nrow+1 .. m) {
- if (A[row].bit(col)) {
- npivot = row
- nrow++
- break
- }
- }
- next if (npivot < 0)
- if (npivot != nrow) {
- A.swap(npivot, nrow)
- I.swap(npivot, nrow)
- }
- for row in (nrow+1 .. m) {
- if (A[row].bit(col)) {
- A[row] ^= A[nrow]
- I[row] ^= I[nrow]
- }
- }
- }
- return I
- }
- var n = 5 # number of columns-1
- var A = [
- 0b001100, # 12
- 0b001011, # 11
- 0b010111, # 23
- 0b010011, # 19
- 0b010001, # 17
- 0b001111, # 15
- ]
- say "=> Matrix A before Gaussian elimination"
- display_bitMatrix(A, n)
- var I = gauss_elimination(A, n)
- say "=> Matrix A after Gaussian elimination"
- display_bitMatrix(A, n)
- say "=> Matrix I"
- display_bitMatrix(I, n)
- say "A = #{A}"
- say "I = #{I}"
- assert_eq(I, [2, 18, 6, 10, 7, 46])
- assert_eq(A, [11, 26, 28, 24, 16, 0])
|