Skip to content

Instantly share code, notes, and snippets.

@tompng

tompng/log2_log10_bs.rb

Last active September 24, 2025 15:10
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save tompng/eeb157c4d667689b75f41b0655964447 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save tompng/eeb157c4d667689b75f41b0655964447 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. tompng revised this gist Sep 24, 2025. 1 changed file with 29 additions and 15 deletions.
    44 changes: 29 additions & 15 deletions log2_log10_bs.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -1,17 +1,31 @@
    # # log2: [(1/8), 3, (1/9), 2, (1/15), 2]
    # log10: [(1/8), 10, (1/9), 7, (1/15), 6]
    def logn_params(base)
    [*8..20].combination(3).flat_map do |a, b, c|
    [*1..10].repeated_permutation(3).map do |d, e, f|
    [a,b,c,d,e,f]
    # log(10): [[(1/8), 10], [(1/15), 13], [(1/24), 7]]
    # log(2): [[(1/8), 3], [(1/15), 4], [(1/24), 2]]

    def print_logn_params(base)
    value_factors = {}
    (8..30).each do |n|
    num = (1+1r/n)
    (0..30).each do |exp|
    v = num ** exp
    break if v > 2 * base
    value_factors[v] ||= [v, [[num-1, exp]]]
    end
    end.min_by(&prc=proc{|a,b,c,d,e,f|
    aa = (1+1r/a)**d
    bb = (1+1r/b)**e
    cc = (1+1r/c)**f
    dd = base/aa/bb/cc-1; $cc=[1r/a, d, 1r/b, e, 1r/c, f, dd];
    [1r/a, 1r/b, 1r/c, dd.abs].max + dd.numerator.abs
    })=>min;prc[*min]; $cc
    end
    value_factors.values.combination(2).each do |(v1, f1), (v2, f2)|
    value_factors[v1 * v2] ||= [v1 * v2, f1 + f2]
    end
    vfs = value_factors.values.sort!
    found = {}
    vfs.each do |v, fs|
    v2, fs2 = vfs.bsearch { |v2,| v * v2 >= base }
    if v * v2 == base
    fs = (fs + fs2).sort.reverse
    unless found[fs]
    p fs
    found[fs] = true
    end
    end
    end
    end

    # Calculating Taylor series sum using binary splitting method
    @@ -52,10 +66,10 @@ def log1pinv(n, prec)
    # This is slower than BigMath.log(2) and BigMath.log(10) calculated from soving `exp(y)-2=0` `exp(y)-10=0` with Newton's method.
    def log_e_2(prec)
    n = prec + 5
    (log1pinv(8, n) * 3 + log1pinv(9, n) * 2 + log1pinv(15, n) * 2).mult(1, prec)
    (log1pinv(8, n) * 3 + log1pinv(15, n) * 4 + log1pinv(24, n) * 2).mult(1, prec)
    end

    def log_e_10(prec)
    n = prec + 5
    (log1pinv(8, n) * 10 + log1pinv(9, n) * 7 + log1pinv(15, n) * 6).mult(1, prec)
    (log1pinv(8, n) * 10 + log1pinv(15, n) * 13 + log1pinv(24, n) * 7).mult(1, prec)
    end
  2. tompng created this gist Sep 24, 2025.
    61 changes: 61 additions & 0 deletions log2_log10_bs.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,61 @@
    # # log2: [(1/8), 3, (1/9), 2, (1/15), 2]
    # log10: [(1/8), 10, (1/9), 7, (1/15), 6]
    def logn_params(base)
    [*8..20].combination(3).flat_map do |a, b, c|
    [*1..10].repeated_permutation(3).map do |d, e, f|
    [a,b,c,d,e,f]
    end
    end.min_by(&prc=proc{|a,b,c,d,e,f|
    aa = (1+1r/a)**d
    bb = (1+1r/b)**e
    cc = (1+1r/c)**f
    dd = base/aa/bb/cc-1; $cc=[1r/a, d, 1r/b, e, 1r/c, f, dd];
    [1r/a, 1r/b, 1r/c, dd.abs].max + dd.numerator.abs
    })=>min;prc[*min]; $cc
    end

    # Calculating Taylor series sum using binary splitting method
    # Calculates f(x) = (1/x)*(n0/d0)*(1+(1/x)*(n1/d1)*(1+(1/x)*(n2/d2)*(1+(1/x)*(n3/d3)*(1+...))))
    # x.n_significant_digits or ds.size must be small to be performant.
    def _asymptotic_sum_binary_splitting(x, nds, prec) # :nodoc:
    zero = BigDecimal(0)
    fs = nds.map {|n, d| [zero, BigDecimal(n), BigDecimal(d)] }
    # fs = [[a0, a1, a2], [b0, b1, b2], [c0, c1, c2], ...]
    # f(x) = a0/a2+x*(a1/a2)*(1+b0/b2+x*(b1/b2)*(1+c0/c2+x*(c1/c2)*(1+d0/d2+x*(d1/d2)*(1+...))))
    while fs.size > 1
    # Merge two adjacent fractions
    # from: (1 + a0/a2 + (1/x) * a1/a2 * (1 + b0/b2 + (1/x) * b1/b2 * rest))
    # to: (1 + ((a0*b2*x)+a1*(b2+b0))/(a2*b2*x) + (1/x) * (a1*b1)/(a2*b2*x) * rest)
    xn = xn ? xn.mult(xn, prec) : x
    fs = fs.each_slice(2).map do |(a, b)|
    b ||= [zero, zero, BigDecimal(1)]
    [
    (x * a[0].mult(b[2], prec)).add(a[1] * (b[0] + b[2]), prec),
    a[1].mult(b[1], prec),
    x.mult(a[2].mult(b[2], prec), prec)
    ]
    end
    end
    BigDecimal(fs[0][0]).div(fs[0][2], prec)
    end

    def log1pinv(n, prec)
    # log(1+1/n) = 1/n - 1/(2*n^2) + 1/(3*n^3) - 1/(4*n^4) + ...
    kmax = (1..).bsearch do |k|
    # k*n**k > 10**prec
    Math.log10(k) + Math.log10(n) * k > prec
    end
    params = [[1, 1]] + (2..kmax).map { [1 - it, it] }
    _asymptotic_sum_binary_splitting(BigDecimal(n), params, prec)
    end

    # This is slower than BigMath.log(2) and BigMath.log(10) calculated from soving `exp(y)-2=0` `exp(y)-10=0` with Newton's method.
    def log_e_2(prec)
    n = prec + 5
    (log1pinv(8, n) * 3 + log1pinv(9, n) * 2 + log1pinv(15, n) * 2).mult(1, prec)
    end

    def log_e_10(prec)
    n = prec + 5
    (log1pinv(8, n) * 10 + log1pinv(9, n) * 7 + log1pinv(15, n) * 6).mult(1, prec)
    end