Translating C algorithm to Arduino.

Hello and Noob/Lurker alert :slight_smile:

I am trying to implement Bjorklund’s algorithm, which aims to:

“distribute n pulses over m timing slots in the most even way possible, even though n may not necessarily be an even divisor of m.”

I swiped the algorithm from the paper and modified it so it would run on Arduino, also referencing this (unresolved) post: http://forum.arduino.cc/index.php?topic=77981.0

However, I am experiencing some problems with the code and I need some fresh eyes and guidance. I would be extremely grateful.

Here is what is currently running:

//Bjorklund's Algorithm 
// see: https://ics-web.sns.ornl.gov/timing/Rep-Rate%20Tech%20Note.pdf

int count[16];
int divisor;
int i;
int pattern[16];

void setup() {
  Serial.begin(9600);
}

void loop() {

  delay(3000); //Give enough time to open the serial window and study the output....
  Serial.println(); //Blank line
  
  
  compute_bitmap (16,4); //e.g. Compute for 4 Pulses in 16 steps
}


void compute_bitmap(int num_slots, int num_pulses) {
 
  int remainder[16]; // Should this be declared as a global????

  divisor = (num_slots - num_pulses);
  remainder[0] = num_pulses;
  int newLength; 
  int level = 0; 
  int cycleLength = 1;
  int remLength = 1;
  do { 
    count[level] = (divisor / remainder[level]); 
    remainder[level+1] = (divisor % remainder[level]); 
    divisor = remainder[level]; 
    newLength = (cycleLength * count[level]) + remLength;
    remLength = cycleLength;
    cycleLength = newLength; 
    level = level + 1; 
    
    
    //Debug
    //Serial.println(newLength);
    //Serial.println("---");
    //delay(200); //debug
  }

  while (remainder[level] > 1); 
  count[level] = divisor; 
  if (remainder[level] > 0) 
    cycleLength = (cycleLength * count[level]) + remLength;
  build_string(level); 
}


void build_string(int level)   {

  if (level == -1) {
    //append a “0” to the end of the bitmap;  
    Serial.println("0"); //debug
    delay(500);
  }
  else if (level == -2) {
    //append a “1” to the end of the bitmap;
    Serial.println("1"); //debug
    delay(500);
  }
  else { 
    for (i=0; i < count[level]; i++) 
      build_string(level-1);

    if (remainder[level] != 0) 
      build_string(level-2); 

  }
}

Firstly, if I declare int remainder[16] as a global variable at the top of the file, I receive the following error:

error: invalid conversion from 'double (*)(double, double)' to 'int' [-fpermissive]
error: ISO C++ forbids comparison between pointer and integer [-fpermissive]

But if I instead declare it within the build_string() function, it compiles and runs.

Why is this so?

Secondly, when the algorithm does run, I get very mixed results. For example,

18/6 (001001001001001001) looks OK, as does 12/5 (010010100101), 16/4 etc.

However, 16/6 (0101010101010101) is definitely wrong, and sometimes I just get a stream of 1’s and 0’s.

It seems to be breaking-down somewhere and I having trouble debugging it. Can anyone spot where I’ve gone wrong?

Many kind thanks in advance for any nuggets of help.

:slight_smile:

If remainder[] will be shared among different modules, it has to be declared global. However, the error message that you get doesn't make sense to me. Post the code that causes the error, and you will probably receive better informed suggestions.

Hi, and thanks.

Below is the code the throws the error. It’s the same as the code above except int remainder[16] is declared globally.

//Bjorklund's Algorithm 
// see: https://ics-web.sns.ornl.gov/timing/Rep-Rate%20Tech%20Note.pdf

int count[16];
int divisor;
int i;
int pattern[16];

int remainder[16];

void setup() {
  Serial.begin(9600);
}

void loop() {

  delay(3000); //Give enough time to open the serial debug window and study the output....
  Serial.println(); //Blank line
  
  
  compute_bitmap (16,4); //e.g. Compute for 4 Pulses in 16 steps
}


void compute_bitmap(int num_slots, int num_pulses) 
{ 
 

  divisor = (num_slots - num_pulses);
  remainder[0] = num_pulses;
  int newLength; 
  int level = 0; 
  int cycleLength = 1;
  int remLength = 1;
  do { 
    count[level] = (divisor / remainder[level]); 
    remainder[level+1] = (divisor % remainder[level]); 
    divisor = remainder[level]; 
    newLength = (cycleLength * count[level]) + remLength;
    remLength = cycleLength;
    cycleLength = newLength; 
    level = level + 1; 
    
    //Debug
    //Serial.println(newLength);
    //Serial.println("---");
    //delay(200); //debug
  }

  while (remainder[level] > 1);
  count[level] = divisor; 
  if (remainder[level] > 0) 
    cycleLength = (cycleLength * count[level]) + remLength;
  build_string(level); 
}


void build_string(int level)   {

  if (level == -1) {
    //append a “0” to the end of the bitmap;  
    Serial.println("0"); //debug
    delay(500);
  }
  else if (level == -2) {
    //append a “1” to the end of the bitmap;
    Serial.println("1"); //debug
    delay(500);
  }
  else { 
    for (i=0; i < count[level]; i++) 
      build_string(level-1);

    if (remainder[level] != 0) 
      build_string(level-2); 

  }
}

No errors are reported when I compile it using Arduino 1.0.5-r2 on Win7.

And OK on 1.5.6 on Windows 8.1.

Wow thanks. How mysterious! I must look again at my setup. I have not seen any such issues before.

I am on 1.0.6 , Win7.

here is the verbose error FWIW:

sketch_oct17a.ino: In function 'void compute_bitmap(int, int)':
sketch_oct17a.ino:31:14: warning: pointer to a function used in arithmetic [-Wpointer-arith]
sketch_oct17a:31: error: assignment of function 'double remainder(double, double)'
sketch_oct17a:31: error: cannot convert 'int' to 'double(double, double)' in assignment
sketch_oct17a.ino:37:46: warning: pointer to a function used in arithmetic [-Wpointer-arith]
sketch_oct17a:37: error: invalid operands of types 'int' and 'double(double, double)' to binary 'operator/'
sketch_oct17a.ino:38:22: warning: pointer to a function used in arithmetic [-Wpointer-arith]
sketch_oct17a.ino:38:22: warning: pointer to a function used in arithmetic [-Wpointer-arith]
sketch_oct17a.ino:38:52: warning: pointer to a function used in arithmetic [-Wpointer-arith]
sketch_oct17a:38: error: invalid operands of types 'int' and 'double(double, double)' to binary 'operator%'
sketch_oct17a.ino:39:30: warning: pointer to a function used in arithmetic [-Wpointer-arith]
sketch_oct17a:39: error: invalid conversion from 'double (*)(double, double)' to 'int' [-fpermissive]
sketch_oct17a.ino:51:25: warning: pointer to a function used in arithmetic [-Wpointer-arith]
sketch_oct17a:51: error: ISO C++ forbids comparison between pointer and integer [-fpermissive]
sketch_oct17a.ino:53:22: warning: pointer to a function used in arithmetic [-Wpointer-arith]
sketch_oct17a.ino: In function 'void build_string(int)':
sketch_oct17a.ino:75:24: warning: pointer to a function used in arithmetic [-Wpointer-arith]

OK I think I know the source of the issue. I just realized that I was coding on a Teensy and it looks like a library issue with Teensyarduino (which allows compatibility with Arduino IDE).

I will ask over there.

Thanks for your help. Appreciated.

:)

One problem is that there is no floating point that I can see, so these doubles are confusing.

Also this is a recursive function which may cause problems with the Arduino’s limited stack size.

There must be a remainder() function in a library somewhere. Change the name of the remainder array to something else to avoid the conflict.

Pete

OK, got it working. :slight_smile:

e.g for 17steps and 13 pulses:

Bjorklund took 15.00 microseconds
The pattern is...

11101110111011101

Am I measuring this correctly? Seems fast enough.

The pattern is correct but backwards, so now I have to figure out how to reverse sort it.

Here’s the working example that provides the above output:

//Bjorklund Working!

int count[16];
int level;
int steps;
int pulses;
int stepstatus=0;
char pattern[16];
float currentmicroTime;
float currentmicroTime2;

//2D array to hold the output of Bjorklund's Algo 
char trackArray[8][16] = { 

  {
    1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0    }
  ,
  {
    1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0    }
  ,
  {
    0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,1    }
  ,
  {
    0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0    }
  ,
  {
    0,1,0,0,1,1,0,1,0,1,1,0,0,1,0,0    }
  ,
  {
    1,0,1,0,0,1,0,1,1,0,0,0,0,1,0,1    }
  ,
  {
    1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0    }
  ,
  {
    1,1,0,0,1,0,0,1,0,1,0,1,0,0,0,1    }

};



void setup() {
  
  Serial.begin(9600);
}

void loop() {
  
  delay (2000);
  
  currentmicroTime = (float)micros();
  
  compute_bitmap(17,13); // Steps, Pulses
  
  currentmicroTime2 = (float)micros();
  
  
  Serial.print("Bjorklund took ");Serial.print(currentmicroTime2-currentmicroTime);Serial.print(" microseconds");
  Serial.println();
  Serial.println("The pattern is...");
  Serial.println();
  
  
  for (int i = 0; i < steps; i++) { 
      Serial.print(trackArray[1][i]);
  }
  
  Serial.println();
  Serial.println();  
  delay (5000); 
  
      
} 


void compute_bitmap (int num_slots,int num_pulses)  {
  
  int remainder[16]; //Seems to conflict with TeensyArduino when declared globally. However it does not interfere with operations.
  
  if (num_pulses > num_slots) {num_pulses = num_slots;}         
  int divisor = num_slots - num_pulses;
  steps = num_slots; pulses = num_pulses;
  remainder[0] = num_pulses;
  level = 0;
  do {
    count[level] = divisor / remainder[level];
    remainder[level+1] = divisor % remainder[level];
    divisor = remainder[level];
    level = level +1; }
    while (remainder[level] > 1);

    count[level] = divisor; 
    build_string (level);
 
}

void build_string (int level)  {
  if (level == -1) { 

  //Serial.println('0');  
    trackArray[1][stepstatus]='0'; //insert 0 into array
    stepstatus=stepstatus+1;      //plus 1
  }
  else if (level == -2)  {   

  //Serial.println('1');  
    trackArray[1][stepstatus]='1'; //insert 1 into array
    stepstatus=stepstatus+1;      //plus 1
  }
  else {
    //for (int i = count[level]; i >=0 ; i--)
    for (int i = 0; i < count[level]; i++)
    build_string(level-1);
    if (remainder[level] !=0)
    build_string(level-2);
  }

}

Cheers :slight_smile:

Hi,

Just coming back on this with some additional info and a new question

It seems that KeithRB was right - Arduino doesn't handle recursive functions well.

The final application I built works extremely well, however under stress testing it stops completely after approx 45 mins. I suspect this is due to a stack overflow. Is there any (simple) way to confirm this?

Based on this suspicion, I modified the code to workaround the recursion.

Simply, I duplicated the build_string function and called it build_string2. Now, instead of sending the output back to itself, the function first transmits it to build_string2 which in turn sends [u]it's[/u] output back to build_string.

Essentially the two functions bounce variables back and forth until the job is done. I am testing this now and it seems to have solved the problem.

My next question is: although I've stopped the function recursion, does creating this loop between 2 functions itself present any issues, or is there a best practice for situations like this?

Many thanks again for your valuable insights. :)