local rat = require("Module:Rational")
local utils = require("Module:Utils")
local tip = require("Module:Template input parse")
local m = require("Module:Mediants")
p = {}
-- TODO:
-- Adopt mediants module
-- 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:
-- - The absolute minimum for ratio search int limit, which limits the maximum
-- size of the numerator and denominator.
-- - If subgroup is present, ratios are searched by subgroup within an int
-- limit. Subgroup takes precedence over prime limit, as subgroup is
-- (typically) a subset of prime limit, so prime limit is ignored. (Nonprime
-- subgroups take precedence over prime subgroups.)
-- - If prime limit is present, ratios are searched by prime limit within an int
-- limit.
-- 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.
-- INT_LIMIT_MAX is hardcoded to limit the size of output.
-- 400 -> ~24000 ratios
-- 300 -> ~14000 ratios
-- 250 -> ~9500 ratios
-- 200 -> ~6000 ratios
-- 150 -> ~3400 ratios
-- 128 -> ~2500 ratios
-- 100 -> ~1500 ratios
local INT_LIMIT_MAX = 200
local DEFAULT_INT_LIMIT = 50
--------------------------------------------------------------------------------
----------------------- INT-LIMIT-BASED SEARCH FUNCTION ------------------------
--------------------------------------------------------------------------------
-- Find JI ratios up to an integer limit within the octave by finding mediants.
-- 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)
local max_cents = max_cents or 1200
local integer_limit = integer_limit or DEFAULT_INT_LIMIT
integer_limit = math.max(0, math.min(INT_LIMIT_MAX, integer_limit))
local init_ratios = {{1,1}, {2,1}}
local func = m.int_limit_search
local args = integer_limit
local ratios = m.find_mediants_by_search_func(init_ratios, func, args)
-- If the max cents is greater than the octave, duplicate all existing
-- ratios and raise them by the required number of octaves.
if max_cents > 1200 then
local new_ratios = {}
local num_octaves_up = math.ceil(max_cents / 1200)
for j = 1, num_octaves_up do
for i = 2, #ratios do
local num = ratios[i][1] * math.pow(2, j)
local den = ratios[i][2]
local gcd = utils._gcd(num, den)
num = num / gcd
den = den / gcd
if math.max(num, den) <= integer_limit then
table.insert(new_ratios, {num, den})
end
end
end
for i = 1, #new_ratios do
table.insert(ratios, new_ratios[i])
end
end
-- Remove any ratios that exceed the max cents
-- 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 ratios
end
--------------------------------------------------------------------------------
------------------------ SUBGROUP-BASED SEARCH FUNCTION ------------------------
--------------------------------------------------------------------------------
-- Requires helper functions
function p.search_by_subgroup(subgroup, int_limit, max_cents)
local subgroup = subgroup or { 2, 3, 7, 11 }
local int_limit = int_limit or 50
local max_cents = max_cents or 1200
end
-- Helper function
-- Given a set of factors and a max product, find all values up to the max
-- product that is divisible by at least one of those primes.
-- Factors are either prime or coprime, thus handling nonprime subgroups.
function p.find_products(factors, max_product)
local factors = factors or { 2, 3, 7, 11 }
local max_product = max_product or 100
local products = { }
-- A naive approach is to iterate through all numbers 2..max_product and in-
-- sert them in a table if it consists of at least one of the given factors.
-- Using these numbers, make every possible pair from these numbers to
-- produce a table of ratios within the desired subgroup, given the factors
-- represent a subgroup. This is super inefficient as just the process of
-- producing products involves checking numbers that are produced by factors
-- outside the set of desired factors, which is the vast majority of num-
-- bers. A more targeted approach is to do the following:
-- - For each factor fi, calculate the largest power pi of that factor that
-- is just less than the max product. Keep track of these powers as a
-- vector of powers.
-- - For factors f1, f2, ... fn, and powers p1, p2, ... pn, represent the
-- potential powers as sets {0,1,...,p1}, {0,1,...,p2}, ..., {0,1,...,pn}.
-- The set of all possible vectors of powers is the cartesian product of
-- these sets.
-- - These vectors encode prime factorizations, and to reduce the quantity
-- of products, only permit products that are less than that of the max
-- product. Additionally, since these encode prime factorizations, the use
-- of negative exponents produces ratios for free!
-- - NOTE ABOUT VECTORS OF POWERS: these vectors may be thought of as monzos
-- but without the potential sparseness. EG, whereas [2 0 0 1 1> is a
-- shorthand for 308, in the context of the 2.7.11 subgroup, the lack of
-- 3's and 5's makes the inclusion of these zeroes wasteful; hence the
-- factors are denoted as a vector {2,7,11} and the powers {2,1,1}.
-- Another way to think of these vectors is as a number where each
-- position is a different base; thus, producing every possible vector is
-- as simple as counting up, which is how these vectors are produced in
-- code.
local max_powers = {}
local curr_powers = {}
for i = 1, #factors do
local curr_factor = factors[i]
local curr_max_multiplier = math.floor(max_product/curr_factor)
local max_power = math.log(max_product) / math.log(curr_factor)
table.insert(max_powers, math.floor(max_power))
table.insert(curr_powers, 0)
end
-- Increment current powers one by one
while curr_powers[#curr_powers] < max_powers[#max_powers] do
curr_powers[1] = curr_powers[1] + 1
for i = 1, #factors - 1 do
if curr_powers[i] > max_powers[i] then
curr_powers[i] = 0
curr_powers[i+1] = curr_powers[i+1] + 1
end
end
local curr_product = 1
for i = 1, #curr_powers do
curr_product = curr_product * math.pow(factors[i], curr_powers[i])
end
if curr_product <= max_product then
table.insert(products, curr_product)
end
end
table.sort(products)
return max_powers
end
-- Check whether a number is composed of the following factors.
function p.is_divisible_by_factors(number, factors)
local test_number = number
for i = 1, #factors do
local is_divisible = true
while test_number ~= 0 and is_divisible do
is_divisible = false
if test_number % factors[i] == 0 then
test_number = test_number / factors[i]
is_divisible = true
end
end
end
return test_number == 1
end
--------------------------------------------------------------------------------
------------------------- PARAM-BASED SEARCH FUNCTIONS -------------------------
--------------------------------------------------------------------------------
-- Search for ratios based on params passed in. Each param is its own
-- function call. Params must be parsed first.
function p.search_by_params(params, max_cents)
local max_cents = max_cents or 1200
-- First get ratios up to an int limit. If no int limit was passed in, it
-- will default to the hardcoded default value.
local ratios = {}
if params["Int Limit"] ~= nil then
ratios = p.search_by_int_limit(params["Int Limit"], max_cents)
end
if params["Prime Limit"] ~= nil then
ratios = p.filter_by_prime_limit(ratios, params["Prime Limit"])
end
if params["Tenney Height"] ~= nil then
ratios = p.filter_by_tenney_height(ratios, params["Tenney Height"])
end
return ratios
end
-- Parse search params.
function p.parse_search_params(search_params)
local parsed = tip.parse_kv_pairs(search_params)
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
return parsed
end
function p.search_param_footnotes(search_params)
local result = "Not all notable ratios may be shown, and other interpretations are possible."
if search_params["Prime Limit"] ~= nil then
result = string.format("Ratios shown are within the [[%s-limit]]. %s", search_params["Prime Limit"], result)
elseif search_params["Int Limit"] ~= nil then
result = string.format("Ratios shown are %s-[[integer-limit|integer limit]]. %s", search_params["Int Limit"], result)
end
return result
end
--------------------------------------------------------------------------------
---------------------------- RATIO FILTER FUNCTIONS ----------------------------
--------------------------------------------------------------------------------
-- Filter ratios by Tenney height.
function p.filter_by_tenney_height(ratios, tenney_height)
local tenney_height = tenney_height or 10
local filtered_ratios = {}
for i = 1, #ratios do
local curr_tenney_height = rat.tenney_height(ratios[i])
if curr_tenney_height <= tenney_height then
table.insert(filtered_ratios, ratios[i])
end
end
return filtered_ratios
end
-- Filter ratios by prime limit.
function p.filter_by_prime_limit(ratios, prime_limit)
local prime_limit = prime_limit or 41
local filtered_ratios = {}
for i = 1, #ratios do
local curr_max_prime = rat.max_prime(ratios[i])
if curr_max_prime <= prime_limit then
table.insert(filtered_ratios, ratios[i])
end
end
return filtered_ratios
end
-- Filter ratios by (prime) subgroup. EG: 2.3.5.7
function p.filter_by_subgroup(ratios, subgroup)
end
-- Filter ratios by rational/nonprime subgroup. EG, 2.7/2.11/2, or 2.5.7.9
-- Does not support irrational subgroups.
function p.filter_by_nonprime_subgroup(ratios, subgroup)
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_text(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 table of tables into a table of text
function p.ratios_as_texts(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_text(ratios[i], add_links, delimiter)
table.insert(texts, text)
end
return texts
end
function p.tester()
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 takes several seconds
-- to return only 1563 results: factors 2, 3, 7, 11; max product: 10 million
local factors = { 2, 3, 7, 11 }
local max_product = 20
return p.find_products(factors, max_product)
end
return p
.svg){kind=icon}
