計算機科学のブログ

function is_even(n) {
    return n % 2 === 0;
}
function square(x) {
    return x * x;
}
function expt(b, n) {
    function iter(n, a) {
        return n === 0 ?
            a :
            is_even(n) ?
                iter(n - 2, square(b) * a) :
                iter(n - 1, b * a);
    }
    return iter(n, 1);
}

const tolerance = 0.00001;
function fixed_point(f, first_guess) {
    function close_enough(x, y) {
        return Math.abs(x - y) < tolerance;
    }
    function try_with(guess) {
        const next = f(guess);
        return close_enough(guess, next) ?
            next :
            try_with(next);
    }
    return try_with(first_guess);
}
function average(x, y) {
    return (x + y) / 2;
}
function compose(f, g) {
    return x => f(g(x));
}
function repeat(f, n) {
    return n === 1 ?
        f :
        compose(f, repeat(f, n - 1));
}
function average_damp(f) {
    return x => average(x, f(x));
}
function n_root_search(x, n, m) {
    return fixed_point(
        repeat(average_damp, m)(y => x / expt(y, n - 1)),
        1
    );
}
function f(n, m) {
    console.log(`2^${n} ${m}回 ${n_root_search(expt(2, n), n, m)}`);
}
// f(2, 0);
f(2, 1);
f(3, 1);
// f(4, 1);
f(4, 2);
f(5, 2);
f(6, 2);
f(7, 2);
// f(8, 2);
f(8, 3);
f(9, 3);
f(10, 3);
f(11, 3);
f(12, 3);
f(13, 3);
f(14, 3);
f(15, 3);
// f(16, 3);
f(16, 4);
f(17, 4);
f(19, 4);
f(20, 4);
f(21, 4);
f(22, 4);
f(23, 4);
f(24, 4);
f(25, 4);
f(26, 4);
f(27, 4);
f(28, 4);
f(29, 4);
f(30, 4);
f(31, 4);
// f(32, 4);
f(32, 5);

function log_iter(n) {
    function f(k) {
        if (k <= n) {
            console.log(`log_{2} ${k} = ${Math.log(k) / Math.log(2)}`)
            f(k + 1);
        }
    }
    f(1);
}
log_iter(32);

 % node answer1.45.js
2^2 1回 2.000000000000002
2^3 1回 1.9999981824788517
2^4 2回 2.0000000000021965
2^5 2回 2.000001512995761
2^6 2回 2.0000029334662086
2^7 2回 2.0000035538623377
2^8 3回 2.000000000003967
2^9 3回 1.9999997106840102
2^10 3回 2.0000011830103324
2^11 3回 1.999997600654736
2^12 3回 1.9999976914703093
2^13 3回 2.0000029085658984
2^14 3回 1.9999963265447056
2^15 3回 2.0000040951543028
2^16 4回 2.0000000000769576
2^17 4回 2.0000000561635765
2^19 4回 2.0000003649180282
2^20 4回 1.999999063225966
2^21 4回 2.000001254054255
2^22 4回 1.9999986334227025
2^23 4回 1.999997131591442
2^24 4回 1.9999978146920847
2^25 4回 1.9999977429539466
2^26 4回 1.9999975541207249
2^27 4回 1.9999966641661144
2^28 4回 1.9999957943905207
2^29 4回 1.9999957104786472
2^30 4回 2.000004490765405
2^31 4回 1.9999951809750391
2^32 5回 2.000000000000006
log_{2} 1 = 0
log_{2} 2 = 1
log_{2} 3 = 1.584962500721156
log_{2} 4 = 2
log_{2} 5 = 2.321928094887362
log_{2} 6 = 2.584962500721156
log_{2} 7 = 2.807354922057604
log_{2} 8 = 3
log_{2} 9 = 3.1699250014423126
log_{2} 10 = 3.3219280948873626
log_{2} 11 = 3.4594316186372978
log_{2} 12 = 3.5849625007211565
log_{2} 13 = 3.700439718141092
log_{2} 14 = 3.8073549220576037
log_{2} 15 = 3.9068905956085187
log_{2} 16 = 4
log_{2} 17 = 4.08746284125034
log_{2} 18 = 4.169925001442312
log_{2} 19 = 4.247927513443585
log_{2} 20 = 4.321928094887363
log_{2} 21 = 4.392317422778761
log_{2} 22 = 4.459431618637297
log_{2} 23 = 4.523561956057013
log_{2} 24 = 4.584962500721157
log_{2} 25 = 4.643856189774724
log_{2} 26 = 4.700439718141093
log_{2} 27 = 4.754887502163469
log_{2} 28 = 4.807354922057604
log_{2} 29 = 4.857980995127573
log_{2} 30 = 4.906890595608519
log_{2} 31 = 4.954196310386876
log_{2} 32 = 5
%