Module:Mediants

Module documentation[view] [edit] [history] [purge]

This module primarily serves as a library for other modules and has no corresponding template.

Module:Mediants is used for finding mediants starting from a set of starting ratios (by default, 1/1 and 1/0), either by search depth, integer limit, or by a custom search function.

Introspection summary for Module:Mediants

Functions provided (14) Line Function Params 18 deepest_depth (depths) 30 simplify_ratio (ratio) 36 sort_ratios (ratios) 52 to_rational (ratio) 58 to_rationals (ratios) 89 int_limit_search (mediant_data, int_limit) 96 depth_search (mediant_data, search_depth) 112 find_mediants_by_search_func (init_ratios, search_func, search_args) 157 find_only_mediants_by_search_func (init_ratios, search_func, search_args) 174 find_mediants (init_ratios, depth) 185 find_only_mediants (init_ratios, depth) 204 find_mediants_by_int_limit (init_ratios, int_limit) 215 find_only_mediants_by_int_limit (init_ratios, int_limit) 229 tester none

Lua modules required (2) Variable Module Functions used rat Module:Rational new utils Module:Utils _gcd

No function descriptions were provided. The Lua code may have further information.

---

-- This module follows [[User:Ganaram inukshuk/Provisional style guide for Lua]]
local rat   = require("Module:Rational")
local utils = require("Module:Utils")

local p = {}

-- Mediants consists of code used to find a tree of mediants, starting from a
-- set of starting ratios (default 1/1 and 1/0). Search can be by int limit,
-- depth, or a custom search function.
-- Ratios produced this way are a table consisting of the numerator and
-- denominator, which allows for non-simplified ratios to be represented.

--------------------------------------------------------------------------------
------------------------------ UTILITY FUNCTIONS -------------------------------
--------------------------------------------------------------------------------

-- Given a table of depths, return the deepest depth
function p.deepest_depth(depths)
	local deepest = nil
	for _, value in ipairs(depths) do
		if not deepest or value > deepest then
			deepest = value
		end
	end
	
	return deepest
end

-- Given a ratio, return its simplified form.
function p.simplify_ratio(ratio)
	local gcd = utils._gcd(ratio[1], ratio[2])
	return { ratio[1] / gcd, ratio[2] / gcd }
end

-- Sort ratios in ascending order. Comparison function is built-in.
function p.sort_ratios(ratios)
	table.sort(ratios, function(ratio_1, ratio_2)
		return ratio_1[1] / ratio_1[2] < ratio_2[1] / ratio_2[2]
		end
	)
end

--------------------------------------------------------------------------------
----------------------------- CONVERTER FUNCTIONS ------------------------------
--------------------------------------------------------------------------------

-- Converts ratios into the form defined by [[Module:Rational]], a table 
-- consisting of its prime factorization.

-- Given a single ratio, as a table of two numbers, convert to rational and
-- return it.
function p.to_rational(ratio)
	return rat.new(ratio[1], ratio[2])
end

-- Given a table of ratios, each a table of two numbers, return an array of
-- ratios in the form as defined by module:Rational.
function p.to_rationals(ratios)
	local rats = {}
	for i = 1, #ratios do
		table.insert(rats, p.to_rational(ratios[i]))
	end
	return rats
end

--------------------------------------------------------------------------------
------------------------------- SEARCH FUNCTIONS -------------------------------
--------------------------------------------------------------------------------

-- Search functions determine whether a mediant meets a specific criteria for
-- being added to a set of mediants, be it based on something about the mediant,
-- its search depth, the ratios that produced the mediant, or any combination
-- thereof.
-- NOTE: some search criteria, such as prime limit, are considered unsuitable,
-- since mediants not within a prime limit are used to find ratios within a
-- prime limit, it will likely prevent desired ratios from being found at all.
-- For this reason, these functions are meant for broad search, and finer
-- filtering must be done afterwards.

-- A search function has two params: a table containing the mediant and the
-- depth it was found at, and a search param.
-- Mediant data is a table that contains the mediant, the search depth it was
-- found at, and the two ratios that were used to find the mediant.
-- The search params can be a single numeric value, or a table of values for
-- finer control.

-- Int limit search determines whether a ratio is within an int limit. Only uses
-- information about the mediant. Meant for use with searching for JI ratios.
function p.int_limit_search(mediant_data, int_limit)
	local mediant = mediant_data["mediant"]
	return math.max(mediant[1], mediant[2]) <= int_limit
end

-- Depth search determines whether a ratio is within a target depth. Only uses
-- the depth it was found at. Meant for use with searching for step ratios.
function p.depth_search(mediant_data, search_depth)
	local depth = mediant_data["depth"]
	return depth <= search_depth
end

