Fraction

L
```-- Fraction "class" with metatable-based operators, featuring modulo and integer exponentiation
-- Fractions are often used to improve numerical stability in algorithms that rely on accurate division
-- which imprecise floating-point operations often can't provide

local gcd = require("math.greatest_common_divisor")
local intpow = require("math.intpow")

local fraction = {}

local metatable = { __index = fraction }

local function shorten(self)
-- Divide numerator & denominator by their GCD
local divisor = gcd(self.numerator, self.denominator)
self.numerator = self.numerator / divisor
self.denominator = self.denominator / divisor
if self.denominator < 0 then -- always move signs to the numerator
self.denominator = -self.denominator
self.numerator = -self.numerator
end
end

local function extend_to_common_denominator(self, other)
local divisor = gcd(self.denominator, other.denominator)
local extend_other = self.denominator / divisor
return other.denominator / divisor * self.numerator,
extend_other * other.numerator,
extend_other * other.denominator
end

local function new(numerator, denominator)
return setmetatable({ numerator = numerator, denominator = denominator }, metatable)
end

-- Constants

fraction.zero = new(0, 1)
fraction.one = new(1, 1)

-- Constructors

function fraction.new(numerator, denominator)
assert(denominator ~= 0)
local self = new(numerator, denominator)
shorten(self)
return self
end

function fraction.from_number(
number -- may be decimal; note that some decimals aren't accurately represented by floats
)
local denominator = 1
while number % 1 ~= 0 do
number = number * 2
denominator = denominator * 2
end
return fraction.new(number, denominator)
end

function fraction.from_string(
str -- string numerator/denominator as produced by tostring(fraction)
)
local numerator, denominator = str:match("^(.-)/(.+)")
return fraction.new(assert(tonumber(assert(numerator))), assert(tonumber(denominator)))
end

base = base or 10
assert(base % 1 == 0 and base >= 2 and base <= 36, "invalid base")
return base
end

function fraction.from_float_string(
str, -- <digit>{<digit>}.{digit}[(<digit>{digit})], ex.: `-1.2(3)`
base -- integer from 2 to 36, defaults to 10 (decimal)
)
return assert(tonumber(str_, base))
end

local integer, fractional = str:match("^([0-9a-zA-Z][0-9a-zA-Z]-)%.([0-9a-zA-Z%(%)]+)")
if not fractional then
end

local pre_period, period = fractional:match("^([0-9a-zA-Z]-)%(([0-9a-zA-Z]+)%)\$")
if not period then
end

local after_dot = (
read_number(pre_period == "" and "0" or pre_period) -- digits before the period
+ fraction.new(read_number(period), base ^ #period - 1)
) -- period
return read_number(integer) + after_dot / base ^ #pre_period
end

-- Conversions

function metatable:__tostring()
return self.numerator .. "/" .. self.denominator
end

local function digit(value)
if value < 10 then -- decimals for bases <= 10
return string.char(("0"):byte() + value)
end
-- letters for bases > 10 up to 36
return string.char(("a"):byte() + value - 10)
end

-- Converts a fraction to a floating point string exactly representing the fraction in the given base
function fraction:to_float_string(
base -- integer from 2 to 36, defaults to 10 (decimal)
)
local base_fraction = new(base, 1)

-- Determine sign
local sign = ""
if self < fraction.zero then
sign = "-"
self = -self
end

-- Split in integer (>= 1) & fractional (< 1) part
local fractional = self % fraction.one
local integer = self - fractional
assert(integer.denominator == 1)
integer = integer.numerator

-- Format integer in given base
local int_digits = {}
while integer ~= 0 do
local digit_value = integer % base -- last (least significant) digit
table.insert(int_digits, digit(digit_value))
integer = (integer - digit_value) / base -- remove last digit, move to next digit
end
-- concat & reverse digits: resulting order is most significant to least significant digit
int_digits = table.concat(int_digits):reverse()
if int_digits == "" then
int_digits = 0
end

if fractional == fraction.zero then -- no fractional part
return sign .. int_digits -- signed integer (ex.: `-42`)
end

local seen_divisions = {} -- [division key] = index of the first fractional digit resulting from the division
local fractional_digits = {} -- list of digits after the point, from most significant to least significant
while fractional ~= fraction.zero do
-- Period handling
local div_key = ("%x/%x"):format(fractional.numerator, fractional.denominator) -- format division as hex a/b
local last_digit_index = seen_divisions[div_key]
if last_digit_index then -- have we seen this division already?
local pre_period_digits = last_digit_index > 1
and table.concat(fractional_digits, "", 1, last_digit_index - 1)
or ""
local period = "(" .. table.concat(fractional_digits, "", last_digit_index) .. ")"
-- signed integer plus fractional part and optional period in parentheses (ex.: `-42.42(3)`)
return sign .. int_digits .. "." .. pre_period_digits .. period
end

local digit_index = #fractional_digits + 1 -- index where the new digit is to be appended
seen_divisions[div_key] = digit_index -- mark division as seen, store index of occurrence

fractional = fractional * base_fraction -- move the point one to the right...
local remaining_fractional = fractional % fraction.one
local digit_value = fractional - remaining_fractional
assert(digit_value.denominator == 1)
digit_value = digit_value.numerator
fractional_digits[digit_index] = digit(digit_value) -- append digit
fractional = remaining_fractional -- proceed with remaining digits, remove this one
end

fractional_digits = table.concat(fractional_digits)
-- signed integer plus fractional part (ex.: `-42.33`)
return sign .. int_digits .. "." .. fractional_digits
end

function fraction:to_number()
return self.numerator / self.denominator -- numeric value of the fraction - possibly lossy
end

-- Operators

local function bin_op(name, operator)
metatable["__" .. name] = function(self, other)
-- Treat numbers as fractions with denominator 1
if type(self) == "number" then
self = fraction.from_number(self)
elseif type(other) == "number" then
other = fraction.from_number(other)
end
return operator(self, other)
end
end

-- Arithmetic binary operators

metatable.__pow = intpow

local self_numerator, other_numerator, common_denominator = extend_to_common_denominator(self, other)
return fraction.new(self_numerator + other_numerator, common_denominator)
end)

bin_op("sub", function(self, other)
local self_numerator, other_numerator, common_denominator = extend_to_common_denominator(self, other)
return fraction.new(self_numerator - other_numerator, common_denominator)
end)

bin_op("mul", function(self, other)
return fraction.new(self.numerator * other.numerator, self.denominator * other.denominator)
end)

bin_op("div", function(self, other)
assert(other.numerator ~= 0, "division by zero")
return fraction.new(self.numerator * other.denominator, self.denominator * other.numerator)
end)

bin_op("mod", function(self, other)
local self_numerator, other_numerator, common_denominator = extend_to_common_denominator(self, other)
return fraction.new(self_numerator % other_numerator, common_denominator)
end)

-- Unary minus

function metatable:__unm()
return new(-self.numerator, self.denominator)
end

-- Comparison operators

bin_op("eq", function(self, other)
-- extending the fractions is not needed for equality comparison as fractions are always shortened
return self.numerator == other.numerator and self.denominator == other.denominator
end)

bin_op("lt", function(self, other)
local self_numerator, other_numerator = extend_to_common_denominator(self, other)
return self_numerator < other_numerator
end)

-- Technically this need not be provided, as Lua automatically defaults properly
bin_op("le", function(self, other)
local self_numerator, other_numerator = extend_to_common_denominator(self, other)
return self_numerator <= other_numerator
end)

return fraction
```