Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork5.8k
added-ModularArithmetic-code#1217
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
Merged
raklaptudirm merged 3 commits intoTheAlgorithms:masterfromhiitesh1127:hiitesh1127-patch-5Oct 20, 2022
Uh oh!
There was an error while loading.Please reload this page.
Merged
Changes fromall commits
Commits
Show all changes
3 commits Select commitHold shift + click to select a range
File filter
Filter by extension
Conversations
Failed to load comments.
Loading
Uh oh!
There was an error while loading.Please reload this page.
Jump to
Jump to file
Failed to load files.
Loading
Uh oh!
There was an error while loading.Please reload this page.
Diff view
Diff view
There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,56 @@ | ||
| import { extendedEuclideanGCD } from './ExtendedEuclideanGCD' | ||
| /** | ||
| * https://brilliant.org/wiki/modular-arithmetic/ | ||
| * @param {Number} arg1 first argument | ||
| * @param {Number} arg2 second argument | ||
| * @returns {Number} | ||
| */ | ||
| export class ModRing { | ||
| constructor (MOD) { | ||
| this.MOD = MOD | ||
| } | ||
| isInputValid = (arg1, arg2) => { | ||
| if (!this.MOD) { | ||
| throw new Error('Modulus must be initialized in the object constructor') | ||
| } | ||
| if (typeof arg1 !== 'number' || typeof arg2 !== 'number') { | ||
| throw new TypeError('Input must be Numbers') | ||
| } | ||
| } | ||
| /** | ||
| * Modulus is Distributive property, | ||
| * As a result, we separate it into numbers in order to keep it within MOD's range | ||
| */ | ||
| add = (arg1, arg2) => { | ||
| this.isInputValid(arg1, arg2) | ||
| return ((arg1 % this.MOD) + (arg2 % this.MOD)) % this.MOD | ||
| } | ||
| subtract = (arg1, arg2) => { | ||
| this.isInputValid(arg1, arg2) | ||
| // An extra MOD is added to check negative results | ||
| return ((arg1 % this.MOD) - (arg2 % this.MOD) + this.MOD) % this.MOD | ||
| } | ||
| multiply = (arg1, arg2) => { | ||
| this.isInputValid(arg1, arg2) | ||
| return ((arg1 % this.MOD) * (arg2 % this.MOD)) % this.MOD | ||
| } | ||
| /** | ||
| * | ||
| * It is not Possible to find Division directly like the above methods, | ||
| * So we have to use the Extended Euclidean Theorem for finding Multiplicative Inverse | ||
| * https://github.com/TheAlgorithms/JavaScript/blob/master/Maths/ExtendedEuclideanGCD.js | ||
| */ | ||
| divide = (arg1, arg2) => { | ||
| // 1st Index contains the required result | ||
| // The theorem may have return Negative value, we need to add MOD to make it Positive | ||
| return (extendedEuclideanGCD(arg1, arg2)[1] + this.MOD) % this.MOD | ||
| } | ||
| } |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,45 @@ | ||
| import { ModRing } from '../ModularArithmetic' | ||
| describe('Modular Arithmetic', () => { | ||
| const MOD = 10000007 | ||
| let ring | ||
| beforeEach(() => { | ||
| ring = new ModRing(MOD) | ||
| }) | ||
| describe('add', () => { | ||
| it('Should return 9999993 for 10000000 and 10000000', () => { | ||
| expect(ring.add(10000000, 10000000)).toBe(9999993) | ||
| }) | ||
| it('Should return 9999986 for 10000000 and 20000000', () => { | ||
| expect(ring.add(10000000, 20000000)).toBe(9999986) | ||
| }) | ||
| }) | ||
| describe('subtract', () => { | ||
| it('Should return 1000000 for 10000000 and 9000000', () => { | ||
| expect(ring.subtract(10000000, 9000000)).toBe(1000000) | ||
| }) | ||
| it('Should return 7 for 10000000 and 20000000', () => { | ||
| expect(ring.subtract(10000000, 20000000)).toBe(7) | ||
| }) | ||
| }) | ||
| describe('multiply', () => { | ||
| it('Should return 1000000 for 100000 and 10000', () => { | ||
| expect(ring.multiply(100000, 10000)).toBe(9999307) | ||
| }) | ||
| it('Should return 7 for 100000 and 10000100', () => { | ||
| expect(ring.multiply(10000000, 20000000)).toBe(98) | ||
| }) | ||
| }) | ||
| describe('divide', () => { | ||
| it('Should return 4 for 3 and 11', () => { | ||
| expect(ring.divide(3, 11)).toBe(4) | ||
| }) | ||
| it('Should return 2 for 18 and 7', () => { | ||
| expect(ring.divide(18, 7)).toBe(2) | ||
| }) | ||
| }) | ||
| }) |
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.