Module:SB tree: Difference between revisions
No edit summary |
No edit summary |
||
| Line 4: | Line 4: | ||
-- Function that constructs a sequence of ratios according to the Stern-Brocot tree | -- 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 | -- 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 | -- Mediants are found between adjacent ratio iteratively | ||
-- Start and stop ratio may be any two ratios, but the default values are 1/1 and 1/0 | -- 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 | -- Depth may be specified to be any value, but the default is 4 | ||
-- Edge extend iteratively finds the mediants of the first two and last two ratios; default is 0 | -- Edge extend iteratively finds the mediants of the first two and last two ratios; default is 0 | ||
-- Transpiled from python to lua with aid of ChatGPT | -- Transpiled from python code to lua with aid of ChatGPT | ||
function p.sb_tree(depth, start_ratio, stop_ratio, edge_extend) | function p.sb_tree(depth, start_ratio, stop_ratio, edge_extend) | ||
-- Default parameter values | -- Default parameter values | ||
| Line 16: | Line 16: | ||
edge_extend = edge_extend or 0 | edge_extend = edge_extend or 0 | ||
-- Initial tree are the ratios 1/1 and 1/0 | -- Initial tree are the ratios 1/1 and 1/0, if default params are used | ||
local tree = {start_ratio, stop_ratio} | local tree = {start_ratio, stop_ratio} | ||
-- Iteratively find the mediants of every adjacent pair of ratios | |||
for i = 1, depth do | for i = 1, depth do | ||
-- Make another tree that's empty | -- Make another tree that's empty | ||
local new_tree = {} | local new_tree = {} | ||
-- Make a new tree that has entries in between existing ratios | -- 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; the last ratio in the array is added separately after the loop | |||
for j = 1, #tree - 1 do | for j = 1, #tree - 1 do | ||
local ratio_1 = tree[j] | local ratio_1 = tree[j] | ||
local ratio_2 = tree[j+1] | local ratio_2 = tree[j+1] | ||
local | 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, ratio_1) | ||
table.insert(new_tree, | table.insert(new_tree, mediant) | ||
end | end | ||
-- Add last ratio, then replace tree with new tree with mediants | |||
table.insert(new_tree, tree[#tree]) | table.insert(new_tree, tree[#tree]) | ||
tree = new_tree | tree = new_tree | ||
end | 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 | for i = 1, edge_extend do | ||
local last_ratio_1 = tree[#tree - 1] -- Second last ratio | local last_ratio_1 = tree[#tree - 1] -- Second last ratio | ||
local last_ratio_2 = tree[#tree] -- Last ratio | local last_ratio_2 = tree[#tree] -- Last ratio | ||
local | local mediant_last = {last_ratio_2[1] + last_ratio_1[1], last_ratio_2[2] + last_ratio_1[2]} | ||
tree[#tree] = | tree[#tree] = mediant_last | ||
table.insert(tree, last_ratio_2) | table.insert(tree, last_ratio_2) | ||
local first_ratio_1 = tree[1] -- First ratio | local first_ratio_1 = tree[1] -- First ratio | ||
local first_ratio_2 = tree[2] -- Second first ratio | local first_ratio_2 = tree[2] -- Second first ratio | ||
local | local mediant_first = {first_ratio_2[1] + first_ratio_1[1], first_ratio_2[2] + first_ratio_1[2]} | ||
tree[1] = | tree[1] = mediant_first | ||
table.insert(tree, 1, first_ratio_1) | table.insert(tree, 1, first_ratio_1) | ||
end | end | ||
| Line 58: | Line 65: | ||
-- {{#invoke:SB_tree|sb_table}} | -- {{#invoke:SB_tree|sb_table}} | ||
function p.sb_table(frame) | function p.sb_table(frame) | ||
-- Call the sb function | |||
-- Start/stop ratios are the same, depth is deeper, and edge-extend is allowed | |||
local sb_tree_ratios = p.sb_tree(5, {1, 1}, {1, 0}, 3) | |||
-- Create the table | |||
result = '{| class="wikitable"\n' | result = '{| class="wikitable"\n' | ||
result = result .. "|+\n" | result = result .. "|+\n" | ||
result = result .. "|-\n" | result = result .. "|-\n" | ||
result = result .. "! Ratio\n" | result = result .. "! Ratio\n" | ||
for i = 1, #sb_tree_ratios | for i = 1, #sb_tree_ratios | ||