for a thesis I am creating a program that constructs curling sequences.

The curling number of a sequence is defined as ‘the largest frequency of any period at the end of the sequence’. (For example, 11232323 has curling number 3, because 23 is repeated three times)

Currently, I am mostly interested in the appearance of a 1 as curling number, when the sequence is generated with any possible combination of 2’s and 3’s (for example, we generate 2322322 and want to find the first occurence of ‘1’ as curling number).

I changed to multi-threading recently, but my performance lacks for what I need.

Does anyone have any suggestions on how to improve the speed of this multi-threaded program? I hope I provided enough comments to make it clear, but any questions will be answered.

```
#include <vector>
#include <iostream>
#include <chrono>
#include <thread>
#include <mutex>
#include <cmath>
#pragma warning (disable : 26451)
using namespace std::chrono;
const int range = 200; // used to reserve size for each sequence
std::mutex m_tail; // thread-lock for the tail
int tail = 0; // value to keep track of the longest tail encountered
int length = 0; // user input to define length of generator
thread_local std::vector<short int> sequence(range); // sequence for each individual thread
thread_local long double duur = 0; // value for each individual thread to time functions
// this function finds the curling number (curl) of a sequence
// the curl of a sequence is defined as: the highest frequency of a period at the end of a sequence
// some examples:
// the curl of 11232323 is 3, because 23 is the most-repeated element at the end of the sequence
// the curl of 2222 is 4, because 2 is the most-repeated element at the end of the sequence
// the curl of 1234 is 1, because every period at the end of the sequence is repeated only once
int krul(short int j, short int last_curl) {
short int curl = 1; // the minimum curl of a sequence is 1
for (short int length = 1; length <= int(j / (curl + 1) + 1); ++length) {
short int freq = 1; // the minimum frequency of any period is 1
while ((freq + 1) * length <= j and std::equal(sequence.begin() + j - (freq + 1) * length, sequence.begin() + j - freq * length, sequence.begin() + j - length)) {
// while within length of the sequence, and while periods match, continue
++freq; // if they match, the frequency is increased with 1
if (freq > curl) { // if the frequency of this period is higher than the curl yet
curl = freq; // update the value for curl
if (curl > last_curl) { // mathematical break: the curl can't be 'last_curl + 2', so when we encounter 'last_curl + 1' we can stop
return curl;
}
}
}
}
return curl;
}
// this function constructs a whole sequence by adding the curling number and then recalculating the curling number since the sequence got a new element
// and then adds the new curling number and recalculates and so on and so on
int constructor(std::vector<short int> sequence_generator) {
sequence = (std::move(sequence_generator)); // we move the sequence from the generator to the main sequence
short int j = length;
short int last_curl = length;
for (j; j <= range; ++j) { // the sequence is built from starting length to given range
krul(j, last_curl);
short int curl = krul(j, last_curl); // the resulting curling number is the highest of all the candidate curling numbers.
if (curl == 1) { return j; } // for this program, we want to stop if the curling number == 1 and return the length of the sequence (j)
sequence(j) = curl;
if (curl >= 4) { return j + 1; } // if the curling number >= 4, the next curling number is 1 so we can already break and return the length of the sequence (j + 1)
last_curl = curl; // we update the value of last_curl for the next calculation
}
return 0; // we don't encounter this because each sequence breaks, but just in case we return 0
}
// this function takes a number and generates its binary twin, but then existing of 2's and 3's
// because we want every possible generator existing of any combination of 2's and 3's
// and after construction of the generator we call the constructor of the sequence
int decToBinary(unsigned long long n) {
std::vector<short int> sequence_generator(range);
for (long int i = length - 1; i >= 0; i--) {
long int k = n >> i;
if (k & 1) {
sequence_generator(length - 1 - i) = 3;
}
else {
sequence_generator(length - 1 - i) = 2;
}
}
return (constructor(sequence_generator) - length); // the 'tail' of the sequence is the total length ('j' of constructor) minus the length of the generator
}
// this function starts a thread and calls the decToBinary function for a range of sequences
void multi_threader(int thread_number, int thread_count) {
std::cout << "thread " << thread_number << " initiated!" << std::endl;
auto start_time = high_resolution_clock::now(); // timer to keep track of elapsed time of thread
int thread_tail = 0; // value to keep track of maximum tail length of this thread
unsigned long long start = (thread_number - 1) * pow(2, length) / (thread_count); // start value for this thread
unsigned long long stop = pow(2, length) / (thread_count)*thread_number; // end value for this thread
for (unsigned long long int i = start; i < stop; ++i) {
auto start2 = high_resolution_clock::now(); // partial timer start
int local_tail = decToBinary(i); // tail of this sequence
if (local_tail > thread_tail) { // if larger than any earlier tail in this sequence...
thread_tail = local_tail; // update its value
}
auto stop2 = high_resolution_clock::now(); // partial timer end
duur = duur + duration_cast<microseconds>(stop2 - start2).count(); // print elapsed partial time
}
{
std::lock_guard<std::mutex> l(m_tail); // lock 'tail' while editing
if (thread_tail > tail) { // if largest tail in this thread is larger than any thread before...
tail = thread_tail; // update the value
}
}
std::cout << duur / 1000 << std::endl;
auto stop_time = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop_time - start_time).count() / 1000;
std::cout << "thread " << thread_number << " exited, duration: " << duration << " ms, result " << thread_tail << std::endl;
}
// this function calls for as many threads as the user requests and passes the length the user requested on to the thread
void iterate_generator() {
std::vector<std::thread> thread_vector;
int thread_count, thread_number;
thread_number = 0;
std::cout << "enter the length for the sequence generator (e.g. 10, maximum 40)" << std::endl;
std::cin >> length;
length = 25; // example value
std::cout << "enter the desired number of threads (e.g. 2, maximum 4)" << std::endl;
std::cin >> thread_count;
thread_count = 4; //example value
// start the threads and join them
for (int i = 0; i < thread_count; ++i) {
++thread_number;
std::thread th = std::thread((thread_number, thread_count)() {multi_threader(thread_number, thread_count); });
thread_vector.push_back(std::move(th));
}
for (auto& th : thread_vector) { th.join(); }
}
int main() {
while (true) {
iterate_generator();
std::cout << tail << std::endl << std::endl;
}
}
```

Thanks in advance!!