Sponsoring The Perl Toolchain Summit 2025: Help make this important event another success Learn more

TRIZEN / Sidef-24.11 / scripts / Tests / number_binary_search.sf 

            

              
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

              
#!/usr/bin/ruby
var n = 10**19
assert_eq(n.bsearch_le { |k|
    ((k*(log(k)-1) + log(Num.tau*k)/2)) / log(10) <=> n
}, 577134533044522749)  # see also: https://oeis.org/A119906
assert_eq(n.bsearch_ge { |k|
    ((k*(log(k)-1) + log(Num.tau*k)/2)) / log(10) <=> n
}, 577134533044522750)
assert_eq(bsearch_le(100, 200, {|n| exp(n) <=> 10**65 }), 149)   # i.e.: exp(149) <= 10^65
assert_eq(bsearch_ge(100, 200, {|n| exp(n) <=> 10**65 }),150)    # i.e.: exp(150) >= 10^65
assert_eq(100.bsearch {|n| n! <=> 120 }, 5)           # 5! = 120
assert_eq(bsearch(50, 80, {|n| n**2 <=> 4225 }), 65)  # 65^2 = 4225
define τ = Num.tau
func number_of_required_terms(n) {
    n.bsearch_le { |k|
        ((k*(log(k)-1) + log(τ*k)/2)) / log(10) <=> n
    }
}
assert_eq(number_of_required_terms(100), 69)
assert_eq(number_of_required_terms(500), 253)
assert_eq(number_of_required_terms(1e20), 5463531774867094396)
assert_eq(number_of_required_terms(1e21), 51865645374019695121)
assert_eq(20..100 -> bsearch { |n| n! <=> 30! }, 30)
assert_eq(42..100 -> bsearch_le { |n| exp(n) <=> 10**28 }, 64)   # i.e.: exp(64) <= 10^28
assert_eq(42..100 -> bsearch_ge { |n| exp(n) <=> 10**28 }, 65)   # i.e.: exp(65) >= 10^28
for k in (1..100) {
    var t = bsearch_min(1, irand(1e4,1e5), {|p|
        pi(p) <=> k
    })
    assert_eq(pi(t), k)
    assert(pi(t-1) < k)
    var u = bsearch_max(1, irand(1e4,1e5), {|p|
        pi(p) <=> k
    })
    assert_eq(pi(u), k)
    assert(pi(u+1) > k)
}
for k in (1..100) {
    var q = prime(k)
    var t = bsearch_min(1, irand(1e4,1e5), {|p|
        prime(p) <=> q
    })
    assert_eq(prime(t), q)
    var u = bsearch_max(1, irand(1e4,1e5), {|p|
        prime(p) <=> q
    })
    assert_eq(prime(u), q)
}
for k in (2..100) {
    var t = bsearch_min(1, irand(1e4,1e5), {|p|
        prime(p) <=> k
    })
    assert(prime(t) >= k, "prime(#{t}) >= #{k}")
    assert(prime(t+1) > k, "prime(#{t}+1) > #{k}")
    assert(prime(t-1) < k, "prime(#{t}-1) < #{k}")
    var u = bsearch_max(1, irand(1e4,1e5), {|p|
        prime(p) <=> k
    })
    assert(prime(u) <= k, "prime(#{t}) <= #{k}")
    assert(prime(u+1) > k, "prime(#{t}) > #{k}")
    assert(prime(u-1) < k, "prime(#{t}) < #{k}")
}
say "** Test passed!"