|
|
| Line 7: |
Line 7: |
|
| |
|
| -- TODO: | | -- TODO: |
| | -- Add back in tenney height and complement filtering to subgroup search. |
|
| |
|
| -- 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 68: |
Line 69: |
| ["Int Limit"] = int_limit | | ["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 | | end |
|
| |
|
| Line 230: |
Line 208: |
| -- Sort | | -- Sort |
| table.sort(ratios, rat.lt) | | table.sort(ratios, rat.lt) |
| | |
| | -- TODO: add filtering by tenney height and complements |
|
| |
|
| return ratios | | return ratios |
| end | | end |
|
| |
|
| -- BFS search, implemented as a helper function | | -- Helper function for subgroup search; implementation of BFS |
| function p.multiply_ratios_using_bfs(init_ratio, subgroup, int_limit) | | function p.multiply_ratios_using_bfs(init_ratio, subgroup, int_limit) |
| local ratios = { init_ratio } | | local ratios = { init_ratio } |
| Line 257: |
Line 237: |
| end | | end |
| return ratios | | 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 | | end |
|
| |
|