計算機科学のブログ

Building Abstractions with Functions - Functions and the Processes They Generate - Example: Testing for Primality - Probabilistic methods - even, odd

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.23の解答を求めてみる。

コード

function square(x) {
    return x * x;
}
function display(x) {
    console.log(x);
}
function get_time() {
    // return Date.now();
    return performance.now();
}
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 is_prime(n) {
    return n === smallest_divisor(n);
}
function timed_prime_test(n) {
    display(n);
    return start_prime_test(n, get_time());
}
function start_prime_test(n, start_time) {
    return is_prime(n) ?
        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.23.js
1001
1003
1005
1007
1009
 *** 
0.004269003868103027
1011
1013
 *** 
0.004587024450302124
1015
1017
1019
 *** 
0.004538983106613159
10001
10003
10005
10007
 *** 
0.005214005708694458
10009
 *** 
0.0054750144481658936
10011
10013
10015
10017
10019
10021
10023
10025
10027
10029
10031
10033
10035
10037
 *** 
0.004469007253646851
10039
 *** 
0.004980981349945068
100001
100003
 *** 
0.011891007423400879
100005
100007
100009
100011
100013
100015
100017
100019
 *** 
0.014627009630203247
100021
100023
100025
100027
100029
100031
100033
100035
100037
100039
100041
100043
 *** 
0.01186099648475647
1000001
1000003
 *** 
0.046591997146606445
1000005
1000007
1000009
1000011
1000013
1000015
1000017
1000019
1000021
1000023
1000025
1000027
1000029
1000031
1000033
 *** 
0.03972700238227844
1000035
1000037
 *** 
0.036972999572753906
1000039
 *** 
0.0607990026473999
%