Xenharmonic Wiki

Module:JI ratios: Difference between revisions

← Older editNewer edit →
Ganaram inukshuk (talk | contribs)
autopatrolled, emailconfirmed
6,211 edits
Reworked products search as a BFS algorithm
Ganaram inukshuk (talk | contribs)
autopatrolled, emailconfirmed
6,211 edits
Moar cleanup; refined subgroup-search code to implement bfs
Line 96: Line 96:
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------


-- WARNING: searching by nonprime subgroup may lead to redundant ratios being
-- Subgroup-based search
-- added, so checking for duplicates is necessary, but not implemented yet.
-- Can support higher int limits than int-limit search can, provided the sub-
-- Rational subgroup isn't supported yet either.
-- group is sufficiently small (about 10 members)
-- Prime limits should be converted to subgroup (eg, 7-limit -> 2.3.5.7) so as
-- to avoid brute-force searching incurred by first searching by int limit.
-- WARNING: code is inefficient when the subgroup has lots of values.
-- Needs a new algorithm.
function p.search_by_subgroup(subgroup, int_limit, equave)
function p.search_by_subgroup(subgroup, int_limit, equave)
local subgroup = subgroup or { 2, 3, 7, 11 }
local subgroup = subgroup or { 2, 3, 7, 11 }
local int_limit = int_limit or 50
local int_limit = int_limit or 50
local equave = equave or rat.new(2,1)
local equave = equave or {2,1}
local equave_as_float = rat.as_float(equave)
local possible_values = p.find_products(subgroup, int_limit)
local ratios = p.find_ratios_using_values(possible_values, equave)
-- For each factor in the subgroup, calculate the largest exponent (power)
-- that factor can be raised to that is just less than the int limit.
-- Use this to create a running vector of powers.
local max_powers = {}
local curr_powers = {} -- Running vector of powers
for i = 1, #subgroup do
local curr_max_multiplier = math.floor(int_limit/subgroup[i])
local max_power = math.log(int_limit) / math.log(subgroup[i])
table.insert(max_powers, math.floor(max_power))
table.insert(curr_powers, -max_powers[i])
end
-- Increment current powers one by one, and use those powers to create the
-- required ratios.
local ratios = {}
while curr_powers[#curr_powers] <= max_powers[#max_powers] do
-- Calculate new ratio
local new_ratio = { 1, 1 }
for i = 1, #curr_powers do
if curr_powers[i] >= 1 then
new_ratio[1] = new_ratio[1] * math.pow(subgroup[i], curr_powers[i])
else
new_ratio[2] = new_ratio[2] * math.pow(subgroup[i], -curr_powers[i])
end
end
-- Check whether new ratio as a float is within the range of 1 and the
-- equave as a float, and whether its num and den are within the int
-- limit. If so, add it to the running list of ratios.
local curr_product = new_ratio[1] / new_ratio[2]
if new_ratio[1] <= int_limit and new_ratio[2] <= int_limit and curr_product >= 1 and curr_product <= equave_as_float then
table.insert(ratios, new_ratio)
end
-- Increment powers
curr_powers[1] = curr_powers[1] + 1
for i = 1, #curr_powers - 1 do
if curr_powers[i] > max_powers[i] then
curr_powers[i] = -max_powers[i]
curr_powers[i+1] = curr_powers[i+1] + 1
end
end
end
-- Convert to ratios that Module:Rational can work with
-- Convert to ratios that Module:Rational can work with
Line 163: Line 115:
end
end


-- Go back to having a find-products function
-- Helper function
-- Finds all eligible values for the numerator and denominator
function p.find_products(factors, max_product)
function p.find_products(factors, max_product)
local factors = factors or { 2, 3, 5, 7, 11, 13, 17, 19 }
local factors = factors or { 2, 3, 7, 11 }
local max_product = max_product or 10000
local max_product = max_product or 50
-- Perform a breadth-first-search
-- Perform a breadth-first-search.
-- Starting with the number 1 at the root node of a (simulated) search tree,
-- Starting with the number 1 at the root node of a (simulated) search tree,
-- explore the possible products (child nodes) of multiplying that number
-- explore the possible products (child nodes) of multiplying that number
Line 176: Line 129:
-- plying by one of each factor. The search on any one branch stops if the
-- plying by one of each factor. The search on any one branch stops if the
-- resulting products exceed that of the max product.
-- resulting products exceed that of the max product.
-- Products are stored as a jagged array, where the index of each inner
-- array is the search depth. Duplicate products are excluded.
-- NOTE: the search starts with the number 1 for this operation to work. To
-- make sense of this, this operation can be thought of a BFS for powers
-- pi raising factors fi (f1^p1 * f2^p2 * ... * fn^pn), so 1 is where each
-- factor fi is raised by zero, thus BFS increases the exponents by 1.
local products = {{1}}
local products = {{1}}
local new_products_found = true
local new_products_found = true
Line 184: Line 143:
local new_product = products[#products][j] * factors[i]
local new_product = products[#products][j] * factors[i]
if new_product <= max_product then
if new_product <= max_product then
-- Check whether the product already exists; if not, add it
-- to the table of new products.
local product_already_added = false
local product_already_added = false
for k = 1, #new_products do
for k = 1, #new_products do
Line 216: Line 173:
return products
return products
end
end
-- Finds all potential ratios whose numerator and denominator is from the list
-- of given values, and whose value, as a float, is between 1 and a given
-- equave.
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 = {}
for i = 1, #values do
local denominator = values[i]
for j = i, #values do
local numerator = values[j]
local gcd = utils._gcd(numerator, denominator)
if gcd == 1 then
local within_equave = numerator / denominator <= equave_as_float
if within_equave then
table.insert(ratios, {numerator, denominator})
else
break
end
end
end
end
return ratios
end


--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
Line 411: Line 398:
-- are present in the subgroup) takes several seconds to return only 1563
-- 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.
-- results using these params: factors 2, 3, 7, 11; max product: 10 million.
local factors = { 2, 15, 17, 22 }
local factors = { 2, 3 }
local max_product = 100
local max_product = 5000
return p.ratios_as_text(p.search_by_subgroup(factors, max_product))
return p.ratios_as_text(p.search_by_subgroup(factors, max_product, {3,1}))
--return p.find_products(factors, max_product)
end
end


return p
return p
Retrieved from "https://en.xen.wiki/w/Module:JI_ratios"