Xenharmonic Wiki

MOS substitution: Difference between revisions

← Older edit
VisualWikitext
Inthar (talk | contribs)
autopatrolled, emailconfirmed
15,668 edits
No edit summary
Inthar (talk | contribs)
autopatrolled, emailconfirmed
15,668 edits
 
(15 intermediate revisions by the same user not shown)
Line 1: Line 1:
'''MOS substitution''' is a procedure for obtaining a ternary (3 step sizes) scale from two [[MOS]] patterns. It consists of substituting the step pattern of one MOS pattern (called the filling MOS), scale step for scale step, for all occurrences of a chosen step size of another MOS pattern (called the template MOS). Unlike MV3 scales, a MOS substitution scale may have any combination of step sizes.
'''MOS substitution''' is a procedure for obtaining a ternary (3 step sizes) scale from two [[MOS]] patterns. It consists of substituting the step pattern of one MOS pattern (called the ''filling MOS''), scale step for scale step, for all occurrences of a chosen step size of another MOS pattern (called the ''template MOS''). Unlike MV3 scales, a MOS substitution scale may have any combination of step sizes.


[[Aberrismic theory]] uses MOS substitution. In fact, groundfault reports having come up with a similar concept but not following up on it.
[[Aberrismic theory]] uses MOS substitution. In fact, groundfault reports having come up with a similar concept but not following up on it.
Line 43: Line 43:


== Formal definition ==
== Formal definition ==
Suppose ''a'', ''b'', and ''c'' are positive integers. Suppose that the noncircular binary word ''t''('''x''', '''X''') is the brightest mode of the MOS scale word with step signature ''a'''''x'''(''b'' + ''c'')'''X''' when treating '''x''' as larger than '''X''', and that the noncircular binary word ''f''('''y''', '''z''') is one rotation of the MOS scale word with step signature ''b'''''y'''''c'''''z'''. Then the result of replacing the ''i''th occurrence of '''X''' in ''t'' replaced with the ''i''th letter of ''f'' for 0 &le; ''i'' < |''f''|, treated as a circular word, is said to be a ''MOS substitution scale word'' with ''template MOS'' ''a'''''x'''(''b'' + ''c'')'''X''' and ''filling MOS'' ''b'''''y'''''c'''''z''', or in shorthand, a "subst&nbsp;''a'''''x'''(''b'''''y'''''c'''''z''')".
A ternary scale word ''w''('''x'''<sub>1</sub>, '''x'''<sub>2</sub>, '''x'''<sub>3</sub>) is a ''MOS substitution'' scale word if there exists a permutation <math>\pi \in S_3</math> such that the following holds:
* identifying '''x'''<sub>π(1)</sub> and '''x'''<sub>π(2)</sub> results in a MOS (called the ''template MOS'') and
* deleting all instances of '''x'''<sub>π(3)</sub> (called the ''slot letter'') results in a MOS (called the ''filling MOS'').


