rational approximation

rational approximation

# rational approximation, approximate a ratio with a rational number n / d
function rational_approx(ratio::Float64, tol::Float64)
  # given a list of values for a continued fraction
  # reconstruct as a simple fraction n / d
  function re_construct(fract_list)
    rev_list = reverse(fract_list)
    n = rev_list[1]
    d = 1
    for x in rev_list[2:end]
      new_n = n * x + d
      new_d = n
      n = new_n
      d = new_d
    end
    n, d
  end

  # iteratively compute the values for the continued fraction 
  cur_decim_part = ratio % 1
  fract_list = [floor(ratio)]
  fracts = re_construct(fract_list)
  # while precision is insufficient, expand the fraction
  while(abs(fracts[1] / fracts[2] - ratio) > tol)
    new_1_over = 1 / cur_decim_part
    cur_decim_part = new_1_over % 1
    push!(fract_list, floor(new_1_over))
    fracts = re_construct(fract_list)
  end
  fracts
end

# approximating 0.387 with a fraction with tolerance of 0.001
rational_approx(0.387, 0.001)
# the result is 12 / 31 
12 / 31