Module:SB tree
Jump to navigation
Jump to search
Documentation for this module may be created at Module:SB tree/doc
local p = {}
-- 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 adjacent ratios 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; this is how many generations
-- after the initial ratios to produce successive layers of the tree, so depth 4 is 5 layers
-- Edge extend iteratively finds the mediants of the first two and last two ratios; default is 0
-- Transpiled from python code to lua with aid of ChatGPT
function p.sb_tree_ratios(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, if default params are used
local tree = {start_ratio, stop_ratio}
-- Iteratively find the mediants of every adjacent pair of ratios
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 (the mediants)
-- For loop needs to make one fewer iteration since the current ratio and its mediant with the next
-- are added as a pair; the last ratio in the array is added separately after the loop
for j = 1, #tree - 1 do
local ratio_1 = tree[j]
local ratio_2 = tree[j+1]
local mediant = {ratio_1[1] + ratio_2[1], ratio_1[2] + ratio_2[2]}
-- Add to new tree
table.insert(new_tree, ratio_1)
table.insert(new_tree, mediant)
end
-- Add last ratio, then replace tree with new tree with mediants
table.insert(new_tree, tree[#tree])
tree = new_tree
end
-- Edge-extend code
-- Mediants of the last two ratios are added, as are the mediants of the first two ratios
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 mediant_last = {last_ratio_2[1] + last_ratio_1[1], last_ratio_2[2] + last_ratio_1[2]}
tree[#tree] = mediant_last
table.insert(tree, last_ratio_2)
local first_ratio_1 = tree[1] -- First ratio
local first_ratio_2 = tree[2] -- Second first ratio
local mediant_first = {first_ratio_2[1] + first_ratio_1[1], first_ratio_2[2] + first_ratio_1[2]}
tree[1] = mediant_first
table.insert(tree, 1, first_ratio_1)
end
return tree
end
-- Function that calculates the depths of each ratio in the Stern-Brocot tree
-- This is nearly identical to the sb_tree_ratios function, except only the depth
-- and edge extend are needed
-- Transpiled from python code to lua with aid of ChatGPT
function p.sb_tree_depths(depth, edge_extend)
-- Default parameter values
depths = depths or 4
edge_extend = edge_extend or 0
-- Initial depths of the initial ratios are 1 for lua programming purposes
local tree = {1, 1}
-- Calculate depths for successive layers in the tree
for i = 1, depth do
local new_tree = {}
-- Depths of the first and mediant of first and second ratio are added in pairs
-- The last ratio is added after the for loop itself
for j = 1, #tree - 1 do
local depth_1 = tree[j]
local depth_new = i + 1
table.insert(new_tree, depth_1)
table.insert(new_tree, depth_new)
end
table.insert(new_tree, tree[#tree])
tree = new_tree
end
-- For extending the edges of the tree
-- When edge-extending, the first and last depths must always be 1
for i = 1, edge_extend do
-- Extend at end
tree[#tree] = tree[#tree - 1] + 1
table.insert(tree, 1)
-- Extend at front
tree[1] = tree[2] + 1
table.insert(tree, 1, 1)
end
return tree
end
-- Helper function that parses ratios entered as "p/q", returning it as an array { p, q }
function p.parse_ratio(ratio_unparsed)
local ratio = {}
for number in string.gmatch(ratio_unparsed, '([^/]+)') do
table.insert(ratio, number)
end
return ratio
end
-- Test function that produces the ratios of the SB tree as a multi-column table, using different arguments
-- To try this out, add the following text (not as a lua comment):
-- {{#invoke:SB_tree|sb_table}}
function p.sb_table(frame)
-- Call the sb function
-- Start/stop ratios are the same, depth is deeper, and edge-extend is allowed
local depth = frame.args['Depth'] or 4
local edge_extend = frame.args['Edge Extend'] or 2
local start_ratio_unparsed = frame.args['Start Ratio'] or "1/1"
local stop_ratio_unparsed = frame.args['Stop Ratio'] or "1/0"
local stagger_ratios = (frame.args['Stagger Ratios'] and string.lower(frame.args['Stagger Ratios'])) == "true" and true or false
-- Parse ratios
local start_ratio = p.parse_ratio(start_ratio_unparsed)
local stop_ratio = p.parse_ratio(stop_ratio_unparsed)
-- Get the ratios and depths
local sb_tree_depths = p.sb_tree_depths(depth, edge_extend)
local sb_tree_ratios = p.sb_tree_ratios(depth, start_ratio, stop_ratio, edge_extend)
-- Create the table
result = '{| class="wikitable"\n'
result = result .. "|+\n"
result = result .. "|-\n"
-- Create the header cell
if stagger_ratios then
result = result .. '! colspan="' .. depth + edge_extend + 1 .. " | Ratios\n"
else
result = result .. "! Ratios\n"
end
-- Create the individual rows
for i = 1, #sb_tree_ratios
do
result = result .. "|-\n"
-- Create the cells for each row
if stagger_ratios then
-- Stagger ratios
for j = 1, depth + edge_extend + 1 do
if j == sb_tree_depths[i] then
result = result .. "|" .. sb_tree_ratios[i][1] .. "/" .. sb_tree_ratios[i][2] .. "\n"
else
result = result .. "|\n"
end
end
else
-- Don't stagger ratios
result = result .. "|" .. sb_tree_ratios[i][1] .. "/" .. sb_tree_ratios[i][2] .. "\n"
end
end
result = result .. "|}"
return result
end
return p