Module:SB tree

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

This module should not be invoked directly; use its corresponding template instead: Template:SB tree.

This module is used to create a Stern–Brocot tree, given a pair of starting ratios and a depth.

Introspection summary for Module:SB tree
Functions provided (2) Line Function Params 11 sb_tree (depth, start_ratio, stop_ratio, edge_extend) 59 sb_table (invokable) (frame)	Lua modules required (1) Variable Module Functions used rat Module:Rational dependency not used

No function descriptions were provided. The Lua code may have further information.

---

local p = {}
local rat = require('Module:Rational')

-- Function that constructs a sequence of ratios according to the Stern-Brocot tree
-- Ratios are entered as arrays, such as {1, 1} for the ratio 1/1 and {1, 0} for the ratio 1/0
-- Mediants are found between each ratio iteratively
-- Start and stop ratio may be any two ratios, but the default values are 1/1 and 1/0
-- Depth may be specified to be any value, but the default is 4
-- Edge extend recursively finds the mediants of the first two and last two ratios; default is 0
-- Transpiled from python to lua with aid of ChatGPT; may need testing to make sure code works
function p.sb_tree(depth, start_ratio, stop_ratio, edge_extend)
	-- Default parameter values
	depth = depth or 4
	start_ratio = start_ratio or {1, 1}
	stop_ratio = stop_ratio or {1, 0}
	edge_extend = edge_extend or 0
	
    -- Initial tree are the ratios 1/1 and 1/0
    local tree = {start_ratio, stop_ratio}

    for i = 1, depth do
        -- Make another tree that's empty
        local new_tree = {}

        -- Make a new tree that has entries in between existing ratios
        for j = 1, #tree - 1 do
            local ratio_1 = tree[j]
            local ratio_2 = tree[j+1]
            local new_ratio = {ratio_1[1] + ratio_2[1], ratio_1[2] + ratio_2[2]}

            table.insert(new_tree, ratio_1)
            table.insert(new_tree, new_ratio)
        end

        table.insert(new_tree, tree[#tree])
        tree = new_tree
    end

    for i = 1, edge_extend do
        local last_ratio_1 = tree[#tree - 1]     -- Second last ratio
        local last_ratio_2 = tree[#tree]         -- Last ratio
        local new_ratio_in_between = {last_ratio_2[1] + last_ratio_1[1], last_ratio_2[2] + last_ratio_1[2]}
        tree[#tree] = new_ratio_in_between
        table.insert(tree, last_ratio_2)

        local first_ratio_1 = tree[1]            -- First ratio
        local first_ratio_2 = tree[2]            -- Second first ratio
        local new_ratio_in_between_2 = {first_ratio_2[1] + first_ratio_1[1], first_ratio_2[2] + first_ratio_1[2]}
        tree[1] = new_ratio_in_between_2
        table.insert(tree, 1, first_ratio_1)
    end

    return tree
end

-- Test function that produces the ratios of the SB tree as a one-column table, using default parameters
-- To try this out, add the following text (not as a lua comment):
-- {{#invoke:SB_tree|sb_table}}
function p.sb_table(frame)
	result = '{| class="wikitable"\n'
	result = result .. "|+\n"
	result = result .. "|-\n"
	result = result .. "! Ratio\n"
	
	local sb_tree_ratios = p.sb_tree(4, {1, 1}, {1, 0}, 0)
	
	for i = 1, #sb_tree_ratios
	do
		result = result .. "|-\n"
		result = result .. "|" .. sb_tree_ratios[i][1] .. "/" ..  sb_tree_ratios[i][2] .. "\n"
	end
	
	result = result .. "|}"
	
	return result
end

return p