Module:Limits
Jump to navigation
Jump to search
local rat = require("Module:Rational")
local ET = require("Module:ET")
local p = {}
-- compute all positive ratios n/m with n and m <= q modulo powers of equave
-- previous: already computed ratios for q-1
function p.limit_modulo_equave(q, equave, previous)
equave = equave or 2
local ratios = {}
if previous then
for n = 1, q do
local a = rat.new(n, q)
a = rat.modulo_mul(a, equave)
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
return ratios
end
-- compute q-integer limit
-- if a function `norm` and a number `max_norm` are provided, the output will be additionally restricted
function p.integer_limit(q, norm, max_norm)
local check_norm = type(norm) == "function" and type(max_norm) == "number"
local ratios = {}
for n = 1, q do
for m = 1, q do
local a = rat.new(n, m)
if not check_norm or norm(a) <= max_norm then
local key = rat.as_ratio(a)
ratios[key] = a
end
end
end
return ratios
end
-- check additive consistency for a set of ratios (modulo powers of equave):
-- 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
-- `previous`: already computed ratios for the previous iteraton
function p.additively_consistent(et, ratios, distinct, previous)
distinct = distinct or false
previous = previous or {}
if distinct then
local approx_set = {}
for a_key, a in pairs(previous) do
local a_approx = ET.approximate(et, rat.as_float(a)) % et.size
if approx_set[a_approx] then
if not rat.eq(rat.modulo_mul(rat.div(a, approx_set[a_approx]), et.equave), 1) then
mw.log(a_key .. " -> " .. a_approx .. ": conflict!")
return false
end
end
approx_set[a_approx] = a
mw.log(a_key .. " -> " .. a_approx)
end
for a_key, a in pairs(ratios) do
local a_approx = ET.approximate(et, rat.as_float(a)) % et.size
if approx_set[a_approx] then
if not rat.eq(rat.modulo_mul(rat.div(a, approx_set[a_approx]), et.equave), 1) then
mw.log(a_key .. " -> " .. a_approx .. ": conflict!")
return false
end
end
approx_set[a_approx] = a
mw.log(a_key .. " -> " .. a_approx)
end
end
if type(distinct) == "number" then
return true
end
local previous_ordered = {}
for _, a in pairs(previous) do
table.insert(previous_ordered, a)
end
local ratios_ordered = {}
for _, a in pairs(ratios) do
table.insert(ratios_ordered, a)
end
for i, a in ipairs(ratios_ordered) do
local a_approx = ET.approximate(et, rat.as_float(a))
for _, b in ipairs(previous_ordered) do
local b_approx = ET.approximate(et, rat.as_float(b))
local c = rat.mul(a, b)
local c_approx = ET.approximate(et, rat.as_float(c))
c = rat.modulo_mul(c, et.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
if i <= j then
local b_approx = ET.approximate(et, rat.as_float(b))
local c = rat.mul(a, b)
local c_approx = ET.approximate(et, rat.as_float(c))
c = rat.modulo_mul(c, et.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
end
end
return true
end
-- find additive consistency limit
-- returns nil when at least `max_n`
-- `distinct`: whether distinct ratios are required to be mapped to distinct approximations
-- - if an integer, it is the regular consistency limit already known
function p.consistency_limit(et, distinct, max_n)
if et.size == 0 then
-- the answer is known already
return "∞"
end
max_n = max_n or 1 / 0
distinct = distinct or false
local n = 1
local last_n = 1
local previous = {}
while true do
if type(distinct) == "number" and n > distinct then
return last_n
end
local ratios = p.limit_modulo_equave(n, et.equave, previous)
for key, _ in pairs(ratios) do
mw.log("step " .. n .. ": " .. key)
end
if next(ratios) ~= nil then
local consistent = p.additively_consistent(et, ratios, distinct, previous)
if not consistent then
mw.log("Not consistent at step " .. n .. ", returning " .. last_n)
return last_n
end
for key, ratio in pairs(ratios) do
previous[key] = ratio
end
last_n = n
end
n = n + 1
if n > max_n then
return nil
end
end
end
return p