8000 feat: add determinant algorithm · TheAlgorithms/TypeScript@ef5b88b · GitHub
[go: up one dir, main page]
Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit ef5b88b

Browse files
cosmicproccosmicproc
committed
feat: add determinant algorithm
1 parent 19b4ced commit ef5b88b

File tree

2 files changed

+143
-0
lines changed

2 files changed

+143
-0
lines changed

‎maths/determinant.ts‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
/**
2+
* @function det
3+
* @description
4+
* Computes the determinant of the given matrix using elimination.
5+
* - Rounding errors may occur for some matrices.
6+
* - Only handles 6 decimal places. Rounds thereafter.
7+
* @Complexity_Analysis
8+
* Time complexity: O(n^3)
9+
* Space Complexity: O(n^2)
10+
* @param {number[][]} m - A square matrix (2D array)
11+
* @return {number} - The determinant
12+
* @example det([[1,1],[1,1]]) = 0
13+
*/
14+
15+
export function det(m: number[][]): number {
16+
if (m.some((r) => r.length != m.length)) {
17+
throw new Error('only square matrices can have determinants')
18+
}
19+
20+
const decPlaces = 6
21+
22+
// track the number of applied interchange operations
23+
let appliedICs = 0
24+
for (let i = 0; i < m[0].length; i++) {
25+
// partial pivotting
26+
let idealPivot = -1
27+
let maxValue = 0
28+
for (let j = i; j < m.length; j++) {
29+
if (Math.abs(m[j][i]) > maxValue) {
30+
maxValue = Math.abs(m[j][i])
31+
idealPivot = j
32+
}
33+
}
34+
if (idealPivot === -1) {
35+
return 0
36+
}
37+
if (idealPivot != i) {
38+
appliedICs++
39+
;[m[i], m[idealPivot]] = [m[idealPivot], m[i]]
40+
}
41+
// eliminate entries under the pivot
42+
for (let j = i + 1; j < m.length; j++) {
43+
if (Math.abs(m[j][i]) > 1 / 10 ** decPlaces) {
44+
m[j] = m[j].map((e, k) => e + (-m[j][i] / m[i][i]) * m[i][k])
45+
}
46+
}
47+
}
48+
let diagProduct = 1
49+
for (let i = 0; i < m.length; i++) {
50+
diagProduct *= m[i][i]
51+
}
52+
let result = diagProduct * (-1) ** appliedICs
53+
return parseFloat(result.toFixed(decPlaces))
54+
}

‎maths/test/determinant.test.ts‎

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
import { det } from '../determinant'
2+
3+
describe('determinant', () => {
4+
test.each([
5+
[
6+
[
7+
[1, 2],
8+
[3, 4, 5]
9+
]
10+
],
11+
[
12+
[
13+
[1, 2, 3],
14+
[4, 5, 6]
15+
]
16+
],
17+
[
18+
[
19+
[1, 2],
20+
[3, 4],
21+
[5, 6]
22+
]
23+
]
24+
])('should throw an error for non square matrix %p', (matrix) => {
25+
expect(() => det(matrix)).toThrow(
26+
'only square matrices can have determinants'
27+
)
28+
})
29+
30+
test.each([
31+
[
32+
[
33+
[1, 2],
34+
[3, 4]
35+
],
36+
-2
37+
],
38+
[
39+
[
40+
[1, 1],
41+
[1, 1]
42+
],
43+
0
44+
],
45+
[
46+
[
47+
[1, 2],
48+
[0, 0]
49+
],
50+
0
51+
],
52+
[
53+
[
54+
[8, 1, 5],
55+
[9, 3, 7],
56+
[1, 4, 4]
57+
],
58+
8
59+
],
60+
[
61+
[
62+
[15, 85, 32],
63+
[76, 83, 23],
64+
[28, 56, 92]
65+
],
66+
-382536
67+
],
68+
[
69+
[
70+
[2, -1, 0, 3],
71+
[4, 0, 1, 2],
72+
[3, 2, -1, 1],
73+
[1, 3, 2, -2]
74+
],
75+
-42
76+
],
77+
[
78+
[
79+
[0.75483643, 0.68517541, 0.53548329, 0.5931435],
80+
[0.37031247, 0.80103707, 0.82563949, 0.91266224],
81+
[0.39293451, 0.27228353, 0.54093836, 0.51963319],
82+
[0.60997323, 0.40161682, 0.58330774, 0.17392144]
83+
],
84+
-0.051073
85+
]
86+
])('determinant of %p should be %d', (matrix, expected) => {
87+
expect(det(matrix)).toBe(expected)
88+
})
89+
})

0 commit comments

Comments
 (0)
0