Created
April 18, 2017 19:04
-
-
Save finom/dd3b02df49a16d8e1035d75531058920 to your computer and use it in GitHub Desktop.
Get unique number
This file contains 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
// Some math based on https://en.wikipedia.org/wiki/Discrete_logarithm | |
// The function fastModularExponentiation allow to generate | |
// pseudo-random unique number from 0 to prime - 1. | |
// In other words every gotten number is converted to another number and returned numbers are unique | |
// Warning! When number arg is more than prime then returned numbers are going to be repeated | |
// thus for biggrer numbers we'll need to choose bigger prime number. | |
// The implementation if fastModularExponentiation is taken there https://gist.github.com/krzkaczor/0bdba0ee9555659ae5fe | |
// Primitive root calc: http://www.bluetulip.org/2014/programs/primitive.html | |
const prime = 9999991; | |
const primitiveRoot = 22; | |
function fastModularExponentiation(a, b, n) { | |
a %= n; // eslint-disable-line no-param-reassign | |
let result = 1; | |
let x = a; | |
while (b > 0) { | |
const leastSignificantBit = b % 2; | |
b = Math.floor(b / 2); // eslint-disable-line no-param-reassign | |
if (leastSignificantBit === 1) { | |
result *= x; | |
result %= n; | |
} | |
x *= x; | |
x %= n; | |
} | |
return result; | |
} | |
function getUniqueNumber(number) { | |
return fastModularExponentiation(primitiveRoot, number, prime); | |
} | |
// TODO: Move this test to another place | |
function test() { // eslint-disable-line no-unused-vars | |
const set = {}; | |
for (let i = 0; i < prime - 1; i++) { // eslint-disable-line no-plusplus | |
const n = getUniqueNumber(i); | |
if (n in set) { | |
throw Error('Not passed'); | |
} | |
set[n] = 1; | |
} | |
console.log('Passed'); // eslint-disable-line no-console | |
} | |
module.exports = getUniqueNumber; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment