User JWinslow23 brought this up in chat yesterday: What's the fastest way to determine whether a list of six or so musical notes represented by numbers from 0 to 12 is "musical"; that is, all the notes fall within the same major scale?

I couldn't wait for him to start a topic, so I'm posting my code here. With the list in L1:


Code:


Where each "badmask" is a 12 element list of the notes *not* in a certain major scale. For example, badmask1 would be:


Code:


I have a feeling there's a faster solution. Ideas:

Instead of masking with lists, use prime factors and remainder(. That is, use the first 12 primes; the masks would be the primes multiplied together that correspond to the notes in a certain musical scale. min(remainder({goodMasks},notes)) would give a 1 if for each mask, there is a prime in "notes" that isn't in that mask.

I don't know which is faster; testing must be done.

<winey> I hate the western musiacal notation, why cant we just write notes as frequencies?!?!</winey>
<oftopic>
It does not mater if notes are in the same scale or not, it matters if they sound good or not
the reason we think some sequence of notes is better is becouse we are used to the western music system <_<
</oftopic>

Thank you for this, lirtosiast. However, I did state in IRC (after you had left for a while, to be fair) that my solution was good enough for my purposes.

I do appreciate this solution, though.

EDIT: After testing your code, I'd like to tell you a few more specifics. I needed code for any length of notes to test, not 8 as your program seems to suggest to me. Also, there are 12 tones in the chromatic scale, and thus, there are 12 major scales I want to test. How would I modify this to fit that?

My code I had before asking you this (I used string input, and I used the characters 0 through B, as base 12 digits):

Code:

I agree with these points - although it is difficult for humans to read a list of frequencies and times and then spontaneously translate that into sounds. Most of the algorithmic music I have seen is based off of a series of filters or "masks" that are applied in some sort of pattern or at random. This results in something that might be relatively appealing. It could be relatively simple to generate music from a fixed set of notes; however it would be very limited (which could be useful for video games and other things where the music is not the main point of interest).

So yeah. I really want to know the fastest solution. It'd be interesting to do an analysis with arbitrary sequences, whether or not they are "musical". As well, I wonder how we'd do a program that finds the largest subsequences of a sequence that are musical together.

Example (in pi base 12):
31848
0
9493b918664
573a
62
11bb151551
a05729290a7
8
09a492742
14
0a60a55
2
56a066
1a03753a3aa5
480
564
6880181a3683083

It'd be interesting to feed in other irrational constants and see their results.

Here's how I'd go about solving this problem. Note that I don't have a calc on me right now, so I'm just going to explain the algorithm. Should be easy enough to implement.

So, a major scale is made up of the following intervals: whole, whole, half, whole, whole, whole, half. Using this, you can determine if any given subset of notes are in the same major scale. So, do the following:

Make a list with the intervals of a major scale: { 2, 2, 1, 2, 2, 2, 1 }.

Have a list with the inputs, assume that there are no duplicates, and that they are in order. If this isn't true, make it true. This part should be trivial. For the sake of example, the following is my input list: { 0 4 5 9 11 }

Alright, our major-scale list is broken up into whole and half step intervals. So, we need to get our input list into the same intervals. First, just get the intervals between the notes (by subtracting each note from the next): { 4 1 4 2 }

Next, decompose any interval > 2 into a sum of 2s and 1. This should just take a loop through each element and another list you shove the values into. With our list, this should become: { 2 2 1 2 2 2 }

Now we have the sequence of whole and half steps that make up the input list. Next, we just need to check if this list exists in the list of major scale intervals. We can see that this is true by looking at it, but two for loops should be able to take care of this in your code.

Here's another example that fails:
Input: { 0 1 9 12 }
Intervals: { 1 8 3 }
Decomposed intervals: {1 2 2 2 2 2 1 }
You can see that this doesn't show up at all in our list of intervals.

Some nice things:
1) You can check other scale types, too. So long as it can be broken up into whole- and half-step intervals. So a minor scale etc. If your scale as 1.5 steps, you have to change this a bit.
2) If your list of inputs is longer than the number of elements in your scale interval list, you know they don't fit! So that one is pretty quick.
3) You can determine WHICH scale these notes fall in as well, by which index they match in the scale list, and which note is the first in the list.

My program works for all lengths; the 8 masks should be 7, because there are 7 different major scales that include a certain note.

Here's my prime-products method. I estimate the runtime to be around 80 ms, of which more than half is on the last line. Because I don't shift the list so 1 is the first element, I need 12 masks instead of 7, but masking using primes is faster, so I think it's fine.


Code:


I haven't tested this yet, but I think it should work.

Jonimus found a deficiency in my algorithm: When you decompose the intervals, you have to actually get all the permutation for any given interval. So if your notes are { 0 4 9 12 }, your intervals are { 4 5 3} which decompose to { { 2 2 } { 2 2 1 } { 2 1 } }, and you need to actually test each combination of permutations of that decomposition. This is quite slow, so it's definitely not the fastest. I still like it as a solution, though, so long as you're not on a memory and speed restricted platform.

lirtosiast: I'd love an explanation of your algorithm, rather than just code.

Is there a way without using remainder(? I downgraded to OS 2.43 and refuse to upgrade to MP again.

Code:

I'm fully aware of that, I use it regularly for mod() expressions

Also, lirtosiast, your code works. I just had to change L2(L1(X to L2(1+L1(X.

JWinslow: Yes, I had written it for 1~12 rather than 0~11. You don't need to multiply by B after the fPart(, by the way, since you're checking against 0 anyway.

Here's an explanation (assuming again 1~12):


Code:


That's the first part. It converts a list like L1={1,5,10,13} to one like L2={1,0,0,0,1,0,0,0,0,1,0,0,1}, where the positions of the 1s are the numbers in L1. To make this O(n) rather than O(n*musical notes), I loop through the list with a For( rather than using a seq(max(L1=X),X,1,12).


Code:


That's the second part. The returned value will be divisible by 2 if there was a 1 in L2(1), divisible by 3 if there was a 1 in L2(2), and so on up to the 12th prime. Finally for the last part:


Code:


Let's take just the first number for now:


Code:


If Ans is a multiple of any prime that is *not* in 29153410, the remainder will be nonzero. Therefore, if Ans contains any musical notes that are not in the musical scale, the remainder will be nonzero. This does the same thing as max(L2 and not({1,0,1,0,1,1,0,1,0,1,0,1}))—but it's fast. 4 ms vs 15, and since we're doing operations on single numbers we can even vectorize on a whole list, reducing parser overhead!

The other eleven numbers represent the primes that are notes in the other 11 possible musical scales; for a list to not be musical, it needs to fail (that is, have a nonzero remainder for) every scale. So it passes if the min( is zero.

This method of using products of primes to represent sets was inspired by Weregoose's famous routine to score a game of Yahtzee.

I generated the masks using a simple Python script.

I completely missed a much simpler algorithm for finding whether notes are musical: Just map the notes onto the circle of fifths, and they're musical if they all lie on a consecutive arc of seven notes--that is, there's a continuous gap of five.

Mapping onto the circle of fifths is as simple as multiplying by 5 and modding by 12; thus:


Code:


Input is, as before, a unique list. Now it doesn't need to be sorted ascending. I judge maybe... 30 ms. SortA( is O(n^2), but since the lists are at most 13 elements it shouldn't take too long.

I use augment( to make sure that a continuous gap of five is counted, even if it wraps around from 11 to 0.

You know what they say: premature optimization is the root of all evil. I guess this applies to optimizing the code before the algorithm too.