== Original derivation ==
== Original derivation ==
Line 52: Line 54:
In the original aberrismic-informed context, say that <math>d = (a, c) > 1.</math> Consider the MOS word <math>(a + c)\mathbf{X}b\mathbf{m}</math>, which we call the ''template MOS''. Since the "most even" arrangement (in the sense of [[distributional evenness]]) of <math>a</math>-many <math>\mathbf{L}</math> steps and <math>c</math>-many <math>\mathbf{s}</math> steps is the MOS <math>a\mathbf{L}b\mathbf{s}</math> (which will in general be a non-[[primitive]] MOS), this method prescribes following the latter MOS, called the ''filling MOS'', to fill in the <math>\mathbf{X}</math> steps. Fixing a choice of which <math>\mathbf{X}</math> in the MOS <math>(a + c)\mathbf{X}b\mathbf{m}</math> you start from, we can choose one of <math>(a+c)/d</math> modes of <math>a \mathbf{L} c \mathbf{s}.</math> If <math>a = c</math>, we obtain a balanced (thus MV3) ternary scale; when in addition <math>b</math> is odd, the scale is also SV3 and chiral, and we recover the two chiralities from the two modes of <math>a\mathbf{L}a\mathbf{s}</math>. Of course, one may do this using template MOS <math>a\mathbf{L}(b + c)\mathbf{X}</math> and the <math>(b, c)</math>-multiperiod filling MOS <math>b\mathbf{m} c\mathbf{s}</math> instead. This article denotes the resulting scale <math>\mathsf{MOS\_subst}(a, b, c; \mathbf{y}, \mathbf{z}; k):</math>  
In the original aberrismic-informed context, say that <math>d = (a, c) > 1.</math> Consider the MOS word <math>(a + c)\mathbf{X}b\mathbf{m}</math>, which we call the ''template MOS''. Since the "most even" arrangement (in the sense of [[distributional evenness]]) of <math>a</math>-many <math>\mathbf{L}</math> steps and <math>c</math>-many <math>\mathbf{s}</math> steps is the MOS <math>a\mathbf{L}b\mathbf{s}</math> (which will in general be a non-[[primitive]] MOS), this method prescribes following the latter MOS, called the ''filling MOS'', to fill in the <math>\mathbf{X}</math> steps. Fixing a choice of which <math>\mathbf{X}</math> in the MOS <math>(a + c)\mathbf{X}b\mathbf{m}</math> you start from, we can choose one of <math>(a+c)/d</math> modes of <math>a \mathbf{L} c \mathbf{s}.</math> If <math>a = c</math>, we obtain a balanced (thus MV3) ternary scale; when in addition <math>b</math> is odd, the scale is also SV3 and chiral, and we recover the two chiralities from the two modes of <math>a\mathbf{L}a\mathbf{s}</math>. Of course, one may do this using template MOS <math>a\mathbf{L}(b + c)\mathbf{X}</math> and the <math>(b, c)</math>-multiperiod filling MOS <math>b\mathbf{m} c\mathbf{s}</math> instead. This article denotes the resulting scale <math>\mathsf{MOS\_subst}(a, b, c; \mathbf{y}, \mathbf{z}; k):</math>  


<math>\displaystyle{ \mathsf{MOS\_subst}(a, b, c; \mathbf{y}, \mathbf{z}; k) := \mathsf{subst}\left( a\mathbf{w}(b + c)\mathbf{X}(0) , \mathbf{X}, b\mathbf{y}c\mathbf{z}(k) \right) }</math>
<math>\displaystyle{\mathsf{subst}\left( a\mathbf{w}(b + c)\mathbf{X}(0) , \mathbf{X}, b\mathbf{y}c\mathbf{z}(k) \right) }</math>
 
For brevity, this should usually be written:
 
<math>\mathsf{subst} \ a\mathbf{x}\left(b\mathbf{y}\,c\mathbf{z} \ k\,\vert\,b+c-1-k\right),</math>
 
using [[simplified UDP]] for the filling MOS.


Here <math>\mathbf{z}</math> is the new step size inserted, <math>\mathbf{y}</math> is the step size in the starting MOS identified with <math>\mathbf{z}</math> by the template MOS, and <math>k</math> is the brightness of the mode of the filling MOS used (<math>k = 0</math> corresponds to the darkest mode; the conventional understanding of "brightness" makes sense as <math>\mathbf{L}</math> (resp. <math>\mathbf{m}</math>) > <math>\mathbf{s}</math>).
Here <math>\mathbf{z}</math> is the new step size inserted, <math>\mathbf{y}</math> is the step size in the starting MOS identified with <math>\mathbf{z}</math> by the template MOS, and <math>k</math> is the brightness of the mode of the filling MOS used (<math>k = 0</math> corresponds to the darkest mode; the conventional understanding of "brightness" makes sense as <math>\mathbf{L}</math> (resp. <math>\mathbf{m}</math>) > <math>\mathbf{s}</math>).
Line 179: Line 175:


In particular, all [[monotone-MOS scale]]s (i.e. such that the results of {{nowrap|'''L''' {{=}} '''m''' | '''m''' {{=}} '''s'''}}, and {{nowrap|'''s''' {{=}} '''0'''}} temperings are MOSes) arise from MOS substitution in this way.
In particular, all [[monotone-MOS scale]]s (i.e. such that the results of {{nowrap|'''L''' {{=}} '''m''' | '''m''' {{=}} '''s'''}}, and {{nowrap|'''s''' {{=}} '''0'''}} temperings are MOSes) arise from MOS substitution in this way.
=== If a ternary scale satisfies all three possible MOS-substitution types, then it is pairwise-MOS and deletion-MOS ===
This fact is immediate. (See [[pairwise-MOS]] and [[deletion-MOS]].)
Corollary (by [[Ternary scale theorems]]): Such a scale is [[Fraenkel word|Fraenkel]], [[odd-regular]], or [[even-regular]].


=== If the template MOS is primitive, MOS substitution yields binary well-formed generator sequences ===
=== If the template MOS is primitive, MOS substitution yields binary well-formed generator sequences ===
Line 193: Line 193:
* the imperfect generator of the filling MOS corresponds to looping back to ''C''<sub>1</sub> but on the next note of ''C''<sub>1</sub>, so it and the ''q'' &minus; 1 notes thereafter are advanced by 1 note from any predecessor notes in the chains.
* the imperfect generator of the filling MOS corresponds to looping back to ''C''<sub>1</sub> but on the next note of ''C''<sub>1</sub>, so it and the ''q'' &minus; 1 notes thereafter are advanced by 1 note from any predecessor notes in the chains.


Hence these particular MOS substitution scales satisfy a property that we call ''parallelogram substring''. An '''e'''-equivalent scale is a ''parallelogram substring'' if there exist integers ''m'' > 0, ''n'' > 0, 0 &le; ''a'' < ''n'', 0 &le; ''b'' < ''n'', a vector '''a''', and two linearly independent vectors '''v''' and '''w''' such that the set of notes in the scale as a subset of the lattice of '''e'''-equivalent pitches is  
Hence these particular MOS substitution scales satisfy a property that we call ''[[parallelogram substring scale|parallelogram substring]]''. An '''e'''-equivalent scale is a ''parallelogram substring'' if there exist integers ''m'' > 0, ''n'' > 0, 0 &le; ''a'' < ''n'', 0 &le; ''b'' < ''n'', a vector '''a''', and two linearly independent vectors '''v''' and '''w''' such that the set of notes in the scale as a subset of the lattice of '''e'''-equivalent pitches is  


<math>
<math>
Line 217: Line 217:


Case 2: Neither of ''k'' and {{nowrap|''k'' + 1}} equals ({{nowrap|''b'' + ''c''}}). Here, if '''Y''' occurs ''j'' or {{nowrap|''j'' + 1}} times in a window of size ''k'', then '''Y''' occurs {{nowrap|''j'' + 1}} or {{nowrap|''j'' + 2}} times in a window of size {{nowrap|''k'' + 2}}.
Case 2: Neither of ''k'' and {{nowrap|''k'' + 1}} equals ({{nowrap|''b'' + ''c''}}). Here, if '''Y''' occurs ''j'' or {{nowrap|''j'' + 1}} times in a window of size ''k'', then '''Y''' occurs {{nowrap|''j'' + 1}} or {{nowrap|''j'' + 2}} times in a window of size {{nowrap|''k'' + 2}}.
=== Ternary parallelogram scales are MOS substitution scales ===
:''Main article: [[Ternary parallelogram scales are MOS substitution]]''


== MOS substitution scales and RTT ==
== MOS substitution scales and RTT ==
Line 242: Line 245:
     scale = subst_step_sizes(word, {"X": sizeX, "Y": sizeY, "Z": sizeZ})
     scale = subst_step_sizes(word, {"X": sizeX, "Y": sizeY, "Z": sizeZ})
     return scale
     return scale
