Module:Limits: Difference between revisions
Consistency limits optimisation |
Further optimisations & a bugfix for non-EDOs |
||
| Line 3: | Line 3: | ||
-- compute all positive ratios n/m with n and m <= q modulo powers of equave | -- compute all positive ratios n/m with n and m <= q modulo powers of equave | ||
function p.limit_modulo_equave(q, equave) | -- previous: already computed ratios for q-1 | ||
function p.limit_modulo_equave(q, equave, previous) | |||
equave = equave or 2 | equave = equave or 2 | ||
local ratios = {} | local ratios = {} | ||
if previous then | |||
for | for n = 1, q do | ||
local a = rat.new(n, | local a = rat.new(n, q) | ||
a = rat.modulo_mul(a, equave) | a = rat.modulo_mul(a, equave) | ||
local key = rat.as_ratio(a) | local a_key = rat.as_ratio(a) | ||
local b = rat.new(q, n) | |||
b = rat.modulo_mul(b, equave) | |||
local b_key = rat.as_ratio(b) | |||
if previous[a_key] == nil then | |||
ratios[a_key] = a | |||
end | |||
if previous[b_key] == nil then | |||
ratios[b_key] = b | |||
end | |||
end | |||
else | |||
for n = 1, q do | |||
for m = 1, q do | |||
local a = rat.new(n, m) | |||
a = rat.modulo_mul(a, equave) | |||
local key = rat.as_ratio(a) | |||
ratios[key] = a | |||
end | |||
end | end | ||
end | end | ||
| Line 20: | Line 40: | ||
-- approx(a*b) = approx(a) + approx(b) forall a, b: a, b, ab in ratios | -- approx(a*b) = approx(a) + approx(b) forall a, b: a, b, ab in ratios | ||
-- `distinct`: whether distinct ratios are required to be mapped to distinct approximations | -- `distinct`: whether distinct ratios are required to be mapped to distinct approximations | ||
function p.additively_consistent(equave, size, ratios, distinct) | -- previous: already computed ratios for q-1 | ||
function p.additively_consistent(equave, size, ratios, distinct, previous) | |||
distinct = distinct or false | distinct = distinct or false | ||
previous = previous or {} | |||
local function approximate(a) | local function approximate(a) | ||
return math.floor(size * math.log(rat.as_float(a)) / math.log(rat.as_float(equave)) + 0.5) | return math.floor(size * math.log(rat.as_float(a)) / math.log(rat.as_float(equave)) + 0.5) | ||
| Line 27: | Line 49: | ||
if distinct then | if distinct then | ||
local approx_set = {} | local approx_set = {} | ||
for a_key, a in pairs(previous) do | |||
local a_approx = approximate(a) % size | |||
if approx_set[a_approx] then | |||
return false | |||
end | |||
approx_set[a_approx] = true | |||
end | |||
for a_key, a in pairs(ratios) do | for a_key, a in pairs(ratios) do | ||
local a_approx = approximate(a) % size | local a_approx = approximate(a) % size | ||
| Line 34: | Line 63: | ||
approx_set[a_approx] = true | approx_set[a_approx] = true | ||
end | end | ||
end | |||
local previous_ordered = {} | |||
for a_key, a in pairs(previous) do | |||
table.insert(previous_ordered, a) | |||
end | end | ||
local ratios_ordered = {} | local ratios_ordered = {} | ||
| Line 41: | Line 74: | ||
for i, a in ipairs(ratios_ordered) do | for i, a in ipairs(ratios_ordered) do | ||
local a_approx = approximate(a) | local a_approx = approximate(a) | ||
for j, b in ipairs(previous_ordered) do | |||
local b_approx = approximate(b) | |||
local c = rat.mul(a, b) | |||
local c_approx = approximate(c) | |||
c = rat.modulo_mul(c, equave) | |||
local c_key = rat.as_ratio(c) | |||
if previous[c_key] or ratios[c_key] then | |||
if c_approx ~= a_approx + b_approx then | |||
mw.log('a = ' .. rat.as_ratio(a) .. '; b = ' .. rat.as_ratio(b) .. '; ab = ' .. c_key) | |||
mw.log(a_approx .. ' + ' .. b_approx .. ' != ' .. c_approx) | |||
return false | |||
end | |||
end | |||
end | |||
for j, b in ipairs(ratios_ordered) do | for j, b in ipairs(ratios_ordered) do | ||
if i <= j then | if i <= j then | ||
| Line 50: | Line 99: | ||
c = rat.modulo_mul(c, equave) | c = rat.modulo_mul(c, equave) | ||
local c_key = rat.as_ratio(c) | local c_key = rat.as_ratio(c) | ||
if ratios[c_key] then | if previous[c_key] or ratios[c_key] then | ||
if c_approx ~= a_approx + b_approx then | if c_approx ~= a_approx + b_approx then | ||
mw.log('a = ' .. rat.as_ratio(a) .. '; b = ' .. rat.as_ratio(b) .. '; ab = ' .. c_key) | |||
mw.log(a_approx .. ' + ' .. b_approx .. ' != ' .. c_approx) | |||
return false | return false | ||
end | end | ||
| Line 70: | Line 121: | ||
local n = 1 | local n = 1 | ||
local last_n = 1 | local last_n = 1 | ||
local previous = {} | |||
while true do | while true do | ||
local ratios = p.limit_modulo_equave(n, equave, previous) | |||
n | for key, ratio in pairs(ratios) do | ||
mw.log('step ' .. n .. ': ' .. key) | |||
end | |||
local consistent = p.additively_consistent(equave, size, ratios, distinct) | if next(ratios) ~= nil then | ||
local consistent = p.additively_consistent(equave, size, ratios, distinct, previous) | |||
if not consistent then | if not consistent then | ||
return last_n | return last_n | ||
end | |||
for key, ratio in pairs(ratios) do | |||
previous[key] = ratio | |||
end | end | ||
last_n = n | last_n = n | ||
end | end | ||
n = n + 1 | |||
if n > max_n then | if n > max_n then | ||
return nil | return nil | ||