local rat = require("Module:Rational")
local utils = require("Module:Utils")
local tip = require("Module:Template input parse")
local med = require("Module:Mediants")
local yesno = require("Module:Yesno")
p = {}
-- TODO:
-- Template for handling multiple entry of JI ratios into a template, and for
-- searching for JI ratios if automatic entry is desired.
-- This is a successor/replacement for JI ratio finder.
-- JI ratios are searched by the following params in a hierarchy:
-- - Search by prime limit. Int limit is used to limit the num/den of ratios.
-- Prime limit takes precedence over subgroup.
-- - Search by subgroup. (Subgroup may contain nonprime numbers, but ratios are
-- currently not supported.) Int limit is used to limit the num/den of ratios.
-- - If neither prime limit or subgroup is present, search by int limit. This
-- is considered the absolute minimum requirement for ratio searching.
-- NOTES:
-- - Prime limits are infinite sets, so int limit is used to restrain the set
-- to a finite size. The same is true for subgroup.
-- - Tenney height is used for further filtering of ratios, and is considered
-- optional. If omitted, tenney height defaults to infinity.
local DEFAULT_FINE_SEARCH_ARGS = {
["Int Limit"] = 50,
["Tenney Height"] = 1/0,
["Complements Only"] = false
}
--------------------------------------------------------------------------------
------------------------------ HELPER FUNCTIONS --------------------------------
--------------------------------------------------------------------------------
-- Does not return anything; entries in source are added to destination.
function p.merge_ratio_tables_without_duplicates(dest_table, source_table)
for i = 1, #source_table do
if not p.find_ratio_in_table(dest_table, source_table[i]) then
table.insert(dest_table, source_table[i])
end
end
end
-- Checks whether a ratio was already in a table
function p.find_ratio_in_table(table_, ratio)
local found = false
for i = 1, #table_ do
if rat.as_float(table_[i]) == rat.as_float(ratio) then
found = true
break
end
end
return found
end
-- Preprocess fine-search args
function p.preprocess_fine_search_args(fine_search_args)
local fine_search_args = fine_search_args or DEFAULT_FINE_SEARCH_ARGS
local tenney_height = fine_search_args["Tenney Height"] or 1/0
local comps_only = fine_search_args["Complements Only"] or false
local int_limit = fine_search_args["Int Limit"] or DEFAULT_INT_LIMIT
return {
["Tenney Height"] = tenney_height,
["Complements Only"] = comps_only,
["Int Limit"] = int_limit
}
end
-- Given a ratio, determine whether to include it based on:
-- - Whether it's between 1/1 and the equave
-- - Whether it's within an int limit (required)
-- - Whether it's below a tenney height (default height is infinity)
-- NOTE: ratio is not of the form defined by module:rational, but equave is!
function p.ratio_within_search(ratio, equave, fine_search_args)
-- Ratio, complement, and equave as float
local ratio_as_float = ratio[1] / ratio[2]
local equave_as_float = rat.as_float(equave)
-- Fine search params for ease of access
local int_limit = fine_search_args["Int Limit"]
local tenney_height = fine_search_args["Tenney Height"]
local comps_only = fine_search_args["Complements Only"]
local ratio_within_int_limit = math.max(ratio[1], ratio[2]) <= int_limit
local ratio_within_tenney_height = math.log(ratio[1] * ratio[2]) / math.log(2) <= tenney_height
local ratio_within_equave = ratio_as_float <= equave_as_float
return ratio_within_int_limit and ratio_within_tenney_height and ratio_within_equave
end
--------------------------------------------------------------------------------
------------------------------- FILTER FUNCTIONS -------------------------------
--------------------------------------------------------------------------------
-- Remove ratios whose complements exceed the int limit and Tenney height.
-- If filtering based on Tenney height is not needed, then Tenney height is set
-- to infinity instead, which should be done by the calling function.
function p.filter_ratios_by_complements(ratios, equave, fine_search_args)
if fine_search_args["Complements Only"] then
local filtered_ratios = {}
for i = 1, #ratios do
local complement = rat.mul(rat.inv(ratios[i]), equave)
if rat.int_limit(complement) <= fine_search_args["Int Limit"] and rat.tenney_height(complement) <= fine_search_args["Tenney Height"] then
table.insert(filtered_ratios, ratios[i])
end
end
return filtered_ratios
else
return ratios
end
end
-- Remove ratios that exceed the Tenney height. This is skipped if the Tenney
-- height is infinity.
function p.filter_ratios_by_tenney_height(ratios, equave, fine_search_args)
if not fine_search_args["Tenney Height"] == 1/0 then
local filtered_ratios = {}
for i = 1, #ratios do
if rat.tenney_height(ratios[i]) <= fine_search_args["Tenney Height"] then
table.insert(filtered_ratios, ratios[i])
end
end
return filtered_ratios
else
return ratios
end
end
--------------------------------------------------------------------------------
----------------------- INT-LIMIT-BASED SEARCH FUNCTION ------------------------
--------------------------------------------------------------------------------
-- Int-limit-based search; finds ratios between 1/1 and an equave, within an int
-- limit.
function p.search_within_equave(equave, fine_search_args)
local equave = equave or rat.new(2,1) -- Defualt equave is 2/1.
local fine_search_args = p.preprocess_fine_search_args(fine_search_args)
local init_ratios = {{1,1}, {1,0}}
local ratios = med.find_only_mediants_by_int_limit(init_ratios, fine_search_args["Int Limit"])
-- Convert to ratios that Module:Rational can work with
for i = 1, #ratios do
ratios[i] = rat.new(ratios[i][1], ratios[i][2])
end
-- Remove ratios that exceed the equave.
-- Note that mediant search returns sorted ratios, so remove them from the
-- end until there's no more to remove.
while rat.gt(ratios[#ratios], equave) do
table.remove(ratios, #ratios)
end
-- Filter out ratios that exceed the int limit.
ratios = p.filter_ratios_by_tenney_height(ratios, equave, fine_search_args)
-- Filter out ratios if their equave complement would be filtered out.
ratios = p.filter_ratios_by_complements(ratios, equave, fine_search_args)
return ratios
end
--------------------------------------------------------------------------------
---------------- WORK-IN-PROGERSS SUBGROUP-BASED SEARCH FUNCTION ---------------
--------------------------------------------------------------------------------
function p.search_by_prime_limit_new(prime_limit, equave, fine_search_args)
local prime_limit = prime_limit or 5
local equave = equave or rat.new(2,1)
local fine_search_args = p.preprocess_fine_search_args(fine_search_args)
-- Find all primes up to the prime limit.
local primes = {}
for i = 2, prime_limit do
local is_prime = true
for j = 2, math.floor(math.sqrt(i)) do
if i % j == 0 then
is_prime = false
break
end
end
if is_prime then
table.insert(primes, rat.new(i))
end
end
-- Perform subgroup search on the primes found, as subgroup-search code can
-- be reused for prime-limit search.
return p.search_by_subgroup_new(primes, equave, fine_search_args)
end
-- WORK-IN-PROGRESS!!
function p.search_by_subgroup_new(subgroup, equave, fine_search_args)
local subgroup = subgroup or {rat.new(2), rat.new(3), rat.new(7)}
local equave = equave or rat.new(2,1)
local fine_search_args = p.preprocess_fine_search_args(fine_search_args)
-- Fine search params for ease of access
local tenney_height = fine_search_args["Tenney Height"]
local comps_only = fine_search_args["Complements Only"]
local int_limit = fine_search_args["Int Limit"]
-- Search for ratios within int limit within subgroup by multiplication.
local products = p.multiply_ratios_using_bfs(rat.new(1), subgroup, int_limit)
-- Use the products found to find all ratios between 1 and the equave.
-- For each ratio found, have it be the denominator and have the numerator
-- be all successive ratios after it. For each new ratio found this way, add
-- it to the table of ratios, excluding ratios that exceed the equave or int
-- limit, and excluding duplicates. This is way faster than performing BFS
-- on each ratio and yields the same results.
local ratios = {}
for i = 1, #products do
local new_ratios = {}
for j = i, #products do
local ratio = rat.div(products[j], products[i])
if rat.as_float(ratio) > rat.as_float(equave) then break end
if not p.find_ratio_in_table(new_ratios, ratio) and rat.int_limit(ratio) <= int_limit then
table.insert(new_ratios, ratio)
end
end
p.merge_ratio_tables_without_duplicates(ratios, new_ratios)
end
-- Sort
table.sort(ratios, rat.lt)
return ratios
end
-- BFS search, implemented as a helper function
function p.multiply_ratios_using_bfs(init_ratio, subgroup, int_limit)
local ratios = { init_ratio }
local i = 1
while i <= #ratios do
local new_ratios = p.multiply_ratio_by_subgroup_elements(ratios[i], subgroup, int_limit)
p.merge_ratio_tables_without_duplicates(ratios, new_ratios)
i = i + 1
end
table.sort(ratios, rat.lt)
return ratios
end
-- Helper function for BFS search; returns { ratio } X subgroup
function p.multiply_ratio_by_subgroup_elements(ratio, subgroup, int_limit)
local ratios = {}
for i = 1, #subgroup do
local new_ratio = rat.mul(ratio, subgroup[i])
if rat.int_limit(new_ratio) <= int_limit and not p.find_ratio_in_table(ratios, new_ratio) then
table.insert(ratios, new_ratio)
end
end
return ratios
end
--------------------------------------------------------------------------------
------------------------ SUBGROUP-BASED SEARCH FUNCTION ------------------------
--------------------------------------------------------------------------------
-- Subgroup-based search; finds ratios between 1/1 and an equave, within a sub-
-- group. An int limit is passed in to limit the size of output, since subgroups
-- are infinite sets. An optional tenney height can be passed in to further
-- limit output.
-- Unlike int limit search, subgroup search can allow for very high int limits,
-- as long as the subgroup is reasonably small and has reasonably small terms.
-- Note that members in a subgroup need not be prime, as long as the terms are,
-- for the most part, relatively prime.
function p.search_by_subgroup_within_equave(subgroup, equave, fine_search_args)
local subgroup = subgroup or { 2, 3, 7 }
local equave = equave or rat.new(2,1) -- Defualt equave is 2/1
local fine_search_args = p.preprocess_fine_search_args(fine_search_args)
-- Be absolutely sure the subgroup's members are sorted!
table.sort(subgroup)
-- Fine search params for ease of access
local int_limit = fine_search_args["Int Limit"]
local tenney_height = fine_search_args["Tenney Height"]
local comps_only = fine_search_args["Complements Only"]
-- Find all possible products given the factors in the subgroup.
-- These will be used to find all possible ratios.
local products = {{1}}
local new_products_found = true
while new_products_found do
local new_products = {}
for i = 1, #subgroup do
for j = 1, #products[#products] do
local new_product = products[#products][j] * subgroup[i]
if new_product <= int_limit then
local product_already_added = false
for k = 1, #new_products do
product_already_added = product_already_added or new_product == new_products[k]
if product_already_added then break end
end
if not product_already_added then
table.insert(new_products, new_product)
end
end
end
end
if #new_products == 0 then
new_products_found = false
else
table.insert(products, new_products)
end
end
-- Consolidate and sort products
local consolidated_products = {}
for i = 1, #products do
for j = 1, #products[i] do
table.insert(consolidated_products, products[i][j])
end
end
products = consolidated_products
table.sort(products)
-- Using the products produced earlier, combine them to make all possible
-- ratios from 1/1 to the equave.
local ratios = {}
local equave_as_float = rat.as_float(equave)
for i = 1, #products do
local denominator = products[i]
for j = i, #products do
local numerator = products[j]
local gcd = utils._gcd(numerator, denominator)
local ratio = { numerator / gcd, denominator / gcd }
local ratio_added_alraedy = false
for k = 1, #ratios do
ratio_added_alraedy = ratios[k][1] == ratio[1] and ratios[k][2] == ratio[2]
if ratio_added_alraedy then
break
end
end
if not ratio_added_alraedy and p.ratio_within_search(ratio, equave, fine_search_args) then
table.insert(ratios, ratio)
end
end
end
-- Convert to ratios that Module:Rational can work with
for i = 1, #ratios do
ratios[i] = rat.new(ratios[i][1], ratios[i][2])
end
-- Sort ratios
table.sort(ratios, rat.lt)
-- Filter out ratios whose complements exceed the int limit
ratios = p.filter_ratios_by_complements(ratios, equave, fine_search_args)
return ratios
end
--------------------------------------------------------------------------------
---------------------- PRIME-LIMIT-BASED SEARCH FUNCTION -----------------------
--------------------------------------------------------------------------------
-- Prime-limit-based search; finds ratios between 1/1 and an equave, within a
-- prime limit. An int limit is passed in to limit the size of output, since
-- prime limits are inifinite sets. An optional tenney height can be passed in
-- to further limit output.
-- Like subgroup search, prime limit search can also allow for very high int
-- limits, as long as the prime is reasonably small.
function p.search_by_prime_limit_within_equave(prime_limit, equave, fine_search_args)
local prime_limit = prime_limit or 5
local equave = equave or rat.new(2,1) -- Defualt equave is 2/1.
local fine_search_args = p.preprocess_fine_search_args(fine_search_args)
-- Find all primes up to the prime limit.
local primes = {}
for i = 2, prime_limit do
local is_prime = true
for j = 2, math.floor(math.sqrt(i)) do
if i % j == 0 then
is_prime = false
break
end
end
if is_prime then
table.insert(primes, i)
end
end
-- Perform subgroup search on the primes found, as subgroup-search code can
-- be reused for prime-limit search.
return p.search_by_subgroup_within_equave(primes, equave, fine_search_args)
end
--------------------------------------------------------------------------------
-------------------------- ARG-BASED SEARCH FUNCTIONS --------------------------
--------------------------------------------------------------------------------
-- Search for ratios based on an array of args passed in. Certain params have
-- their own function calls.
function p.search_by_args_within_equave(equave, search_args)
local equave = equave or rat.new(2,1)
-- For each search method, check whether the corresponding search arg and
-- int limit are both present and pass it and the equave to that function.
-- All other search args are used as finer search args.
-- Note that search by int limit alone just has the equave and search args
-- passed in.
local ratios = {}
if search_args["Prime Limit"] ~= nil and search_args["Int Limit"] ~= nil then
ratios = p.search_by_prime_limit_new(search_args["Prime Limit"], equave, search_args)
elseif search_args["Subgroup"] ~= nil and search_args["Int Limit"] ~= nil then
ratios = p.search_by_subgroup_new(search_args["Subgroup"], equave, search_args)
elseif search_args["Int Limit"] ~= nil then
ratios = p.search_within_equave(equave, search_args)
end
return ratios
end
-- Parse search args.
function p.parse_search_args(search_args)
local parsed = tip.parse_kv_pairs(search_args)
if parsed["Int Limit"] ~= nil then
parsed["Int Limit"] = tonumber(parsed["Int Limit"])
end
if parsed["Tenney Height"] ~= nil then
parsed["Tenney Height"] = tonumber(parsed["Tenney Height"])
end
if parsed["Prime Limit"] ~= nil then
parsed["Prime Limit"] = tonumber(parsed["Prime Limit"])
end
if parsed["Subgroup"] ~= nil then
local subgroup_elements = tip.parse_numeric_pairs(parsed["Subgroup"], ".", "/", true)
for i = 1, #subgroup_elements do
subgroup_elements[i] = rat.new(subgroup_elements[i][1], subgroup_elements[i][2])
end
parsed["Subgroup"] = subgroup_elements
end
if parsed["Complements Only"] ~= nil then
parsed["Complements Only"] = yesno(parsed["Complements Only"])
end
return parsed
end
function p.search_footnotes(search_args)
local result = "Other interpretations are possible."
local autosearch_text = "Automatic search may be inexact."
local search_text = ""
if search_args["Prime Limit"] ~= nil then
search_text = string.format("Ratios shown are within the %s-prime limit.", search_args["Prime Limit"])
.. " " .. autosearch_text
elseif search_args["Subgroup"] ~= nil then
local subgroup_members = {}
for i = 1, #search_args["Subgroup"] do
local a, b = rat.as_pair(search_args["Subgroup"][i])
table.insert(subgroup_members, (b == 1 and string.format("%s", a) or string.format("%s/%s", a, b)))
end
search_text = string.format("Ratios shown are within the %s subgroup.", table.concat(subgroup_members, "."))
.. " " .. autosearch_text
elseif search_args["Int Limit"] ~= nil then
search_text = string.format("Ratios shown are within the %s-integer limit.", search_args["Int Limit"])
.. " " .. autosearch_text
end
result = search_text .. " " .. result
return result
end
--------------------------------------------------------------------------------
--------------------------- RATIO SORTING FUNCTIONS ----------------------------
--------------------------------------------------------------------------------
-- Sorts ratios by closeness to cent values.
function p.sort_by_closeness_to_cent_values(ratios, cent_values, tolerance)
local tolerance = tolerance or 30
local sorted_ratios = {}
local curr_index = 1 -- Index of current_ratio
for i = 1, #cent_values do
local lower_bound = cent_values[i] - tolerance
local upper_bound = cent_values[i] + tolerance
local cents_within_range = true
local curr_ratios = {}
for j = curr_index, #ratios do
local curr_ratio = ratios[j]
local curr_cents = rat.cents(curr_ratio)
if lower_bound < curr_cents and curr_cents < upper_bound then
table.insert(curr_ratios, curr_ratio)
--elseif curr_cents > upper_bound then
-- curr_index = j
-- break
end
end
table.insert(sorted_ratios, curr_ratios)
end
return sorted_ratios
end
--------------------------------------------------------------------------------
------------------------ RATIO PARSING/INPUT FUNCTIONS -------------------------
--------------------------------------------------------------------------------
-- Parse a list of ratios from a string. String is formatted as follows:
-- "a/b; c/d; e/f; g/h"
function p.parse_ratios(unparsed)
local parsed = tip.parse_numeric_pairs(unparsed)
for i = 1, #parsed do
parsed[i] = rat.new(parsed[i][1], parsed[i][2])
end
return parsed
end
--------------------------------------------------------------------------------
---------------------------- RATIO STRING FUNCTIONS ----------------------------
--------------------------------------------------------------------------------
-- Convert a table of ratios into a string, with options for links and delimiter
function p.ratios_as_string(ratios, add_links, delimiter)
local add_links = add_links == true
local delimiter = delimiter or ", "
local text = ""
if #ratios ~= 0 then
text = add_links and string.format("[[%s]]", rat.as_ratio(ratios[1])) or rat.as_ratio(ratios[1])
for i = 2, #ratios do
text = text .. (add_links and string.format("%s[[%s]]", delimiter, rat.as_ratio(ratios[i])) or string.format("%s%s", delimiter, rat.as_ratio(ratios[i])))
end
end
return text
end
-- Convert a jagged array of ratios into an array of strings
function p.ratios_as_strings(ratios, add_links, delimiter)
local add_links = add_links == true
local delimiter = delimiter or ", "
local texts = {}
for i = 1, #ratios do
local text = p.ratios_as_string(ratios[i], add_links, delimiter)
table.insert(texts, text)
end
return texts
end
function p.tester()
local equave = rat.new(2,1)
local fine_search_args = p.parse_search_args("Subgroup: 2.5.9/7.21; Complements Only: 1")
local subgroup = {rat.new(2), rat.new(3), rat.new(5), rat.new(7)}
return p.search_footnotes(fine_search_args)
end
return p
.svg){kind=icon}
