Building Abstractions with Functions - Functions and the Processes They Generate - Example: Testing for Primality - Probabilistic methods - Miller-Rabin test
Structure and Interpretation of Computer Programs: JavaScript Edition(Harold Abelson(著)、Gerald Jay Sussman(著)、Julie Sussman(著)、The MIT Press)のChapter 1(Building Abstractions with Functions)、1.2(Functions and the Processes They Generate)、1.2.6(Example: Testing for Primality)、Probabilistic methods、Exercise 1.28の解答を求めてみる。
コード
function square(x) {
return x * x;
}
function is_even(n) {
return n % 2 === 0;
}
function display(x) {
console.log(x);
}
function math_floor(x) {
return Math.floor(x);
}
function math_random() {
return Math.random();
}
function expmod(base, exp, m) {
function nontrivial_square_root_signal(n) {
let r = square(n) % m;
return n !== 1 && n !== m - 1 && r === 1 ?
0 :
r;
}
return exp === 0 ?
1 :
is_even(exp) ?
nontrivial_square_root_signal(expmod(base, exp / 2, m)) :
(base * expmod(base, exp - 1, m)) % m;
}
function miller_rabin_test(n) {
function try_it(a) {
return expmod(a, n, n) === a;
}
return try_it(1 + math_floor(math_random() * (n - 1)));
}
function fast_is_prime(n, times) {
return times === 0 ?
true :
miller_rabin_test(n) ?
fast_is_prime(n, times - 1) :
false;
}
function is_prime(n) {
return fast_is_prime(n, 10);
}
console.log('Carmichael numbers');
console.log(is_prime(561));
console.log(is_prime(1105));
console.log(is_prime(1729));
console.log(is_prime(2465));
console.log(is_prime(2821));
console.log(is_prime(6601));
console.log('素数');
console.log(is_prime(2));
console.log(is_prime(3));
console.log(is_prime(5));
console.log(is_prime(7));
console.log(is_prime(1009));
入出力結果(Terminal, Zsh)
% node answer1.28.js
Carmichael numbers
false
false
false
false
false
false
素数
true
true
true
true
true
%