Octave Tree

00ctztree.md

CTZTree

A tree can be produced by counting the number of trailing zeros from an input integer index.

This count ('c') of trailing zeros (or position of the lowest bit) comes back every 2^c sample, i.e. corresponds to a frequency of 2^-c

Furthermore every sample corresponds with one and only one octave.

I first encountered this contruction in pink noise generator in audio, using this tree of octaves to downsample a source of white noise into many down-octaves with a gain of 2^{-Octave}

One advantage is that the downsampled octaves pull from the white noise generator at most once per sample, so there's an even load on the generator and no "bursts" of randomness.

• Voss-McCartney pink noise generator, see http://www.firstpr.com.au/dsp/pink-noise/#Voss and http://www.firstpr.com.au/dsp/pink-noise/#Voss-McCartney
• Stefan Stenzel's New Shade Of Pink generator, see http://stenzel.waldorfmusic.de/post/pink/

Application by Alex Evans to generate pink noise in a tweet:

one cheap way to make fairly pink noise: static signed char r[8]; static int pink,frame; int b=__builtin_ctz(128|frame++); pink-=r[b]; r[b]=rand(); return pink+=r[b]; // running sum of 8 uniform random numbers updated every 2,4,8... samples

ctztree.c

//
// A tree can be produced by counting the number of trailing zeros
// from an input integer index.
//
// This count ('c') of trailing zeros (or position of the lowest bit)
// comes back every 2^c sample, i.e. corresponds to a frequency of 2^-c
//
// Furthermore every sample corresponds with one and only one octave.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

// Example C standard implementation, replace with your favorite
// compiler's intrinsic or the CTZ/BSF instruction of your target
// CPU.
int count_trailing_zeros(unsigned int x) {
  int c = 0;
  for (int o = 0; o < sizeof(unsigned int)*8; o++) {
    unsigned int mask = 1U << o;
    if (x & mask) break;
    c++;
  }
  return c;
}

int globals_length = 16;

int parse_args(int argc, char **argv);

int main(int argc, char **argv) {
  if (parse_args(argc, argv) < 0) {
    return -1;
  }
  int const length = globals_length;
  for (int x = 0; x < length; x++) {
    int y = count_trailing_zeros(x + 1);
    printf("%0*x:%0*x %*sx\n", 4, x, 4, y, y, "");
  }
}

int parse_args(int argc, char **argv)
{
  int argi = 1;
  if (argi != argc) {
    if (argv[argi][0] == '-') {
      fprintf(stderr, "USAGE: %s <length>\n", argv[0]);
    }
  }
  if (argi != argc) {
    char *end;
    long y = strtol(argv[argi], &end, 10);
    if (y < 0) { 
      fprintf(stderr, "ERROR:%s:argv[%d]:length: expected positive number\n", argv[0], argi);
      return -1;
    } else if (y > INT_MAX) {
      fprintf(stderr, "ERROR:%s:argv[%d]:length: too large number\n", argv[0], argi);
      return -1;
    } 
    globals_length = (int) y;
    argi++;
  }
  if (argi != argc) {
      fprintf(stderr, "ERROR:%s:argv[%d]: too many arguments\n", argv[0], argi);
  }
  return 0;
}

result.txt

nicolass-mini:CTZTree nicolas$ ./ctztree 16
0000:0000 x
0001:0001  x
0002:0000 x
0003:0002   x
0004:0000 x
0005:0001  x
0006:0000 x
0007:0003    x
0008:0000 x
0009:0001  x
000a:0000 x
000b:0002   x
000c:0000 x
000d:0001  x
000e:0000 x
000f:0004     x