--------------------------------------------------------------------------------
---------------------------- GENERAL SEARCH FUNCTION ---------------------------
--------------------------------------------------------------------------------

-- General search function searches for mediants using a filter function. A
-- custom filter function can be passed in to "filter" out mediants. Ratios
-- are added using a while loop, which exits if a loop iteration adds no new
-- ratios.

-- Find mediants by filter, where the filter function and its args are passed in
-- as part of the function call.
function p.find_mediants_by_search_func(init_ratios, search_func, search_args)
	local init_ratios = init_ratios or {{1,1}, {1,0}}
	
	local ratios = {}
	local depths = {}
	for i = 1, #init_ratios do
		table.insert(ratios, init_ratios[i])
		table.insert(depths, 0)
	end
	
	local new_ratios_added = true
	while new_ratios_added do
		new_ratios_added = false
		local new_ratios = {}
		local new_depths = {}
		
		for i = 1, #ratios-1 do
			local ratio_1 = ratios[i]
			local ratio_2 = ratios[i+1]
			local mediant = { ratio_1[1] + ratio_2[1], ratio_1[2] + ratio_2[2] }
			table.insert(new_ratios, ratio_1)
			
			local depth_1 = depths[i]
			local depth_2 = depths[i+1]
			local new_depth = math.max(depth_1, depth_2) + 1
			table.insert(new_depths, depth_1)
			
			local mediant_data = { ["mediant"] = mediant, ["depth"] = new_depth, ["ratio_1"] = ratio_1, ["ratio_2"] = ratio_2 }
			if search_func(mediant_data, search_args) then
				table.insert(new_ratios, mediant)
				table.insert(new_depths, new_depth)
				new_ratios_added = true
			end
		end
		table.insert(new_ratios, ratios[#ratios])
		table.insert(new_depths, depths[#depths])
		
		ratios = new_ratios
		depths = new_depths
	end
	return ratios, depths
end

-- Find mediants by filter, where the filter function and its args are passed in
-- as part of the function call. Only returns mediants, not depths.
function p.find_only_mediants_by_search_func(init_ratios, search_func, search_args)
	local init_ratios = init_ratios or {{1,1}, {1,0}}
	
	local ratios, depths
	ratios, depths = p.find_mediants_by_search_func(init_ratios, search_func, search_args)
	return ratios
end

--------------------------------------------------------------------------------
------------------------- DEPTH-BASED SEARCH FUNCTION --------------------------
--------------------------------------------------------------------------------

-- Depth-based search finds mediants by building a tree of mediants up to a
-- specified depth. This is made a standalone function under the reasoning that
-- it's a common enough operation.

-- Find mediants by depth of its search tree.
function p.find_mediants(init_ratios, depth)
	local init_ratios = init_ratios or {{1,1}, {1,0}}
	local depth = depth or 5

	local ratios, depths
	ratios, depths = p.find_mediants_by_search_func(init_ratios, p.depth_search, depth)
	
	return ratios, depths
end

-- Find mediants by depth of its search tree. Does not return depths.
function p.find_only_mediants(init_ratios, depth)
	local init_ratios = init_ratios or {{1,1}, {1,0}}
	local depth = depth or 5

	local ratios, depths
	ratios, depths = p.find_mediants_by_search_func(init_ratios, p.depth_search, depth)
	
	return ratios
end

--------------------------------------------------------------------------------
---------------------- INT-LIMIT-BASED SEARCH FUNCTION -------------------------
--------------------------------------------------------------------------------

-- Int limit search finds mediants up to an integer limit, not permitting ratios
-- whose numerator or denominator exceeds the int limit. This is made a stand-
-- alone function under the reasoning that it's a common enough operation.

-- Find mediants within an int limit.
function p.find_mediants_by_int_limit(init_ratios, int_limit)
	local init_ratios = init_ratios or {{1,1}, {1,0}}
	local int_limit = int_limit or 50
	
	local ratios, depths
	ratios, depths = p.find_mediants_by_search_func(init_ratios, p.int_limit_search, int_limit)
	
	return ratios, depths
end

-- Find mediants within an int limit. Does not return depth.
function p.find_only_mediants_by_int_limit(init_ratios, int_limit)
	local init_ratios = init_ratios or {{1,1}, {1,0}}
	local int_limit = int_limit or 50
	
	local ratios, depths
	ratios, depths = p.find_mediants_by_search_func(init_ratios, p.int_limit_search, int_limit)
	
	return ratios
end

--------------------------------------------------------------------------------
----------------------------------- TESTER -------------------------------------
--------------------------------------------------------------------------------

function p.tester()
	--return p.find_only_mediants_by_int_limit()
	local ratios = {{4,3}, {5,1}, {3,2}}
	p.sort_ratios(ratios)
	return p.to_rationals(ratios)
end

return p