Mathematics of MOS: Difference between revisions
Wikispaces>genewardsmith **Imported revision 322232920 - Original comment: ** |
Wikispaces>genewardsmith **Imported revision 322238568 - Original comment: ** |
||
| Line 1: | Line 1: | ||
<h2>IMPORTED REVISION FROM WIKISPACES</h2> | <h2>IMPORTED REVISION FROM WIKISPACES</h2> | ||
This is an imported revision from Wikispaces. The revision metadata is included below for reference:<br> | This is an imported revision from Wikispaces. The revision metadata is included below for reference:<br> | ||
: This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-04-18 14: | : This revision was by author [[User:genewardsmith|genewardsmith]] and made on <tt>2012-04-18 14:36:44 UTC</tt>.<br> | ||
: The original revision id was <tt> | : The original revision id was <tt>322238568</tt>.<br> | ||
: The revision comment was: <tt></tt><br> | : The revision comment was: <tt></tt><br> | ||
The revision contents are below, presented both in the original Wikispaces Wikitext format, and in HTML exactly as Wikispaces rendered it.<br> | The revision contents are below, presented both in the original Wikispaces Wikitext format, and in HTML exactly as Wikispaces rendered it.<br> | ||
| Line 58: | Line 58: | ||
If the period is assumed to be 2^(1/n) for some integer n, we can give instead the total number of large and small steps in the octave, instead of just the period, and this is commonly done. In this case, GCD(L, s) gives the number of periods in an octave. | If the period is assumed to be 2^(1/n) for some integer n, we can give instead the total number of large and small steps in the octave, instead of just the period, and this is commonly done. In this case, GCD(L, s) gives the number of periods in an octave. | ||
==Classification via the ? function== | |||
Yet another way of classifying MOS is via [[http://en.wikipedia.org/wiki/Minkowski%27s_question_mark_function|Minkowski's ? function]]. Here ?(x) is a continuous increasing function from the real numbers to the real numbers which has some peculiar properties, one being that it sends rational numbers to [[http://en.wikipedia.org/wiki/Dyadic_rational|dyadic rationals]]. Hence if q is a rational number 0 < q < 1 in use in the mediant system of classifying MOS, r = ?(q) = A/2^n will be a dyadic rational number which can also be used. Note that the ? function is invertible, and it and its inverse function, the Box function, have code given for them in the algorithms section at the bottom of the article. | Yet another way of classifying MOS is via [[http://en.wikipedia.org/wiki/Minkowski%27s_question_mark_function|Minkowski's ? function]]. Here ?(x) is a continuous increasing function from the real numbers to the real numbers which has some peculiar properties, one being that it sends rational numbers to [[http://en.wikipedia.org/wiki/Dyadic_rational|dyadic rationals]]. Hence if q is a rational number 0 < q < 1 in use in the mediant system of classifying MOS, r = ?(q) = A/2^n will be a dyadic rational number which can also be used. Note that the ? function is invertible, and it and its inverse function, the Box function, have code given for them in the algorithms section at the bottom of the article. | ||
The integer n in the denominator of r (with A assumed to be odd) is the order (or n+1 is, according to some sources) of q in the [[http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree|Stern-Brocot tree]]. The two neighboring numbers of order n+1, which define the range of propriety, can also be expressed in terms of the ? and Box functions as Box(r - 2^(-n-1) and Box(r + 2^(-n-1)). If r represents a MOS, the range of possible values for a generator of the MOS will be Box(r) < g < Box(r + 2^(-n)), and the proper generators will be Box(r) < g < Box(r + 2^(-n-1)). So, for example, the MOS denoted by 3/2048 will be between Box(3/2048) and Box(4/2048), which means that 2/21 < g < 1/10, and will be proper if 2/21 < g < 3/31. Hence 7/72, a generator for miracle temperament, will define a MOS but it will not be proper since 7/72 > 3/31 = Box(3/2048 + 1/4096)). | The integer n in the denominator of r (with A assumed to be odd) is the order (or n+1 is, according to some sources) of q in the [[http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree|Stern-Brocot tree]]. The two neighboring numbers of order n+1, which define the range of propriety, can also be expressed in terms of the ? and Box functions as Box(r - 2^(-n-1) and Box(r + 2^(-n-1)). If r represents a MOS, the range of possible values for a generator of the MOS will be Box(r) < g < Box(r + 2^(-n)), and the proper generators will be Box(r) < g < Box(r + 2^(-n-1)). So, for example, the MOS denoted by 3/2048 will be between Box(3/2048) and Box(4/2048), which means that 2/21 < g < 1/10, and will be proper if 2/21 < g < 3/31. Hence 7/72, a generator for miracle temperament, will define a MOS but it will not be proper since 7/72 > 3/31 = Box(3/2048 + 1/4096)). | ||
==MOS in equal temperaments== | |||
In an equal temperament, all intervals are integer multiples of a smallest unit. If the equal temperament is N-EDO and the period is an octave, the sizes of the large and small steps will be p/N and q/N, with p > q. We then have L(p/N) + s(q/N) = 1, which on multiplying through by N gives us | |||
Lp + sq = N. | |||
which is a linear diophantine equation. Solving this by standard methods, and requiring L and s to be positive, gives us the [L, s] pair for the MOS. If some other quantity of equal steps gives the period, we may make the appropriate adjustment. | |||
==Blackwood R constant== | |||
In the context of the "recognizable diatonic" scales deriving from the Farey pair [1/2, 3/5] [[http://en.wikipedia.org/wiki/Easley_Blackwood,_Jr.|Easley Blackwood Jr.]] defined a characterizing constant R which we may generalize to any MOS as follows. If a/b < g < c/d is a generator with the given Farey pair, take the ratio of relative errors R = (bg - a)/(c - dg). Since this is a ratio of positive numbers, it is positive. As g tends towards a/b it tends to zero, and as g goes to c/d R goes to infinity. When g equals (a + c)/(b + d) it takes the value 1, and the range of propriety is 1/2 <= R <= 2. | |||
When R is less than 1, it represents the ratio in (logarithmic) size between the smaller and the larger step. When it is greater than 1, it is larger/smaller. By replacing g with 1 - g if necessary, we can reduce always to the case where R>1 (or R<1 if we prefer.) | |||
=Algorithms= | |||
Below is some Maple code for various mathematical routines having to do with MOS. If you have access to Maple, you can of course copy and run these programs. Even if you do not, since Maple code makes better pseudocode than most languages or computer algebra packages afford, it can be used as pseudocode. For that purpose, it will be helpful to know that "modp(x, n)" means reducing x mod the integer n to 0, 1, ..., n-1 not only when x is an integer, but also when it is a rational number with denominator prime to n. In that case, p/q mod n = r means p = qr mod n. | |||
log2 := proc(x) | |||
# logarithm base 2 | |||
evalf(ln(x)/ln(2)) end: | |||
nextfarey := proc(q, n) | |||
# next in row n of Farey sequence from q, 0 <= q <= 1 | |||
local a, b, r, s; | |||
if q >= (n-1)/n then RETURN(1) fi; | |||
a := numer(q); | |||
b := denom(q); | |||
s := n - modp(n + 1/a, b); | |||
r := modp(1/b, s); | |||
r/s end: | |||
prevfarey := proc(q, n) | |||
# previous in row n of Farey sequence from q, 0 <= q <= 1 | |||
local a, b, r, s; | |||
if q=0 then RETURN(0) fi; | |||
if n=0 then RETURN(0) fi; | |||
a := numer(q); | |||
b := denom(q); | |||
s := n - modp(n - 1/a, b); | |||
r := modp(-1/b, s); | |||
r/s end: | |||
fareypair := proc(q) | |||
# Farey pair with q as its mediant | |||
local n; | |||
n := denom(q); | |||
[prevfarey(q, n), nextfarey(q, n)] end: | |||
mediant := proc(u, v) | |||
# mediant of two rational numbers u and v | |||
(numer(u) + numer(v))/(denom(u) + denom(v)) end: | |||
convergents := proc(z) | |||
# convergent list for z | |||
local q; | |||
convert(z,confrac,'q'); | |||
q end: | |||
exlist := proc(l) | |||
# expansion of a convergent list to semiconvergents | |||
local i, j, s, d; | |||
if nops(l)<3 then RETURN(l) fi; | |||
d[1] := l[1]; | |||
d[2] := l[2]; | |||
s := 3; | |||
for i from 3 to nops(l)-1 do | |||
for j from 1 to (numer(l[i])-numer(l[i-2]))/numer(l[i-1]) do | |||
d[s] := | |||
(j*numer(l[i-1])+numer(l[i-2]))/(j*denom(l[i-1])+denom(l[i-2])); | |||
s := s+1 od od; | |||
convert(convert(d, array), list) end: | |||
semiconvergents := proc(z) | |||
# semiconvergent list for z | |||
exlist(convergents(z)) end: | |||
penult := proc(q) | |||
# penultimate convergent to q | |||
local i, u; | |||
u := convergents(q); | |||
if nops(u)=1 then RETURN(u[1]) fi; | |||
for i from 1 to nops(u) do | |||
if u[i]=q then RETURN(u[i-1]) fi od; | |||
end: | |||
Ls := proc(q) | |||
# large-small steps from mediant q | |||
local u; | |||
u := fareypair(q); | |||
[denom(u[2]), denom(u[1])] end: | |||
medi := proc(u) | |||
# mediant from Large-small steps | |||
local q, r; | |||
if u[2]=1 then RETURN(1/(u[1]+1)) fi; | |||
r := igcd(u[1], u[2]); | |||
if r>1 then RETURN(medi([u[1]/r, u[2]/r])) fi; | |||
q := penult(u[1]/u[2]); | |||
if q > u[1]/u[2] then RETURN((numer(q)+denom(q))/(u[1]+u[2])) fi; | |||
(u[1]+u[2]-numer(q)-denom(q))/(u[1]+u[2]) end: | |||
Lsgen := proc(g, n) | |||
# given generator g and scale size n determines large-small steps | |||
local q, u, w; | |||
q := round(n*g)/n; | |||
w := n/denom(q); | |||
u := fareypair(q); | |||
if g<u[1] or g>u[2] or g=q then RETURN('false') fi; | |||
if g<q then RETURN([w*denom(u[1]), w*denom(u[2])]) fi; | |||
[w*denom(u[2]), w*denom(u[1])] end: | |||
revlist := proc(l) | |||
# reverse of list | |||
local i, v, e; | |||
e := nops(l); | |||
for i from 1 to e do | |||
v[i] := l[e-i+1] od; | |||
convert(convert(v,array),list) end: | |||
invcon := proc(l) | |||
# inverse continued fraction | |||
local d, i, h, k; | |||
h[-2] := 0; | |||
h[-1] := 1; | |||
k[-2] := 1; | |||
k[-1] := 0; | |||
for i from 0 to nops(l)-1 do | |||
h[i] := l[i+1]*h[i-1] + h[i-2]; | |||
k[i] := l[i+1]*k[i-1] + k[i-2]; | |||
d[i+1] := h[i]/k[i] od; | |||
convert(convert(d, array), list) end: | |||
quest := proc(x) | |||
# Minkowski ? function | |||
local i, j, d, l, s, t; | |||
l := convert(x, confrac); | |||
d := nops(l); | |||
s := l[1]; | |||
for i from 2 to d do | |||
t := 1; | |||
for j from 2 to i do | |||
t := t - l[j] od; | |||
s := s + (-1)^i * 2^t od; | |||
if type(x, float) then s := evalf(s) fi; | |||
s end: | |||
Box := proc(x) | |||
# inverse ? function | |||
local d, e, i, n, w, y; | |||
if type(x, integer) then RETURN(x) fi; | |||
y := x-floor(x); | |||
if y = 1/8 then RETURN(floor(x)+1/4) fi; | |||
w := round(log2(10)*Digits)-5; | |||
n := round(2^w * y); | |||
i :=0; | |||
while n>0 do | |||
i := i+1; | |||
if modp(n,2)=0 then | |||
d[i] := padic[ordp](n, 2); | |||
n := n/2^d[i]; | |||
else | |||
d[i] := padic[ordp](n+1, 2); | |||
n := (n-2^d[i]+1)/2^d[i] fi od; | |||
e := convert(convert(d, array), list); | |||
e := subsop(1=NULL,e); | |||
w := ceil(-log2(y)); | |||
e := [op(e), w]; | |||
e := [op(e), floor(x)]; | |||
e := revlist(e); | |||
n := invcon(e); | |||
w := n[nops(n)]; | |||
if type(x, rational) and modp(denom(x), 2)=0 then RETURN(w) fi; | |||
evalf(w) end: | |||
</pre></div> | </pre></div> | ||
<h4>Original HTML content:</h4> | <h4>Original HTML content:</h4> | ||
<div style="width:100%; max-height:400pt; overflow:auto; background-color:#f8f9fa; border: 1px solid #eaecf0; padding:0em"><pre style="margin:0px;border:none;background:none;word-wrap:break-word;width:200%;white-space: pre-wrap ! important" class="old-revision-html"><html><head><title>Mathematics of MOS</title></head><body><!-- ws:start:WikiTextTocRule: | <div style="width:100%; max-height:400pt; overflow:auto; background-color:#f8f9fa; border: 1px solid #eaecf0; padding:0em"><pre style="margin:0px;border:none;background:none;word-wrap:break-word;width:200%;white-space: pre-wrap ! important" class="old-revision-html"><html><head><title>Mathematics of MOS</title></head><body><!-- ws:start:WikiTextTocRule:16:&lt;img id=&quot;wikitext@@toc@@flat&quot; class=&quot;WikiMedia WikiMediaTocFlat&quot; title=&quot;Table of Contents&quot; src=&quot;/site/embedthumbnail/toc/flat?w=100&amp;h=16&quot;/&gt; --><!-- ws:end:WikiTextTocRule:16 --><!-- ws:start:WikiTextTocRule:17: --><a href="#Mathematical Definition of MOS">Mathematical Definition of MOS</a><!-- ws:end:WikiTextTocRule:17 --><!-- ws:start:WikiTextTocRule:18: --> | <a href="#Mathematical Properties of MOS">Mathematical Properties of MOS</a><!-- ws:end:WikiTextTocRule:18 --><!-- ws:start:WikiTextTocRule:19: --> | <a href="#Visualizing MOS: Generator Chains, Pitch Space, and Hierarchies">Visualizing MOS: Generator Chains, Pitch Space, and Hierarchies</a><!-- ws:end:WikiTextTocRule:19 --><!-- ws:start:WikiTextTocRule:20: --> | <a href="#Classification of MOS">Classification of MOS</a><!-- ws:end:WikiTextTocRule:20 --><!-- ws:start:WikiTextTocRule:21: --><!-- ws:end:WikiTextTocRule:21 --><!-- ws:start:WikiTextTocRule:22: --><!-- ws:end:WikiTextTocRule:22 --><!-- ws:start:WikiTextTocRule:23: --><!-- ws:end:WikiTextTocRule:23 --><!-- ws:start:WikiTextTocRule:24: --> | <a href="#Algorithms">Algorithms</a><!-- ws:end:WikiTextTocRule:24 --><!-- ws:start:WikiTextTocRule:25: --> | ||
<!-- ws:end:WikiTextTocRule: | <!-- ws:end:WikiTextTocRule:25 --><br /> | ||
<!-- ws:start:WikiTextHeadingRule:0:&lt;h1&gt; --><h1 id="toc0"><a name="Mathematical Definition of MOS"></a><!-- ws:end:WikiTextHeadingRule:0 -->Mathematical Definition of MOS</h1> | <!-- ws:start:WikiTextHeadingRule:0:&lt;h1&gt; --><h1 id="toc0"><a name="Mathematical Definition of MOS"></a><!-- ws:end:WikiTextHeadingRule:0 -->Mathematical Definition of MOS</h1> | ||
An MOS specifically consists of:<br /> | An MOS specifically consists of:<br /> | ||
| Line 95: | Line 269: | ||
Since the generator chain and logarithmic pitch space are both 1-dimensional, it may be helpful to graph them together in 2 dimensions. Here is a diagram for sensi[8], an octatonic <a class="wiki_link" href="/3L%205s">3L 5s</a> MOS scale with a generator of about 444¢. The x-axis shows the generator chain and the y-axis shows the nine tones (eight plus octave) in logarithmic pitch space. You can see that the vertical lines are evenly-spaced (since every generator is the same), while the horizontal lines have large and small gaps, representing the large and small steps of sensi[8].<br /> | Since the generator chain and logarithmic pitch space are both 1-dimensional, it may be helpful to graph them together in 2 dimensions. Here is a diagram for sensi[8], an octatonic <a class="wiki_link" href="/3L%205s">3L 5s</a> MOS scale with a generator of about 444¢. The x-axis shows the generator chain and the y-axis shows the nine tones (eight plus octave) in logarithmic pitch space. You can see that the vertical lines are evenly-spaced (since every generator is the same), while the horizontal lines have large and small gaps, representing the large and small steps of sensi[8].<br /> | ||
<br /> | <br /> | ||
<!-- ws:start:WikiTextLocalImageRule: | <!-- ws:start:WikiTextLocalImageRule:102:&lt;img src=&quot;/file/view/map_of_sensi%5B8%5D.png/287845258/map_of_sensi%5B8%5D.png&quot; alt=&quot;&quot; title=&quot;&quot; /&gt; --><img src="/file/view/map_of_sensi%5B8%5D.png/287845258/map_of_sensi%5B8%5D.png" alt="map_of_sensi[8].png" title="map_of_sensi[8].png" /><!-- ws:end:WikiTextLocalImageRule:102 --><br /> | ||
<br /> | <br /> | ||
And another way to visualize MOS scales is hierarchically. Every MOS scale with 3 or more tones:<br /> | And another way to visualize MOS scales is hierarchically. Every MOS scale with 3 or more tones:<br /> | ||
<ol><li>contains at least one MOS scale with fewer tones (and in fact, more than one instance of it), and</li><li>is contained (more than once) in either<ol><li>an MOS scale with more tones, or</li><li>an equal scale (when L:s = 2:1).</li></ol></li></ol><br /> | <ol><li>contains at least one MOS scale with fewer tones (and in fact, more than one instance of it), and</li><li>is contained (more than once) in either<ol><li>an MOS scale with more tones, or</li><li>an equal scale (when L:s = 2:1).</li></ol></li></ol><br /> | ||
Below is a diagram showing four MOS scales in logarithmic pitch space generated by 7\<a class="wiki_link" href="/37edo">37edo</a> (approx. 227¢). Each contains the ones above it and is contained by the ones below it. There are additional MOS scales that would appear above the first line with 1, 2, 3, 4, and 5 tones, but they have been omitted. The bottom line is a case where L:s=2:1, which means that there are no more MOS scales to be had -- the next stopping point is at a complete chromatic scale of <a class="wiki_link" href="/37edo">37edo</a>.<br /> | Below is a diagram showing four MOS scales in logarithmic pitch space generated by 7\<a class="wiki_link" href="/37edo">37edo</a> (approx. 227¢). Each contains the ones above it and is contained by the ones below it. There are additional MOS scales that would appear above the first line with 1, 2, 3, 4, and 5 tones, but they have been omitted. The bottom line is a case where L:s=2:1, which means that there are no more MOS scales to be had -- the next stopping point is at a complete chromatic scale of <a class="wiki_link" href="/37edo">37edo</a>.<br /> | ||
<!-- ws:start:WikiTextLocalImageRule: | <!-- ws:start:WikiTextLocalImageRule:103:&lt;img src=&quot;/file/view/37edo_mos_07.png/285321926/37edo_mos_07.png&quot; alt=&quot;&quot; title=&quot;&quot; /&gt; --><img src="/file/view/37edo_mos_07.png/285321926/37edo_mos_07.png" alt="37edo_mos_07.png" title="37edo_mos_07.png" /><!-- ws:end:WikiTextLocalImageRule:103 --><br /> | ||
For more images showing the hierarchical arrangement of MOS scales, see <a class="wiki_link" href="/MOS%20scales%20of%2017edo">MOS scales of 17edo</a>, <a class="wiki_link" href="/31edo%20MOS%20scales">31edo MOS scales</a>, <a class="wiki_link" href="/MOS%20Scales%20of%2037edo">MOS Scales of 37edo</a>, and <a class="wiki_link" href="/MOS%20Scales%20of%20127edo">MOS Scales of 127edo</a>.<br /> | For more images showing the hierarchical arrangement of MOS scales, see <a class="wiki_link" href="/MOS%20scales%20of%2017edo">MOS scales of 17edo</a>, <a class="wiki_link" href="/31edo%20MOS%20scales">31edo MOS scales</a>, <a class="wiki_link" href="/MOS%20Scales%20of%2037edo">MOS Scales of 37edo</a>, and <a class="wiki_link" href="/MOS%20Scales%20of%20127edo">MOS Scales of 127edo</a>.<br /> | ||
<br /> | <br /> | ||
| Line 112: | Line 286: | ||
If the period is assumed to be 2^(1/n) for some integer n, we can give instead the total number of large and small steps in the octave, instead of just the period, and this is commonly done. In this case, GCD(L, s) gives the number of periods in an octave.<br /> | If the period is assumed to be 2^(1/n) for some integer n, we can give instead the total number of large and small steps in the octave, instead of just the period, and this is commonly done. In this case, GCD(L, s) gives the number of periods in an octave.<br /> | ||
<br /> | <br /> | ||
<!-- ws:start:WikiTextHeadingRule:8:&lt; | <!-- ws:start:WikiTextHeadingRule:8:&lt;h2&gt; --><h2 id="toc4"><a name="Classification of MOS-Classification via the ? function"></a><!-- ws:end:WikiTextHeadingRule:8 -->Classification via the ? function</h2> | ||
Yet another way of classifying MOS is via <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Minkowski%27s_question_mark_function" rel="nofollow">Minkowski's ? function</a>. Here ?(x) is a continuous increasing function from the real numbers to the real numbers which has some peculiar properties, one being that it sends rational numbers to <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Dyadic_rational" rel="nofollow">dyadic rationals</a>. Hence if q is a rational number 0 &lt; q &lt; 1 in use in the mediant system of classifying MOS, r = ?(q) = A/2^n will be a dyadic rational number which can also be used. Note that the ? function is invertible, and it and its inverse function, the Box function, have code given for them in the algorithms section at the bottom of the article.<br /> | |||
<br /> | |||
The integer n in the denominator of r (with A assumed to be odd) is the order (or n+1 is, according to some sources) of q in the <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree" rel="nofollow">Stern-Brocot tree</a>. The two neighboring numbers of order n+1, which define the range of propriety, can also be expressed in terms of the ? and Box functions as Box(r - 2^(-n-1) and Box(r + 2^(-n-1)). If r represents a MOS, the range of possible values for a generator of the MOS will be Box(r) &lt; g &lt; Box(r + 2^(-n)), and the proper generators will be Box(r) &lt; g &lt; Box(r + 2^(-n-1)). So, for example, the MOS denoted by 3/2048 will be between Box(3/2048) and Box(4/2048), which means that 2/21 &lt; g &lt; 1/10, and will be proper if 2/21 &lt; g &lt; 3/31. Hence 7/72, a generator for miracle temperament, will define a MOS but it will not be proper since 7/72 &gt; 3/31 = Box(3/2048 + 1/4096)).<br /> | |||
<br /> | |||
<!-- ws:start:WikiTextHeadingRule:10:&lt;h2&gt; --><h2 id="toc5"><a name="Classification of MOS-MOS in equal temperaments"></a><!-- ws:end:WikiTextHeadingRule:10 -->MOS in equal temperaments</h2> | |||
In an equal temperament, all intervals are integer multiples of a smallest unit. If the equal temperament is N-EDO and the period is an octave, the sizes of the large and small steps will be p/N and q/N, with p &gt; q. We then have L(p/N) + s(q/N) = 1, which on multiplying through by N gives us<br /> | |||
<br /> | |||
Lp + sq = N.<br /> | |||
<br /> | |||
which is a linear diophantine equation. Solving this by standard methods, and requiring L and s to be positive, gives us the [L, s] pair for the MOS. If some other quantity of equal steps gives the period, we may make the appropriate adjustment.<br /> | |||
<br /> | |||
<!-- ws:start:WikiTextHeadingRule:12:&lt;h2&gt; --><h2 id="toc6"><a name="Classification of MOS-Blackwood R constant"></a><!-- ws:end:WikiTextHeadingRule:12 -->Blackwood R constant</h2> | |||
In the context of the &quot;recognizable diatonic&quot; scales deriving from the Farey pair [1/2, 3/5] <a class="wiki_link_ext" href="http://en.wikipedia.org/wiki/Easley_Blackwood,_Jr." rel="nofollow">Easley Blackwood Jr.</a> defined a characterizing constant R which we may generalize to any MOS as follows. If a/b &lt; g &lt; c/d is a generator with the given Farey pair, take the ratio of relative errors R = (bg - a)/(c - dg). Since this is a ratio of positive numbers, it is positive. As g tends towards a/b it tends to zero, and as g goes to c/d R goes to infinity. When g equals (a + c)/(b + d) it takes the value 1, and the range of propriety is 1/2 &lt;= R &lt;= 2.<br /> | |||
<br /> | |||
When R is less than 1, it represents the ratio in (logarithmic) size between the smaller and the larger step. When it is greater than 1, it is larger/smaller. By replacing g with 1 - g if necessary, we can reduce always to the case where R&gt;1 (or R&lt;1 if we prefer.)<br /> | |||
<br /> | |||
<br /> | |||
<!-- ws:start:WikiTextHeadingRule:14:&lt;h1&gt; --><h1 id="toc7"><a name="Algorithms"></a><!-- ws:end:WikiTextHeadingRule:14 -->Algorithms</h1> | |||
Below is some Maple code for various mathematical routines having to do with MOS. If you have access to Maple, you can of course copy and run these programs. Even if you do not, since Maple code makes better pseudocode than most languages or computer algebra packages afford, it can be used as pseudocode. For that purpose, it will be helpful to know that &quot;modp(x, n)&quot; means reducing x mod the integer n to 0, 1, ..., n-1 not only when x is an integer, but also when it is a rational number with denominator prime to n. In that case, p/q mod n = r means p = qr mod n.<br /> | |||
<br /> | |||
log2 := proc(x)<br /> | |||
<ol><li>logarithm base 2</li></ol>evalf(ln(x)/ln(2)) end:<br /> | |||
<br /> | |||
nextfarey := proc(q, n)<br /> | |||
<ol><li>next in row n of Farey sequence from q, 0 &lt;= q &lt;= 1</li></ol>local a, b, r, s;<br /> | |||
if q &gt;= (n-1)/n then RETURN(1) fi;<br /> | |||
a := numer(q);<br /> | |||
b := denom(q);<br /> | |||
s := n - modp(n + 1/a, b);<br /> | |||
r := modp(1/b, s);<br /> | |||
r/s end:<br /> | |||
<br /> | |||
prevfarey := proc(q, n)<br /> | |||
<ol><li>previous in row n of Farey sequence from q, 0 &lt;= q &lt;= 1</li></ol>local a, b, r, s;<br /> | |||
if q=0 then RETURN(0) fi;<br /> | |||
if n=0 then RETURN(0) fi;<br /> | |||
a := numer(q);<br /> | |||
b := denom(q);<br /> | |||
s := n - modp(n - 1/a, b);<br /> | |||
r := modp(-1/b, s);<br /> | |||
r/s end:<br /> | |||
<br /> | |||
fareypair := proc(q)<br /> | |||
<ol><li>Farey pair with q as its mediant</li></ol>local n;<br /> | |||
n := denom(q);<br /> | |||
[prevfarey(q, n), nextfarey(q, n)] end:<br /> | |||
<br /> | |||
mediant := proc(u, v)<br /> | |||
<ol><li>mediant of two rational numbers u and v</li></ol>(numer(u) + numer(v))/(denom(u) + denom(v)) end:<br /> | |||
<br /> | |||
convergents := proc(z)<br /> | |||
<ol><li>convergent list for z</li></ol>local q;<br /> | |||
convert(z,confrac,'q');<br /> | |||
q end:<br /> | |||
<br /> | |||
exlist := proc(l)<br /> | |||
<ol><li>expansion of a convergent list to semiconvergents</li></ol>local i, j, s, d;<br /> | |||
if nops(l)&lt;3 then RETURN(l) fi;<br /> | |||
d[1] := l[1];<br /> | |||
d[2] := l[2];<br /> | |||
s := 3;<br /> | |||
for i from 3 to nops(l)-1 do<br /> | |||
for j from 1 to (numer(l[i])-numer(l[i-2]))/numer(l[i-1]) do<br /> | |||
d[s] :=<br /> | |||
(j*numer(l[i-1])+numer(l[i-2]))/(j*denom(l[i-1])+denom(l[i-2]));<br /> | |||
s := s+1 od od;<br /> | |||
convert(convert(d, array), list) end:<br /> | |||
<br /> | |||
semiconvergents := proc(z)<br /> | |||
<ol><li>semiconvergent list for z</li></ol>exlist(convergents(z)) end:<br /> | |||
<br /> | |||
penult := proc(q)<br /> | |||
<ol><li>penultimate convergent to q</li></ol>local i, u;<br /> | |||
u := convergents(q);<br /> | |||
if nops(u)=1 then RETURN(u[1]) fi;<br /> | |||
for i from 1 to nops(u) do<br /> | |||
if u[i]=q then RETURN(u[i-1]) fi od;<br /> | |||
end:<br /> | |||
<br /> | |||
Ls := proc(q)<br /> | |||
<ol><li>large-small steps from mediant q</li></ol>local u;<br /> | |||
u := fareypair(q);<br /> | |||
[denom(u[2]), denom(u[1])] end:<br /> | |||
<br /> | |||
medi := proc(u)<br /> | |||
<ol><li>mediant from Large-small steps</li></ol>local q, r;<br /> | |||
if u[2]=1 then RETURN(1/(u[1]+1)) fi;<br /> | |||
r := igcd(u[1], u[2]);<br /> | |||
if r&gt;1 then RETURN(medi([u[1]/r, u[2]/r])) fi;<br /> | |||
q := penult(u[1]/u[2]);<br /> | |||
if q &gt; u[1]/u[2] then RETURN((numer(q)+denom(q))/(u[1]+u[2])) fi;<br /> | |||
(u[1]+u[2]-numer(q)-denom(q))/(u[1]+u[2]) end:<br /> | |||
<br /> | |||
Lsgen := proc(g, n)<br /> | |||
<ol><li>given generator g and scale size n determines large-small steps</li></ol>local q, u, w;<br /> | |||
q := round(n*g)/n;<br /> | |||
w := n/denom(q);<br /> | |||
u := fareypair(q);<br /> | |||
if g&lt;u[1] or g&gt;u[2] or g=q then RETURN('false') fi;<br /> | |||
if g&lt;q then RETURN([w*denom(u[1]), w*denom(u[2])]) fi;<br /> | |||
[w*denom(u[2]), w*denom(u[1])] end:<br /> | |||
<br /> | |||
revlist := proc(l)<br /> | |||
<ol><li>reverse of list</li></ol>local i, v, e;<br /> | |||
e := nops(l);<br /> | |||
for i from 1 to e do<br /> | |||
v[i] := l[e-i+1] od;<br /> | |||
convert(convert(v,array),list) end:<br /> | |||
<br /> | |||
invcon := proc(l)<br /> | |||
<ol><li>inverse continued fraction</li></ol>local d, i, h, k;<br /> | |||
h[-2] := 0;<br /> | |||
h[-1] := 1;<br /> | |||
k[-2] := 1;<br /> | |||
k[-1] := 0;<br /> | |||
for i from 0 to nops(l)-1 do<br /> | |||
h[i] := l[i+1]*h[i-1] + h[i-2];<br /> | |||
k[i] := l[i+1]*k[i-1] + k[i-2];<br /> | |||
d[i+1] := h[i]/k[i] od;<br /> | |||
convert(convert(d, array), list) end:<br /> | |||
<br /> | |||
quest := proc(x)<br /> | |||
<ol><li>Minkowski ? function</li></ol>local i, j, d, l, s, t;<br /> | |||
l := convert(x, confrac);<br /> | |||
d := nops(l);<br /> | |||
s := l[1];<br /> | |||
for i from 2 to d do<br /> | |||
t := 1;<br /> | |||
for j from 2 to i do<br /> | |||
t := t - l[j] od;<br /> | |||
s := s + (-1)^i * 2^t od;<br /> | |||
if type(x, float) then s := evalf(s) fi;<br /> | |||
s end:<br /> | |||
<br /> | <br /> | ||
Box := proc(x)<br /> | |||
<ol><li>inverse ? function</li></ol>local d, e, i, n, w, y;<br /> | |||
if type(x, integer) then RETURN(x) fi;<br /> | |||
y := x-floor(x);<br /> | |||
if y = 1/8 then RETURN(floor(x)+1/4) fi;<br /> | |||
w := round(log2(10)*Digits)-5;<br /> | |||
n := round(2^w * y);<br /> | |||
i :=0;<br /> | |||
while n&gt;0 do<br /> | |||
i := i+1;<br /> | |||
if modp(n,2)=0 then<br /> | |||
d[i] := padic[ordp](n, 2);<br /> | |||
n := n/2^d[i];<br /> | |||
else<br /> | |||
d[i] := padic[ordp](n+1, 2);<br /> | |||
n := (n-2^d[i]+1)/2^d[i] fi od;<br /> | |||
e := convert(convert(d, array), list);<br /> | |||
e := subsop(1=NULL,e);<br /> | |||
w := ceil(-log2(y));<br /> | |||
e := [op(e), w];<br /> | |||
e := [op(e), floor(x)];<br /> | |||
e := revlist(e);<br /> | |||
n := invcon(e);<br /> | |||
w := n[nops(n)];<br /> | |||
if type(x, rational) and modp(denom(x), 2)=0 then RETURN(w) fi;<br /> | |||
evalf(w) end:</body></html></pre></div> | |||