Xenharmonic Wiki

Module:JI ratios: Difference between revisions

← Older editNewer edit →
Ganaram inukshuk (talk | contribs)
autopatrolled, emailconfirmed
6,211 edits
save running changes to subgroup search
Ganaram inukshuk (talk | contribs)
autopatrolled, emailconfirmed
6,211 edits
Finalized main algorithm for subgroup search
Line 96: Line 96:
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------


-- Requires helper functions
-- WARNING: searching by nonprime subgroup may lead to redundant ratios being
function p.search_by_subgroup(subgroup, int_limit, max_cents)
-- added, so checking for duplicates is necessary, but not implemented yet.
-- Rational subgroup isn't supported yet either.
-- 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.
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 max_cents = max_cents or 1200
local equave = equave or rat.new(2,1)
local equave_as_float = rat.as_float(equave)
end
-- 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.
-- Helper function
-- Use this to create a running vector of powers.
-- 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 max_powers = {}
local curr_powers = {}
local curr_powers = {} -- Running vector of powers
for i = 1, #factors do
for i = 1, #subgroup do
local curr_factor = factors[i]
local curr_max_multiplier = math.floor(int_limit/subgroup[i])
local curr_max_multiplier = math.floor(max_product/curr_factor)
local max_power = math.log(int_limit) / math.log(subgroup[i])
local max_power = math.log(max_product) / math.log(curr_factor)
table.insert(max_powers, math.floor(max_power))
table.insert(max_powers, math.ceil(max_power))
table.insert(curr_powers, -max_powers[i])
table.insert(curr_powers, -max_powers[i])
end
end
-- Increment current powers one by one, and add to a table containing
-- Increment current powers one by one, and use those powers to create the
-- vectors of powers; this table also contains vectors with negative powers
-- required ratios.
local powers = {}
local ratios = {}
while curr_powers[#curr_powers] < max_powers[#max_powers] do
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
curr_powers[1] = curr_powers[1] + 1
for i = 1, #curr_powers - 1 do
for i = 1, #curr_powers - 1 do
if curr_powers[i] >= max_powers[i] then
if curr_powers[i] > max_powers[i] then
curr_powers[i] = -max_powers[i] + 1
curr_powers[i] = -max_powers[i]
curr_powers[i+1] = curr_powers[i+1] + 1
curr_powers[i+1] = curr_powers[i+1] + 1
end
end
end
end
local new_powers = {}
for i = 1, #curr_powers do
table.insert(new_powers, curr_powers[i])
end
table.insert(powers, new_powers)
end
end
table.sort(products)
-- Convert to ratios that Module:Rational can work with
for i = 1, #ratios do
return powers
ratios[i] = rat.new(ratios[i][1], ratios[i][2])
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
end
return test_number == 1
return ratios
end
end


Line 387: Line 351:
--return p.ratios_as_text(ratios) .. " " .. #ratios
--return p.ratios_as_text(ratios) .. " " .. #ratios
-- Using these params with the naive search algorithm takes several seconds
-- Using these params with the naive search algorithm (iterating through
-- to return only 1563 results: factors 2, 3, 7, 11; max product: 10 million
-- every number from to to the int limit and checking whether its factors
local factors = { 2, 3, 7, 11 }
-- are present in the subgroup) takes several seconds to return only 1563
local max_product = 20
-- results using these params: factors 2, 3, 7, 11; max product: 10 million.
local factors = { 2, 15, 17, 22 }
local max_product = 100
return p.find_products(factors, max_product)
return p.ratios_as_text(p.search_by_subgroup(factors, max_product))
end
end


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