Skip to content

Instantly share code, notes, and snippets.

@nikitaeverywhere

nikitaeverywhere/getReversedT.js

Last active November 24, 2015 22:32
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nikitaeverywhere/20171c9f2aa8d20b5d8a to your computer and use it in GitHub Desktop.
Save nikitaeverywhere/20171c9f2aa8d20b5d8a to your computer and use it in GitHub Desktop.
Download ZIP
Raw
getReversedT.js
/**
* Code snippet for students ^^
* Tarnavsky used this function to find t^-1 from prime number t and m.
* Usage: var tMinusOne = getRevT(m, t);
* Test case 1: getRevT(121, 5) === 97
* Test case 2: getRevT(9, 7) === 13
*/
function getRevT (m, t) {
function stage (a, b) {
var r = a % b, q = Math.floor(a/b);
return r === 0 ? [] : [q].concat(stage(b, r));
}
function backStage (arr, x, y) {
if (!arr.length) return y;
var z = x - y * arr.pop();
return backStage(arr, y, z);
}
return m + backStage(stage(m, t), 0, 1);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment