## Feature #2772

closed### Matrix: Calculating determinant using Bareiss algorithm [patch]

**Description**

=begin

Yu Ichino suggested to use a different algorithm to calculate the determinant of a matrix in [ruby-core:28166].

I second his proposal. To reduce the risk of this proposal to go without a response, I am creating this request.

Bareiss' algorithm has two big advantages:

- can calculate the determinant of integer matrices using only integer intermediate results.
- has minimal requirements on the number of bits required for intermediate results, thus reducing the floating point rounding errors.

Performance-wise, it has the same complexity O(n^3) as the current traditional method.

For Integer matrices, there is a big gain (say about 15 times faster) because the traditional version must use #quo and rationals, while the Bareiss algorithm can use #/ and keep the intermediate results as a Fixnum. The same goes for Bignum, of course (where the gain is even bigger).

For float version, the Bareiss algorithm is slightly slower (~33%):

```
user system total real
```

Fixnum: det 8.660000 0.010000 8.670000 ( 8.672686)

Fixnum: det_bareiss 0.590000 0.000000 0.590000 ( 0.594747)

Float: det 0.160000 0.000000 0.160000 ( 0.154779)

Float: det_bareiss 0.240000 0.000000 0.240000 ( 0.237806)

I have revised Yu's code, and attached a patch.

I'm also attaching the performance test I used, for anyone interested.

=end

**Files**