Xenharmonic Wiki

Module:JI ratios: Difference between revisions

← Older editNewer edit →
Ganaram inukshuk (talk | contribs)
autopatrolled, emailconfirmed
6,211 edits
m m.member_name -> med.member_name; use standalone int-limit search function
Ganaram inukshuk (talk | contribs)
autopatrolled, emailconfirmed
6,211 edits
Rename/reorganize functions; add prime-limit search by reusing subgroup-search code
Line 6: Line 6:


-- TODO:
-- TODO:
-- Adopt mediants module by using custom mediant search function
-- Replace old int-limit search function with new one
-- Add tenney height to int-limit and subgroup search so filtering is done
-- mid-search instead of afterwards


-- Template for handling multiple entry of JI ratios into a template, and for
-- Template for handling multiple entry of JI ratios into a template, and for
Line 15: Line 13:


-- JI ratios are searched by the following params in a hierarchy:
-- JI ratios are searched by the following params in a hierarchy:
-- - The absolute minimum for ratio search int limit, which limits the maximum
-- - Search by prime limit. Int limit is used to limit the num/den of ratios.
--  size of the numerator and denominator.
--  Prime limit takes precedence over subgroup.
-- - If subgroup is present, ratios are searched by subgroup within an int
-- - Search by subgroup. (Subgroup may contain nonprime numbers, but ratios are
--  limit. Subgroup takes precedence over prime limit, as subgroup is
--  currently not supported.) Int limit is used to limit the num/den of ratios.
--  (typically) a subset of prime limit, so prime limit is ignored. (Nonprime
-- - If neither prime limit or subgroup is present, search by prime limit. This
--  subgroups take precedence over prime subgroups.)
--  is considered the absolute minimum requirement for ratio searching.
-- - If prime limit is present, ratios are searched by prime limit within an int
--  limit.
-- NOTES:
-- NOTES:
-- - Prime limits are infinite sets, so int limit is used to restrain the set
-- - Prime limits are infinite sets, so int limit is used to restrain the set
--  to a finite size. The same is true for subgroup.
--  to a finite size. The same is true for subgroup.
-- - Tenney height is used for further filtering of ratios, and is considered
-- - Tenney height is used for further filtering of ratios, and is considered
--  optional.
--  optional. If omitted, tenney height defaults to infinity.


-- INT_LIMIT_MAX is hardcoded to limit the size of output.
-- INT_LIMIT_MAX is hardcoded to limit the size of output. This only applies to
-- int limit search, as other search functions (subgroup, prime-limit) may allow
-- higher search maxima. For reference, searching within the octave yields this
-- many ratios:
-- 400 -> ~24000 ratios
-- 400 -> ~24000 ratios
-- 300 -> ~14000 ratios
-- 300 -> ~14000 ratios
Line 44: Line 43:
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------


-- Find JI ratios up to an integer limit within the octave by finding mediants.
-- Function to be replaced with new one
-- A cent value can be passed in to either exclude ratios that are above an
-- interval below the octave or include ratios above the octave.
function p.search_by_int_limit(integer_limit, max_cents)
function p.search_by_int_limit(integer_limit, max_cents)
local max_cents = max_cents or 1200
local max_cents = max_cents or 1200
Line 92: Line 89:
end
end


--------------------------------------------------------------------------------
-- Int-limit-based search; finds ratios between 1/1 and an equave, within an int
------------------------ SUBGROUP-BASED SEARCH FUNCTION ------------------------
-- limit. An optional tenney height can be passed in.
--------------------------------------------------------------------------------
-- Int limit is hardcoded to a max size to restrict the size of output, to avoid
 
-- risk of out-of-memory operations or the like.
-- Subgroup-based search
function p.search_by_int_limit_within_equave(int_limit, equave, tenney_height)
-- Can support higher int limits than int-limit search can, provided the sub-
local int_limit = int_limit or DEFAULT_INT_LIMIT
-- group is sufficiently small (about 10 members)
local equave = equave or rat.new(2,1) -- Defualt equave is 2/1.
function p.search_by_subgroup(subgroup, int_limit, equave)
local tenney_height = tenney_height or 1/0 -- Defualt tenney height is infinity.
local subgroup = subgroup or { 2, 3, 7, 11 }
local int_limit = int_limit or 50
int_limit = math.max(0, math.min(INT_LIMIT_MAX, int_limit))
local equave = equave or {2,1}
local possible_values = p.find_products(subgroup, int_limit)
local init_ratios = {{1,1}, {2,1}}
local ratios = p.find_ratios_using_values(possible_values, equave)
local search_func = p.int_limit_mediant_search
local search_args = { ["equave"] = equave, ["int_limit"] = int_limit, ["tenney_height"] = tenney_height }
local ratios = med.find_only_mediants_by_search_func(init_ratios, search_func, search_args)
-- Convert to ratios that Module:Rational can work with
-- Convert to ratios that Module:Rational can work with
Line 115: Line 113:
end
end


