計算機科学のブログ

Building Abstractions with Functions - Functions and the Processes They Generate - Example: Testing for Primality - Probabilistic methods - applicative-order, process, log, linear

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

normal-orderではなくapplicative-orderでは、元のコードだとexpmod(base, exp / 2, m)を計算してからsquareが適用されるから、expmod(base, exp / 2, m)の計算は1回で済むけど、問題のコードだとexp(base, exp / 2, m)の計算が2回計算することになるから。

実際に速度の違いを確認。

コード

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 expmod1(base, exp, m) {
    return exp === 0 ?
        1 :
        is_even(exp) ?
            (expmod1(base, exp / 2, m) * expmod1(base, exp / 2, m)) % m :
            (base * expmod1(base, exp - 1, 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 fermat_test1(n) {
    function try_it(a) {
        return expmod1(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 fast_is_prime1(n, times) {
    return times === 0 ?
        true :
        fermat_test1(n) ?
            fast_is_prime1(n, times - 1) :
            false;
}
function timed_prime_test(n) {
    display(n);
    return start_prime_test(n, get_time());
}
function timed_prime_test1(n) {
    display(n);
    return start_prime_test1(n, get_time());
}
function start_prime_test(n, start_time) {
    return fast_is_prime(n, 10) ?
        report_prime(get_time() - start_time) :
        true;
}
function start_prime_test1(n, start_time) {
    return fast_is_prime1(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);
}
function search_for_primes1(start, stop) {
    function iter(n) {
        n > stop ?
            true :
            f(n);
    }
    function f(n) {
        timed_prime_test1(n);
        iter(n + 2);
    }
    start % 2 === 0 ?
        iter(start + 1) :
        iter(start);
}

display('log');
search_for_primes(101, 107);
search_for_primes(1001, 1039);
search_for_primes(10001, 10037);
display('linear');
search_for_primes1(101, 107);
search_for_primes1(1001, 1039);
search_for_primes1(10001, 10037);

入出力結果(Terminal, Zsh)

% node answer1.26.js
log
101
 *** 
0.2722399830818176
103
 *** 
0.019895970821380615
105
107
 *** 
0.019631028175354004
1001
1003
1005
1007
1009
 *** 
0.014706015586853027
1011
1013
 *** 
0.019262969493865967
1015
1017
1019
 *** 
0.018829941749572754
1021
 *** 
0.01666104793548584
1023
1025
1027
1029
1031
 *** 
0.034102022647857666
1033
 *** 
0.012418031692504883
1035
1037
1039
 *** 
0.01595902442932129
10001
10003
10005
10007
 *** 
0.018359005451202393
10009
 *** 
0.020741045475006104
10011
10013
10015
10017
10019
10021
10023
10025
10027
10029
10031
10033
10035
10037
 *** 
0.01862400770187378
linear
101
 *** 
0.30984997749328613
103
 *** 
0.22511601448059082
105
107
 *** 
0.23339003324508667
1001
1003
1005
1007
1009
 *** 
1.286895990371704
1011
1013
 *** 
0.5690180063247681
1015
1017
1019
 *** 
0.217989981174469
1021
 *** 
0.2177630066871643
1023
1025
1027
1029
1031
 *** 
0.32638198137283325
1033
 *** 
0.3273810148239136
1035
1037
1039
 *** 
0.323852002620697
10001
10003
10005
10007
 *** 
2.9872609972953796
10009
 *** 
2.789187967777252
10011
10013
10015
10017
10019
10021
10023
10025
10027
10029
10031
10033
10035
10037
 *** 
3.7627260088920593
%