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

Structure and Interpretation of Computer Programs: JavaScript Edition
楽天ブックス

開発環境

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

Shi is not correct.

exponentialsを求めてから剰余を計算することになるから、元の方法と比べて大きな整数の剰余を計算することになる。

実際に確認。

コード

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 fast_expt(b, n) {
    return n === 0 ?
        1 :
        is_even(n) ?
            square(fast_expt(b, n / 2)) :
            b * fast_expt(b, n - 1);
}
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 fast_expt(base, exp) % m;
}

function timed_expmod(base, exp, m) {
    let t = get_time();
    display(expmod(base, exp, m));
    display(get_time() - t);
    t = get_time();
    display(expmod1(base, exp, m));
    t = get_time();
    display(get_time() - t);
}

function iter(n) {
    if (n > 0) {
        let base = math_floor(math_random() * 1000),
            exp = math_floor(math_random() * 1000),
            m = math_floor(math_random() * 100);
        display(`base = ${base}, exp = ${exp}, m = ${m}`);
        timed_expmod(base, exp, m);
        iter(n - 1);
    }
}
iter(20);
timed_expmod(2, 5, 3);

入出力結果(Terminal, Zsh)

% node answer1.25.js
base = 112, exp = 208, m = 56
0
0.4781380295753479
NaN
0.0021019577980041504
base = 746, exp = 359, m = 53
25
0.14439600706100464
NaN
0.014458954334259033
base = 939, exp = 942, m = 86
1
0.12046104669570923
NaN
0.0021250247955322266
base = 733, exp = 790, m = 89
22
0.09960198402404785
NaN
0.0011680126190185547
base = 290, exp = 804, m = 79
21
0.02437901496887207
NaN
0.001123964786529541
base = 406, exp = 852, m = 95
1
0.18944597244262695
NaN
0.0035860538482666016
base = 672, exp = 537, m = 62
58
0.02233600616455078
NaN
0.0006740093231201172
base = 721, exp = 787, m = 86
63
0.033877015113830566
NaN
0.0005739927291870117
base = 357, exp = 758, m = 99
81
0.02478998899459839
NaN
0.000558018684387207
base = 527, exp = 294, m = 49
1
0.018157005310058594
NaN
0.0009079575538635254
base = 584, exp = 694, m = 48
16
0.018281996250152588
NaN
0.0004660487174987793
base = 876, exp = 387, m = 47
23
0.017250001430511475
NaN
0.00048804283142089844
base = 963, exp = 635, m = 55
32
0.01661604642868042
NaN
0.0004850029945373535
base = 97, exp = 671, m = 99
31
0.022660017013549805
NaN
0.0029739737510681152
base = 129, exp = 599, m = 64
1
0.01907801628112793
NaN
0.0005199909210205078
base = 562, exp = 759, m = 93
70
0.019347012042999268
NaN
0.0006530284881591797
base = 678, exp = 771, m = 55
7
0.021675944328308105
NaN
0.0005180239677429199
base = 467, exp = 276, m = 72
1
0.016160011291503906
NaN
0.0015990138053894043
base = 336, exp = 338, m = 40
16
0.027198970317840576
NaN
0.0005449652671813965
base = 141, exp = 715, m = 1
0
0.017455995082855225
NaN
0.0005429983139038086
2
0.02722698450088501
2
0.0005509853363037109
%

実際に確認してみたら、大きな累乗を求める際にJavaScriptのnumberの範囲の上限を超えてInfinityになり、そのある数の剰余はNaNになってしまうみたい。ただ、小さい数字の場合には、fast_exptを使用した方が速い。