-- Helper function
-- Int limit search function, with equave and tenney height cutoffs.
-- Finds all eligible values for the numerator and denominator
-- If nil is passed in for the tenney height, it will defualt to infinity.
function p.find_products(factors, max_product)
-- To be passed into mediant-search function, as part of int-limit-search
local factors = factors or { 2, 3, 7, 11 }
-- function call.
local max_product = max_product or 50
function p.int_limit_mediant_search(mediant_data, search_args)
local mediant  = mediant_data["mediant"]
local ratio_1  = mediant_data["ratio_1"]
local equave        = search_args["equave"]
local int_limit    = search_args["int_limit"]
local tenney_height = search_args["tenney_height"]
local equave_as_float = rat.as_float(equave)
local rat_1_as_float = ratio_1[1] / ratio_1[2]
local mediant_th = math.log(mediant[1] * mediant[2]) / math.log(2)
-- Perform a breadth-first-search.
return math.max(mediant[1], mediant[2]) <= int_limit and rat_1_as_float < equave_as_float and mediant_th <= tenney_height
-- Starting with the number 1 at the root node of a (simulated) search tree,
end
-- explore the possible products (child nodes) of multiplying that number
 
-- with exactly one each of the given factors. Any products that are less
--------------------------------------------------------------------------------
-- than the max product are added to the search tree, and the search
------------------------ SUBGROUP-BASED SEARCH FUNCTION ------------------------
-- recurses for each child node by finding its children produced by multi-
--------------------------------------------------------------------------------
-- plying by one of each factor. The search on any one branch stops if the
 
-- resulting products exceed that of the max product.
-- Int-limit-based search; finds ratios between 1/1 and an equave, within a sub-
-- Products are stored as a jagged array, where the index of each inner
-- group. An int limit is passed in to limit the size of output, since subgroups
-- array is the search depth. Duplicate products are excluded.
-- are infinite sets. An optional tenney height can be passed in to further
-- NOTE: the search starts with the number 1 for this operation to work. To
-- limit output.
-- make sense of this, this operation can be thought of a BFS for powers
-- Unlike int limit search, subgroup search can allow for very high int limits,
-- pi raising factors fi (f1^p1 * f2^p2 * ... * fn^pn), so 1 is where each
-- as long as the subgroup is reasonably small and has reasonably small terms.
-- factor fi is raised by zero, thus BFS increases the exponents by 1.
-- 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, int_limit, equave, tenney_height)
local subgroup = subgroup or { 2, 3, 7 }
local int_limit = int_limit or 50
local equave = equave or rat.new(2,1) -- Defualt equave is 2/1.
local tenney_height = tenney_height or 1/0 -- Defualt tenney height is infinity.
-- Be absolutely sure the subgroup's members are sorted!
table.sort(subgroup)
-- Find all possible products given the factors in the subgroup.
-- These will be used to find all possible ratios.
local products = {{1}}
local products = {{1}}
local new_products_found = true
local new_products_found = true
while new_products_found do
while new_products_found do
local new_products = {}
local new_products = {}
for i = 1, #factors do
for i = 1, #subgroup do
for j = 1, #products[#products] do
for j = 1, #products[#products] do
local new_product = products[#products][j] * factors[i]
local new_product = products[#products][j] * subgroup[i]
if new_product <= max_product then
if new_product <= int_limit then
local product_already_added = false
local product_already_added = false
for k = 1, #new_products do
for k = 1, #new_products do
Line 170: Line 189:
products = consolidated_products
products = consolidated_products
table.sort(products)
table.sort(products)
return products
end


-- Finds all potential ratios whose numerator and denominator is from the list
-- Using the products produced earlier, combine them to make all possible
-- of given values, and whose value, as a float, is between 1 and a given
-- ratios from 1/1 to the equave. Ratios with non-coprime numerator and
-- equave.
-- denominator, or exceed the tenney height, are omitted.
function p.find_ratios_using_values(values, equave)
local values = values or p.find_products()
local equave = equave or { 2, 1 }
local equave_as_float = equave[1]/equave[2]
local ratios = {}
local ratios = {}
for i = 1, #values do
local equave_as_float = rat.as_float(equave)
local denominator = values[i]
for i = 1, #products do
for j = i, #values do
local denominator = products[i]
local numerator = values[j]
for j = i, #products do
local numerator = products[j]
local gcd = utils._gcd(numerator, denominator)
local gcd = utils._gcd(numerator, denominator)
if gcd == 1 then
if gcd == 1 then
local within_equave = numerator / denominator <= equave_as_float
local within_equave = numerator / denominator <= equave_as_float
if within_equave then
local within_tenney_height = math.log(numerator * denominator) / math.log(2) <= tenney_height
if within_equave and within_tenney_height then
table.insert(ratios, {numerator, denominator})
table.insert(ratios, {numerator, denominator})
else
else
Line 198: Line 210:
end
end
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
end
Line 203: Line 220:
end
end


--------------------------------------------------------------------------------
---------------------- PRIME-LIMIT-BASED SEARCH FUNCTION -----------------------
--------------------------------------------------------------------------------
-- Int-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, int_limit, equave, tenney_height)
local prime_limit = 3
local int_limit = int_limit or 1000
local equave = equave or rat.new(2,1) -- Defualt equave is 2/1.
local tenney_height = tenney_height or 1/0 -- Defualt tenney height is infinity.
-- 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, int_limit, equave, tenney_height)
end


