log2 log10 asymptotic binary splitting

log2_log10_bs.rb

# 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
  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
# 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(15, n) * 4 + log1pinv(24, n) * 2).mult(1, prec)
end

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