decimal to fraction


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Source Code

-- Algorithm to convert A Decimal to A Fraction
-- Original paper, written by J. Kennedy, available at:
-- https://sites.google.com/site/johnkennedyshome/home/downloadable-papers/dec2frac.pdf

-- Returns the integer part of a given decimal number
local function int(arg) return math.floor(arg) end

-- Returns a fraction that approximates a given decimal
-- decimal : a decimal to be converted to a fraction
-- acc     : approximation accuracy, defaults to 1e-8
-- returns : two integer values, the numerator and the denominator of the fraction
return function(decimal, acc)
  acc = acc or 1E-4
  local sign, num, denum
  local sign = (decimal < 0) and -1 or 1
  decimal = math.abs(decimal)
  
  if decimal == int(decimal) then --Handles integers
    num = decimal * sign
    denum = 1
    return num, denum
  end
  
  if decimal < 1E-19 then
    num = sign
    denum = 9999999999999999999
  elseif decimal > 1E+19 then
    num = 9999999999999999999 * sign
    denum = 1
  end

  local z = decimal
  local predenum = 0
  local sc
  denum = 1

  repeat
    z = 1 / (z - int(z))
    sc = denum
    denum = denum * int(z) + predenum
    predenum = sc
    num = int(decimal * denum)
  until ((math.abs(decimal - (num / denum)) < acc) or (z == int(z)))

  num = sign * num
  return num, denum
end
-- Tests for dec2frac.lua
local dec2frac = require 'dec2frac'

local total, pass = 0, 0

local function dec(str, len)
  return #str < len
     and str .. (('.'):rep(len-#str))
      or str:sub(1,len)
end

local function matches(n, d, nf, df) return (n == nf and d == df) end

local function run(message, f)
  total = total + 1
  local ok, err = pcall(f)
  if ok then pass = pass + 1 end
  local status = ok and 'PASSED' or 'FAILED'
  print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

run('Testing dec2frac', function()
  assert(matches(       0,        1, dec2frac(      0       )))
  assert(matches(       5,        1, dec2frac(      5       )))
  assert(matches(      11,        2, dec2frac(    5.5       )))
  assert(matches(      23,       10, dec2frac(    2.3       )))
  assert(matches(     945,      167, dec2frac( 5.6587       )))
  assert(matches(     333,      106, dec2frac(math.pi       )))
  assert(matches(80143857, 25510582, dec2frac(math.pi, 1e-15)))
end)


print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
  :format(total, pass, total-pass, (pass*100/total)))