Skip to content

Instantly share code, notes, and snippets.

@krzkaczor
Created May 16, 2015 23:51
Show Gist options
  • Save krzkaczor/0bdba0ee9555659ae5fe to your computer and use it in GitHub Desktop.
Save krzkaczor/0bdba0ee9555659ae5fe to your computer and use it in GitHub Desktop.
Fast modular exponentiation in Java Script
/**
* Fast modular exponentiation for a ^ b mod n
* @returns {number}
*/
var fastModularExponentiation = function(a, b, n) {
a = a % n;
var result = 1;
var x = a;
while(b > 0){
var leastSignificantBit = b % 2;
b = Math.floor(b / 2);
if (leastSignificantBit == 1) {
result = result * x;
result = result % n;
}
x = x * x;
x = x % n;
}
return result;
};
var assert = function(actual, expected){
if (actual != expected){
throw new Error('Assertion failed');
}
};
assert(fastModularExponentiation(12, 53, 7), 3);
assert(fastModularExponentiation(7, 12, 10), 1);
assert(fastModularExponentiation(3, 51, 13), 1);
@calindotgabriel
Copy link

thanks!

@devildelta
Copy link

The function does not give the expected answer in the following function to solve question 48 of Project Euler, which is to find the last 10 digits of sum(n^n) for n = 1 to 1000:

	let sum = 0;
	const digit_window = 10**10;
	for(let i = 1;i<=1000;i++){
		sum = (sum + mexp(i,i,digit_window)) % digit_window
	}
	console.log(sum);

9110846700 is expected but 6621474085 is yielded.

@y-richie-y
Copy link

@devildelta that is because Javascript uses a floating point representation for numbers, in general you should not use Javascript for large arithmetic.

@fnlctrl
Copy link

fnlctrl commented Jun 16, 2019

@y-richie-y @devildelta Now that chrome and node.js support BigInt natively, you can use javascript as well.
Simply append an n to every number literal to use BigInt:

const modExp = function (a, b, n) {
    a = a % n;
    var result = 1n;
    var x = a;
    while (b > 0) {
        var leastSignificantBit = b % 2n;
        b = b / 2n;
        if (leastSignificantBit == 1n) {
            result = result * x;
            result = result % n;
        }
        x = x * x;
        x = x % n;
    }
    return result;
};
let sum = 0n;
const digit_window = 10n**10n;
for(let i = 1n;i<=1000n;i++){
    sum = (sum + modExp(i,i,digit_window)) % digit_window
}
console.log(sum);
// 9110846700n

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment