Movatterモバイル変換

[0]ホーム
URL:

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

 Sign up
Appearance settings

Commit6f9a8e4

Browse files
authored
added-ModularArithmetic-code (TheAlgorithms#1217)
* added-ModularArithmetic-code* fix-typo* suggested changes
1 parentcf482c4 commit6f9a8e4

File tree

2 files changed

+101
-0
lines changed

2 files changed

+101
-0
lines changed

‎Maths/ModularArithmetic.js

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
import{extendedEuclideanGCD}from'./ExtendedEuclideanGCD'
2+
3+
/**
4+
* https://brilliant.org/wiki/modular-arithmetic/
5+
*@param {Number} arg1 first argument
6+
*@param {Number} arg2 second argument
7+
*@returns {Number}
8+
*/
9+
10+
exportclassModRing{
11+
constructor(MOD){
12+
this.MOD=MOD
13+
}
14+
15+
isInputValid=(arg1,arg2)=>{
16+
if(!this.MOD){
17+
thrownewError('Modulus must be initialized in the object constructor')
18+
}
19+
if(typeofarg1!=='number'||typeofarg2!=='number'){
20+
thrownewTypeError('Input must be Numbers')
21+
}
22+
}
23+
/**
24+
* Modulus is Distributive property,
25+
* As a result, we separate it into numbers in order to keep it within MOD's range
26+
*/
27+
28+
add=(arg1,arg2)=>{
29+
this.isInputValid(arg1,arg2)
30+
return((arg1%this.MOD)+(arg2%this.MOD))%this.MOD
31+
}
32+
33+
subtract=(arg1,arg2)=>{
34+
this.isInputValid(arg1,arg2)
35+
// An extra MOD is added to check negative results
36+
return((arg1%this.MOD)-(arg2%this.MOD)+this.MOD)%this.MOD
37+
}
38+
39+
multiply=(arg1,arg2)=>{
40+
this.isInputValid(arg1,arg2)
41+
return((arg1%this.MOD)*(arg2%this.MOD))%this.MOD
42+
}
43+
44+
/**
45+
*
46+
* It is not Possible to find Division directly like the above methods,
47+
* So we have to use the Extended Euclidean Theorem for finding Multiplicative Inverse
48+
* https://github.com/TheAlgorithms/JavaScript/blob/master/Maths/ExtendedEuclideanGCD.js
49+
*/
50+
51+
divide=(arg1,arg2)=>{
52+
// 1st Index contains the required result
53+
// The theorem may have return Negative value, we need to add MOD to make it Positive
54+
return(extendedEuclideanGCD(arg1,arg2)[1]+this.MOD)%this.MOD
55+
}
56+
}

‎Maths/test/ModularArithmetic.test.js

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
import{ModRing}from'../ModularArithmetic'
2+
3+
describe('Modular Arithmetic',()=>{
4+
constMOD=10000007
5+
letring
6+
beforeEach(()=>{
7+
ring=newModRing(MOD)
8+
})
9+
10+
describe('add',()=>{
11+
it('Should return 9999993 for 10000000 and 10000000',()=>{
12+
expect(ring.add(10000000,10000000)).toBe(9999993)
13+
})
14+
it('Should return 9999986 for 10000000 and 20000000',()=>{
15+
expect(ring.add(10000000,20000000)).toBe(9999986)
16+
})
17+
})
18+
19+
describe('subtract',()=>{
20+
it('Should return 1000000 for 10000000 and 9000000',()=>{
21+
expect(ring.subtract(10000000,9000000)).toBe(1000000)
22+
})
23+
it('Should return 7 for 10000000 and 20000000',()=>{
24+
expect(ring.subtract(10000000,20000000)).toBe(7)
25+
})
26+
})
27+
28+
describe('multiply',()=>{
29+
it('Should return 1000000 for 100000 and 10000',()=>{
30+
expect(ring.multiply(100000,10000)).toBe(9999307)
31+
})
32+
it('Should return 7 for 100000 and 10000100',()=>{
33+
expect(ring.multiply(10000000,20000000)).toBe(98)
34+
})
35+
})
36+
37+
describe('divide',()=>{
38+
it('Should return 4 for 3 and 11',()=>{
39+
expect(ring.divide(3,11)).toBe(4)
40+
})
41+
it('Should return 2 for 18 and 7',()=>{
42+
expect(ring.divide(18,7)).toBe(2)
43+
})
44+
})
45+
})

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp