Home

This is a short follow-up on the last post about rhythmic canon mod p. You may recall I mentionned that Hélianthe had found a greedy algorithm which could find compact rhythmic canons mod p, and I explained how this algorithm works. If you like coding, you should have no problem implementing it in the language of your choice. And if you don’t, here’s my version in C:

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

int main(int argc, char *argv[])
{
	int N;
	int* U;
	int i,mark=0,flag=0;
	unsigned long long L,entry=0;
	FILE* output_file=NULL;
	
	if(argc<2) {
		printf("Length of the motive is required !\n");
		exit(1);
	}
	N = atoi(argv[1]);
	if(argc==3)
		output_file=fopen(argv[2],"w");
		if (output_file!=NULL)
			fprintf(output_file,"Entries for canon with motive {0,1,%d}\n",N);

	
	U = calloc(N+1,sizeof(int));
	if (U==NULL) {
		printf("Error during memory allocation...exiting now !\n");
		exit(1);
	}

	L=N+1;
	
	while(flag==0) {
		
		L+=mark;
		entry+=mark;
		if (output_file!=NULL)
			fprintf(output_file,"%llu\n",entry);
					
		U[0]=1-U[0];
		U[1]=1-U[1];
		U[N]=1-U[N];

		flag=1;
		for (mark=0; mark<N+1; mark++) {
			if (U[mark]==0) {
				flag=0;
				break;
			}
		}
		
		for (i=mark; i<N+1; i++)
			U[i-mark]=U[i];
		for (i=(N+1-mark); i<N+1; i++)
			U[i]=0;
	}
	printf("Final length of canon with motive {0,1,%d}: %llu \n",N,L);
	if (output_file!=NULL)
		fclose(output_file);
	free(U);
}

The program takes one mandatory argument which is the parameter k for determining the length of a \{0,1,k\} canon mod 2, and one optional argument which is the name of a file where the entries of the canon should be written (i.e. the term B in the decomposition A \bigoplus_N B).

Of course, you can modify the above program to implement any motive A you want, for example \{0,2,k\} or \{0,1,2,k\} instead of \{0,1,k\}.

To finish, here is a graph of the logarithm of the length of the canons with A=\{0,1,k\}, with respect to k, for k from 2 up to 41 (this last one took two days and a half to compute on my Mac…):

Graph_lengths_canons_01k

You can clearly see the particular cases A=\{0,1,k=2^p\} and A=\{0,1,k=2^p+1\}. Starting from k=18, things get interesting as we don’t necessarily have an exponential growth of the length of the canon with k. More on that in a later post…

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s