--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
Line 371: Line 423:
end
end


-- Convert a table of tables into a table of text
-- Convert a table of ratios (tables, as defined by rational module) into a
-- line of text, with options for delimiters.
function p.ratios_as_texts(ratios, add_links, delimiter)
function p.ratios_as_texts(ratios, add_links, delimiter)
local add_links = add_links == true
local add_links = add_links == true
Line 384: Line 437:
end
end


-- Int limit search function, with an equave cutoff.
function p.tester()
-- Ratios are added by int limit as normally except when the mediant straddles
-- the equave. If the equave is strictly less than the first ratio, add the
-- mediant formed by it and ratio 2. This minimizes the number of ratios larger
-- than the equave being added, but requires some post-search cleanup.
function p.int_limit_equave_cutoff_search(mediant_data, search_args)
local mediant  = mediant_data["mediant"]
local ratio_1  = mediant_data["ratio_1"]
local equave    = search_args["equave"]
local int_limit = search_args["int_limit"]
local equave_as_float = equave[1] / equave[2]
local rat_1_as_float = ratio_1[1] / ratio_1[2]
return math.max(mediant[1], mediant[2]) <= int_limit and rat_1_as_float < equave_as_float
end


function p.tester()
local ratios = p.search_by_prime_limit_within_equave()
local params = p.parse_search_params("Int Limit: 30; Prime Limit: 17")
--ratios = p.search_by_params(params)
--ratios = p.sort_by_closeness_to_cent_values(ratios, {0, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 1100, 1200}, 15)
--return p.ratios_as_texts(ratios)
--local ratios = p.search_by_int_limit(250)
--return p.ratios_as_text(ratios) .. " " .. #ratios
-- Using these params with the naive search algorithm (iterating through
-- every number from to to the int limit and checking whether its factors
-- are present in the subgroup) takes several seconds to return only 1563
-- results using these params: factors 2, 3, 7, 11; max product: 10 million.
local factors = { 2, 3 }
local max_product = 5000
--return p.ratios_as_text(p.search_by_subgroup(factors, max_product, {3,1}))
--return p.find_products(factors, max_product)
local search_args = {}
search_args["equave"] = {5,4}
search_args["int_limit"] = 30
local ratios = med.find_only_mediants_by_search_func({{1,1},{1,0}}, p.int_limit_equave_cutoff_search, search_args)
--local ratios = p.search_by_int_limit(30)
-- 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
return p.ratios_as_text(ratios)
return p.ratios_as_text(ratios)
Retrieved from "https://en.xen.wiki/w/Module:JI_ratios"