Building Abstractions with Functions - Functions and the Processes They Generate - Example: Testing for Primality - Probabilistic methods - prime, Fermat 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.24の解答を求めてみる。
コード
function square(x) {
return x * x;
}
function is_even(n) {
return n % 2 === 0;
}
function display(x) {
console.log(x);
}
function get_time() {
// return Date.now();
return performance.now();
}
function math_floor(x) {
return Math.floor(x);
}
function math_random() {
return Math.random();
}
function expmod(base, exp, m) {
return exp === 0 ?
1 :
is_even(exp) ?
square(expmod(base, exp / 2, m)) % m :
base * expmod(base, exp - 1, m) % m;
}
function smallest_divisor(n) {
return find_divisor(n, 2);
}
function next(n) {
return n === 2 ?
3 :
n + 2;
}
function find_divisor(n, test_divisor) {
return square(test_divisor) > n ?
n :
divides(test_divisor, n) ?
test_divisor :
// find_divisor(n, test_divisor + 1);
find_divisor(n, next(test_divisor));
}
function divides(a, b) {
return b % a === 0;
}
function fermat_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 :
fermat_test(n) ?
fast_is_prime(n, times - 1) :
false;
}
function timed_prime_test(n) {
display(n);
return start_prime_test(n, get_time());
}
function start_prime_test(n, start_time) {
return fast_is_prime(n, 10) ?
report_prime(get_time() - start_time) :
true;
}
function report_prime(elapsed_time) {
display(" *** ");
display(`${String(elapsed_time)}`);
}
function search_for_primes(start, stop) {
function iter(n) {
n > stop ?
true :
f(n);
}
function f(n) {
timed_prime_test(n);
iter(n + 2);
}
start % 2 === 0 ?
iter(start + 1) :
iter(start);
}
search_for_primes(1001, 1019);
search_for_primes(10001, 10039)
search_for_primes(100001, 100043);
search_for_primes(1000001, 1000039);
入出力結果(Terminal, Zsh)
% node answer1.24.js
1001
1003
1005
1007
1009
***
0.12219798564910889
1011
1013
***
0.024639010429382324
1015
1017
1019
***
0.017154037952423096
10001
10003
10005
10007
***
0.021880030632019043
10009
***
0.04850703477859497
10011
10013
10015
10017
10019
10021
10023
10025
10027
10029
10031
10033
10035
10037
***
0.017830967903137207
10039
***
0.022415995597839355
100001
100003
***
0.030225038528442383
100005
100007
100009
100011
100013
100015
100017
100019
***
0.030609965324401855
100021
100023
100025
100027
100029
100031
100033
100035
100037
100039
100041
100043
***
0.03093796968460083
1000001
1000003
***
0.03696399927139282
1000005
1000007
1000009
1000011
1000013
1000015
1000017
1000019
1000021
1000023
1000025
1000027
1000029
1000031
1000033
***
0.03331094980239868
1000035
1000037
***
0.0342710018157959
1000039
***
0.03790098428726196
%