cs61b lec15 > study_guide > B level 4.grigobreath // https://sp21.datastructur.es/materials/lectures/lec15/lec15#:~:text=public%20void-,grigobreath,-(int%20N)%7B%0A%20%20%20%20%20if

grigobreath.rb

N = 1000

# s = N.times.each_with_object([1, 1]) { |_, a| a << 2*a[-2] + a[-1] }
# p [s, s.size]

# # https://www.crondose.com/2017/02/fibonacci-sequence-generator-ruby/
# s = N.times.reduce([1, 1]) { |a| a << 2*a[-2] + a[-1] }

# # https://docs.ruby-lang.org/ja/master/class/Enumerator.html#S_NEW
# enum = Enumerator.new { |y|
#     a = b = 1
#     loop {
#         y << a
#         a, b = b, 2*a + b
#     }
# }
# s = enum.take(N/2)

s = Array.new(N/2)
s[0] = s[1] = 1
def s.[](i) = fetch(i) || self[i]= 2*self[i-2] + self[i-1]

g = -> n {
    log2_n = Math.log2(n)
    theory = 2.0/3 * n * log2_n
    exact1 = (0..log2_n.floor).sum { |i| s[i] * (n >> i) }
    # exact2 = (0..).lazy.map { |i| s[i] * (n >> i) }.take_while(&:positive?).sum
    # fail unless exact1 == exact2
    puts "%.2f = %.1f / %d\t(n = %d)" % [theory/exact1, theory, exact1, n]
}

(1..30).each &g
(50..N).step(50).each &g

output

0.00 = 0.0 / 1  (n = 1)
0.44 = 1.3 / 3  (n = 2)
0.79 = 3.2 / 4  (n = 3)
0.59 = 5.3 / 9  (n = 4)
0.77 = 7.7 / 10 (n = 5)
0.86 = 10.3 / 12    (n = 6)
1.01 = 13.1 / 13    (n = 7)
0.70 = 16.0 / 23    (n = 8)
0.79 = 19.0 / 24    (n = 9)
0.85 = 22.1 / 26    (n = 10)
0.94 = 25.4 / 27    (n = 11)
0.90 = 28.7 / 32    (n = 12)
0.97 = 32.1 / 33    (n = 13)
1.02 = 35.5 / 35    (n = 14)
1.09 = 39.1 / 36    (n = 15)
0.75 = 42.7 / 57    (n = 16)
0.80 = 46.3 / 58    (n = 17)
0.83 = 50.0 / 60    (n = 18)
0.88 = 53.8 / 61    (n = 19)
0.87 = 57.6 / 66    (n = 20)
0.92 = 61.5 / 67    (n = 21)
0.95 = 65.4 / 69    (n = 22)
0.99 = 69.4 / 70    (n = 23)
0.92 = 73.4 / 80    (n = 24)
0.96 = 77.4 / 81    (n = 25)
0.98 = 81.5 / 83    (n = 26)
1.02 = 85.6 / 84    (n = 27)
1.01 = 89.7 / 89    (n = 28)
1.04 = 93.9 / 90    (n = 29)
1.07 = 98.1 / 92    (n = 30)
0.96 = 188.1 / 195  (n = 50)
0.97 = 442.9 / 457  (n = 100)
0.93 = 722.9 / 780  (n = 150)
0.97 = 1019.2 / 1047    (n = 200)
1.07 = 1327.6 / 1242    (n = 250)
0.94 = 1645.8 / 1760    (n = 300)
0.99 = 1971.9 / 1998    (n = 350)
0.98 = 2305.0 / 2361    (n = 400)
1.01 = 2644.1 / 2620    (n = 450)
1.06 = 2988.6 / 2818    (n = 500)
0.91 = 3337.9 / 3674    (n = 550)
0.94 = 3691.5 / 3920    (n = 600)
0.95 = 4049.2 / 4264    (n = 650)
0.99 = 4410.6 / 4462    (n = 700)
1.01 = 4775.4 / 4721    (n = 750)
0.98 = 5143.4 / 5255    (n = 800)
1.00 = 5514.4 / 5493    (n = 850)
1.01 = 5888.3 / 5840    (n = 900)
1.04 = 6264.8 / 6035    (n = 950)
1.05 = 6643.9 / 6302    (n = 1000)