</syntaxhighlight>
== Code ==
Rust code for generating MOS substitution scales:
<syntaxhighlight lang="rs">
pub type Letter = usize;
/// Return gcd(a, b) and the Bezout coefficients: (g, x, y).
pub fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
    let (mut r, mut old_r) = (a, b);
    let (mut s, mut old_s) = (1, 0);
    let (mut t, mut old_t) = (0, 1);
    while r != 0 {
        let quotient = old_r / r;
        (old_r, r) = (r, old_r - quotient * r);
        (old_s, s) = (s, old_s - quotient * s);
        (old_t, t) = (t, old_t - quotient * t);
    }
    (old_r, old_s, old_t)
}
/// Return the gcd.
pub fn gcd(a: i64, b: i64) -> i64 {
    extended_gcd(a, b).0
}
// Compute `n % abs(m)`
fn modulo(n: i64, m: i64) -> i64 {
    ((n % m) + m) % m
}
/// Return *x* such that (*xa*) mod *b* = 1.
pub fn modinv(a: i64, b: i64) -> Result<i64, String> {
    let (gcd, x, _) = extended_gcd(a, b);
    if gcd == 1 {
        Ok(modulo(x, b))
    } else {
        Err("Non-coprime generator error".to_string())
    }
}
/// The rotation required from the current word to the
/// lexicographically least mode of a word.
/// Booth's algorithm requires at most 3*n* comparisons and *n* storage locations where *n* is the input word's length.
/// See Booth, K. S. (1980). Lexicographically least circular substrings.
/// Information Processing Letters, 10(4-5), 240–242. doi:10.1016/0020-0190(80)90149-0
pub fn booth(scale: &[Letter]) -> usize {
    let n = scale.len();
    // `f` is the failure function of the least rotation; `usize::MAX` is used as a null value.
    // null indicates that the failure function does not point backwards in the string.
    // `usize::MAX` will behave the same way as -1 does, assuming wrapping unsigned addition
    let mut f = vec![usize::MAX; 2 * n];
    let mut k: usize = 0;
    // `j` loops over `scale` twice.
    for j in 1..2 * n {
        let mut i = f[j - k - 1];
        while i != usize::MAX && scale[j % n] != scale[k.wrapping_add(i).wrapping_add(1) % n] {
            // (1) If the jth letter is less than s[(k + i + 1) % n] then change k to j - i - 1,
            // in effect left-shifting the failure function and the input string.
            // This appropriately compensates for the new, shorter least substring.
            if scale[j % n] < scale[k.wrapping_add(i).wrapping_add(1) % n] {
                k = j.wrapping_sub(i).wrapping_sub(1);
            }
            i = f[i];
        }
        if i == usize::MAX && scale[j % n] != scale[k.wrapping_add(i).wrapping_add(1) % n] {
            // See note (1) above.
            if scale[j % n] < scale[k.wrapping_add(i).wrapping_add(1) % n] {
                k = j;
            }
            f[j - k] = usize::MAX;
        } else {
            f[j - k] = i.wrapping_add(1);
        }
        // The induction hypothesis is that
        // at this point `f[0..j - k]` is the failure function of `s[k..(k+j)%n]`,
        // and `k` is the lexicographically least subword of the letters scanned so far.
    }
    k
}
/// Rotate an array. Returns a Vec.
pub fn rotate<T: std::clone::Clone>(slice: &[T], degree: usize) -> Vec<T> {
    let degree = degree % slice.len();
    if degree == 0 {
        slice.to_vec()
    } else {
        [&slice[degree..slice.len()], &slice[0..degree]].concat()
    }
}
/// The lexicographically least mode of a word (where the letters are in their usual order).
pub fn least_mode(scale: &[Letter]) -> Vec<Letter> {
    rotate(scale, booth(scale))
}
/// Delete all instances of one letter.
pub fn delete(scale: &[Letter], letter: Letter) -> Vec<Letter> {
    scale.iter().filter(|x| **x != letter).cloned().collect()
}
/// Letterwise substitution for scale words.
///
/// Note: This function does not fail even if the number of times `x` occurs in `template`
/// does not divide `filler.len()`.
pub fn subst(template: &[Letter], x: Letter, filler: &[Letter]) -> Vec<Letter> {
    let mut ret = vec![];
    let mut i: usize = 0;
    if !filler.is_empty() {
        for &letter in template {
            if letter == x {
                // Use the currently pointed-to letter of `filler` in place of `x`.
                ret.push(filler[i % filler.len()]);
                // Only update `i` when an `x` is replaced.
                i += 1;
            } else {
                ret.push(letter);
            }
        }
    } else {
        // If `filler` is empty, we return `template` but with all `x`s removed.
        return delete(template, x);
    }
    ret
}
/// Return the darkest mode of the MOS axby and the dark generator, using the Bresenham line algorithm.
/// We chose the darkest mode rather than the brightest because this is the mode with brightness == 0.
pub fn darkest_mos_mode_and_gen_bresenham(a: usize, b: usize) -> (Vec<Letter>, Vec<usize>) {
    let d = gcd(a as i64, b as i64) as usize;
    if d == 1 {
        let count_gen_steps = modinv(a as i64, a as i64 + b as i64)
                .expect("The dark generator is a (|L|⁻¹ mod |scale|)-step, since stacking it |L| times results in the s step (mod period).")
                as usize;
        let mut result_scale: Vec<usize> = vec![];
        // Start from the origin (0, 0)
        let (mut current_x, mut current_y) = (0usize, 0usize);
        while (current_x, current_y) != (a, b) {
            if a * (current_y) >= b * (current_x + 1) {
                // If going east (making a (1, 0) step) doesn't lead to going below the line y == b/a*x,
                current_x += 1; // append the x step and reflect the change in the plane vector.
                result_scale.push(0);
            } else {
                // Else, make a (0, 1) step.
                current_y += 1;
                result_scale.push(1);
            }
        }
        // Get the dark generator. We know how many steps and that this will give the perfect generator, not the
        // augmented one, since we just got the darkest mode.
        let result_gen = {
            let mut gen = vec![0, 0, 0];
            for i in 0..count_gen_steps {
                if result_scale[i] < 3 {
                    gen[result_scale[i]] += 1;
                }
            }
            gen
        };
        (result_scale, result_gen)
    } else {
        let (prim_mos, gen) = darkest_mos_mode_and_gen_bresenham(a / d, b / d);
        (prim_mos.repeat(d), gen)
    }
}
/// Return the collection of all MOS substitution scales `subst n0 x (n1 y n2 z)`
/// where the template MOS is assumed to have step signature `n0*0 (n1 + n2)*X` (`X` is the slot letter)
/// and the filling MOS has step signature `n1*1 n2*2`.
fn mos_substitution_scales_one_perm(n0: usize, n1: usize, n2: usize) -> Vec<Vec<Letter>> {
    let (template, _) = darkest_mos_mode_and_gen_bresenham(n0, n1 + n2);
    let (filler, gener) = darkest_mos_mode_and_gen_bresenham(n1, n2);
    let filler = filler.into_iter().map(|x| x + 1).collect::<Vec<_>>();
    let gener_size = gener.len();
    (0..(n1 + n2))
        .map(|i| {
            subst(
                &template,
                1usize,
                &rotate(&filler, (i * gener_size) % filler.len()),
            )
        })
        .collect()
}
/// The set of all [MOS substitution](https://en.xen.wiki/w/User:Inthar/MOS_substitution) ternary scales.
pub fn mos_substitution_scales(sig: &[usize]) -> Vec<Vec<Letter>> {
    let (n0, n1, n2) = (sig[0], sig[1], sig[2]);
    // Only need 3 permutations of (0, 1, 2) for the MOS substitution patterns n0*_ (n1*_ n2*_)
    let redundant_list = [
        // n0L (n1m n2s)
        mos_substitution_scales_one_perm(n0, n1, n2),
        // n1m (n0L n2s)
        mos_substitution_scales_one_perm(n1, n2, n0)
            .into_iter()
            .map(|scale| scale.into_iter().map(|x| (x + 1) % 3).collect())
            .collect(),
        // n2s (n0L n1m)
        mos_substitution_scales_one_perm(n2, n0, n1)
            .into_iter()
            .map(|scale| {
                scale
                    .into_iter()
                    .map(|x| if x == 0 { 2 } else { (x - 1) % 3 })
                    .collect()
            })
            .collect(),
    ]
    .concat();
    // Canonicalize every scale and remove duplicates
    let mut canonicalized_list: Vec<_> = redundant_list
        .into_iter()
        .map(|scale| least_mode(&scale))
        .collect();
    canonicalized_list.sort();
    canonicalized_list.dedup();
    canonicalized_list
}
fn main() {
    for scale in mos_substitution_scales(&[5, 2, 4]) {
        println!("{:?}", scale);
    }
    /*
        [0, 0, 1, 2, 0, 2, 0, 1, 2, 0, 2]
        [0, 0, 2, 0, 1, 2, 0, 0, 2, 1, 2]
        [0, 0, 2, 0, 1, 2, 0, 2, 0, 1, 2]
        [0, 0, 2, 0, 2, 1, 0, 2, 0, 1, 2]
        [0, 0, 2, 0, 2, 1, 0, 2, 0, 2, 1]
        [0, 0, 2, 1, 0, 2, 0, 0, 2, 1, 2]
        [0, 0, 2, 1, 0, 2, 0, 1, 2, 0, 2]
        [0, 0, 2, 1, 0, 2, 0, 2, 0, 1, 2]
        [0, 0, 2, 1, 0, 2, 0, 2, 1, 0, 2]
        [0, 1, 0, 2, 0, 2, 0, 1, 0, 2, 2]
    */
}
</syntaxhighlight>
</syntaxhighlight>


Retrieved from "https://en.xen.wiki/w/MOS_substitution"