Module:Limits

Module documentation[view] [edit] [history] [purge]

This module depends on the following other modules: Module: ET Module: Rational

Todo: add documentation

---

local rat = require('Module:Rational')
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

-- 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(equave, size, ratios, distinct, previous)
	distinct = distinct or false
	previous = previous or {}
	local function approximate(a)
		return math.floor(size * math.log(rat.as_float(a)) / math.log(rat.as_float(equave)) + 0.5)
	end
	if distinct then
		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
			local a_approx = approximate(a) % size
			if approx_set[a_approx] then
				return false
			end
			approx_set[a_approx] = true
		end
	end
	local previous_ordered = {}
	for a_key, a in pairs(previous) do
		table.insert(previous_ordered, a)
	end
	local ratios_ordered = {}
	for a_key, a in pairs(ratios) do
		table.insert(ratios_ordered, a)
	end
	for i, a in ipairs(ratios_ordered) do
		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
			if i <= j then
				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
		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
function p.consistency_limit(size, equave, distinct, max_n)
	if size == 0 then
		-- the answer is known already
		return '∞'
	end
	max_n = max_n or 1/0
	equave = equave or 2
	distinct = distinct or false
	local n = 1
	local last_n = 1
	local previous = {}
	while true do
		local ratios = p.limit_modulo_equave(n, equave, previous)
		for key, ratio in pairs(ratios) do
			mw.log('step ' .. n .. ': ' .. key)
		end
		if next(ratios) ~= nil then
			local consistent = p.additively_consistent(equave, size, ratios, distinct, previous)
			if not consistent then
				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