Random Non-Repeating 4 Step Sequencer - a case study in random sequence generation
  • image


    A random non-repeating sequencer generates a fixed set of random numbers in a random order. It's useful for sequencing because it's possible for a random sequencer to a string of sequences that are the exact same notes in a row. This method on the other hand ensures motion on every single note and within the entire sequence.

    This may seem an easy task at first, but when you examine it a little closer, it becomes a sticky problem, especially in Audulus, which doesn't have an obvious way to iterate through an array. It's a fascinating problem though, and one that gives you a deep insight into why computers are so incredible for tasks like this.

    This is a much improved version of the random non-repeating sequencer I made a while back. It has fewer sample and holds and a much less convoluted method. Below is a CPU% comparison between the old (top) and new (bottom) versions.


    How it works:

    1. A random number is generated and multiplied by n-0.001, where n = number of samples. In this case, 4.
    2. This number is used to control a multiplexer, which acts as the initial state of our unshuffled array. The number chosen is the first step in the sequence. In this case, one of the numbers [0, 1/3, 2/3, 1] is chosen.
    3. The next stage checks the numbers in the array against the chosen number. If the number is chosen, it is turned into a null (a zero).
    4. After that, the set of numbers are sorted using a bubble sort algorithm. This compares each number and determines which is higher and which is lower. This iterates a few times until all incoming sequences are perfectly sorted every time.
    5. The null (0) value obtained by step 3 is discarded and the random number generated in step 1 is multiplied by n-1.001 and chooses one of the remaining 3 numbers.
    6. Steps 3-5 are repeated until a final number remains unchosen, which is switched in position on a new Mux8 with the previous value, and chosen with the same n-2.001 value.

    ArrayX = Chosen [Remaining]
    Array0 = [0, 1/3, 2/3, 1]
    Array1 = 1/3 [0, 2/3, 1] {2}
    Array2 = 1/3, 1, [0, 2/3]
    Array3 = 1/3, 1, 0 [2/3]
    Array 4 = 1/3, 1, 0, 2/3

    The seed of the Random node inside the sequencer must be changed if multiple sequencers are being used at the same tempo and reset rate. If the sequencers are not being played at the same time, or resetting at the same moment, then it's fine to leave the seed the same.

    Keep in mind: when changing seeds, multiple seeds with values 0,1,2,3... will be just as random as 4810, 2795, 1972,... - so no need to go nuts with seed value changes.

    The effect of *not* changing the seed will only become apparent when you open the patch after closing it (when the Random node resets from the seed value), so just be aware of that.


    Randomness and the n! (n factorial):

    The formula for determining the number of possible random combinations for a given number is n! (n factorial). This translates to n*n-1*n-2*n-3...n-n+1. In 4's case, that's 4*3*2*1, or 24. That means there are 24 different patterns you'll hear over the course of using the sequencer.

    Now, of course, the *proper* way to do this random sequence generator in Audulus is to use a lookup table, or a Mux24 that contains all the possibilities of arrangements. I will actually make a version of that as well, but this is an important small proof-of-concept that explains the concept in a way that makes it easy to expand to more steps.

    The reason we don't use multiplexer-based lookup tables for larger factorials is the number of possibilities explodes quickly.*

    If we want an 8 step sequencer, that's 8! = 40,320
    16 step sequencer: 16! ~ 2.1*10^13
    32 step sequencer : 32! ~2.6*10^35

    It would be possible to make a more efficient 8 step sequencer in Audulus 4 when we have the data node, which can treat a .wav file as a lookup table. 40,320 samples is less than 1 second of audio.

    However, this method also *quickly* becomes useless. A 16 step sequencer would require nearly 126,000 HOURS (14 years!) of audio to cover all its possibilities! A 32 step sequencer would need 1.4^23 YEARS of audio - many times the AGE of the UNIVERSE!

    How it sounds:

    Assuming 4/4 time signature and BPM = 120;
    1 bar of 120 BPM 4/4 time = 8 seconds;

    A 4 step random non-repeating (RNR) sequencer randomized every 16 beats will take on average** 24 bars, or 192 seconds (3.2 minutes) to repeat an identical sequence. In reality, you'll hear sequences repeat more often than that, because the pure randomness only appears over large numbers.

    An 8 step RNR sequencer randomized every 16 beats will take on average 40,320 bars, or 89.6 hours to repeat an identical sequence. At this level, you can be almost certain that given an average 3m30s song, you will not hear the same sequence twice.

    A 16 step RNR sequencer randomized every 16 beats will take on average 2.1*10^13 bars, or ~5.3 million years to repeat an identical sequence.

    A 32 step RNR sequencer randomized every 32 beats (assuming 32nd notes here) will take on average 2.6*10^35 bars, or ~6.6*10^28 years to repeat an identical sequence. To put that into perspective, this is 5 quintillion times the age of the universe, and interestingly, almost exactly as long as the lifespan of electrons as detailed in this article (spooky coincidence):


    Thoughts on scaling:

    "Non-repeating" is of course subjective here, as the 0-1 output of the sequencer can be translated into a range that plays only one, two, or three notes when quantized, rather than the maximal 4 notes.

    The signal this 4 step sequencer creates must be at least 0-(3.99/12), or 0~1/3 wide to ensure that at least 4 semi tones are available to play. The formula for chromatic non-randomness is sequence*(n-0.001/12), when sequence<=12 steps.<br />
    Ranges smaller than the one provided by the formula might still move, but will not be non-repeating.

    This is of course an artistic choice for you - you can scale the width of the sequence down in one part, and expand it in another. You can use a Mapper node to bias the randomness exponentially, logarithmically, or in a U or n shape - all up to you.

    This is just to point out the "min spec" for true non-repetition.


    So there you have it. Although computers aren't exactly perfect at creating randomness for cryptography purposes, they are more than adequate for musical randomness.

    I will be creating a lookup table version of this 4 step RNR sequencer, as well as an 8 and 16 step version of the algorithmically generated one. I might wait until I'm snowed in to do the 32 step version ;)


    Further Reading:

    This is the shuffling algorithm I used - from what I understand it is the superior shuffle algorithm that creates provable true randomness.


    This is the sorting algorithm I used - it's not the most efficient, but it is the easiest to implement in Audulus


    Looking more closely it might not be exactly a bubble sort, but it's a similar principle, with the sorts happening in parallel with one another. Perhaps there is a more correct name of this algorithm I used, if so, leave a comment below and I'll amend it.


    *- this could be techinically feasible using @jjthrash's methods of altering Audulus JSON code with an iterative algorithm, but it would be terribly CPU inefficient compared to the shuffling/sorting algorithmic method. You would need 5,040 Mux8 nodes, not to mention all of the logic in between to combine them!

    ** - You can think of the appearance of randomness here like flipping a coin - it's rare to flip HTHTHTHT...over and over. More likely you'll get HHHTTHTHHTHTTTHHTHTHHHHHTTTT...but over time the number of heads and tails approaches a 50-50 distribution. This means it's very rare to, on a first listen through, have a totally un-repeated set of sequences over the course of the given period.
    4 Step Random Non-Repeating Sequencer Demo.audulus
    Screen Shot 2017-11-01 at 2.09.04 AM.png
    1378 x 1702 - 306K
    Screen Shot 2017-11-01 at 11.25.33 AM.png
    2750 x 1012 - 478K
    Screen Shot 2017-11-01 at 11.25.42 AM.png
    1494 x 1704 - 918K
    Screen Shot 2017-11-01 at 11.25.52 AM.png
    688 x 570 - 81K
  • This is craziness. Awesome work!
  • PS - In digging into it, I'm even more impressed. Are you some sort of programmer in hiding?

    I can't do it this week, but I would like to try to use code to build 8 and 16 step version of this.
  • @jjthrash - Thank you! And nope! I’m literally like a piano teacher staying one lesson ahead of the students. The first method I did I intuited and it worked but it’s really inefficient. This one I looked up “shuffling algorithm” and came up with this.

    There might even be a more efficient solution that I’m chasing now, so I’ll let you know about that.

    I’m making the 8 and 16 today and tomorrow probably, but algorithmically. Would be awesome to see what it looks like based on code. My guess is there wouldnt be enough CPU for the 16 step version if you use muxes.

    I’m going to actually make this a really decked out multimedia post on AllTheSynths and lines sincw their forum software is far superior to ours lol! I’ll also include documentation in the patch. Consider the above a first draft.
  • I think I came up with a simpler approach using the "inside-out" variant described at: https://en.wikipedia.org/wiki/Fisher–Yates_shuffle. I really like the demo patch.
    Screen Shot 2017-11-01 at 3.57.44 PM.png
    3624 x 2248 - 959K
    random sequence.audulus
  • This makes me nostalgic for the huge bongo patch @biminiroad made about a year ago.
    @stschoen. I always enjoy seeing your take on patches like this because you have an eye for simplicity. I think your approach will scale a little more neatly into 8 or 16 step versions.
  • I did some performance comparisons and @biminiroad's approach and mine are neck and neck for CPU usage, so I guess it's a matter of preference.
  • But there are only 4 expressions per a step as opposed to an exponentially decreasing number. I think the 8 step version would have 8 expressions per step and the 16 would have 16, correct?
  • Cool I'll take a look at this in a sec!

    I'm deep in a strange attactor patch I'm making right now...all this randomness got me thinking about.....CHAOS!
  • @biminiroad This is UNREAL! You are truly the master. (I'm so addicted to Audulus.)
  • @RobertSyrett, you are correct. For an 8 step this alternative has 8 expressions per step. I guess it's expressions vs. muxes. Here's an 8 step version. @biminiroad I'm looking forward to seeing the strange attractor.
    STS 8 step random sequencer.audulus
  • From the videos, Rob Hordijk was also very interested in chaos theory and how it relates to music. You’re certainly following in some illustrious footsteps. BTW your explanation was spot on. I think it will make an excellent tutorial.
  • @stschoen I love it! But I think the reset is acting more like a hold gate. Is this intended? If not I would just rename it, because hold is also very handy.
  • Reset should reset the counter driving the sequencer but doesn’t change the current pattern. I copied the sequencer section from @biminiroad’s design and haven’t looked at the logic for the counter, but I’ve found resets are tough to do reliably.
  • >I’ve found resets are tough to do reliably.

  • BTW I want to stress that the credit for this module belongs entirely to @biminiroad. He had the concept, did the research and put it together. I used his reference as the source for the algorithm I used. I love a puzzle and I was intrigued by the “inside-out” approach.
  • Indeed, @biminiroad, very nice presentation. Looking forward to the all the synths multimedia barrage.