How can I make this program faster?

Question

#include <chrono>
#include <cstring>
#include <exception>
#include <iostream>

using namespace std;
#define ULL unsigned long long

#define SZARRAY 0xdffffff
ULL* memo = nullptr;

ULL maxLen(ULL n) {
  if (n == 1) {
    return 1;
  }
  if (n < SZARRAY && memo[n] > 0) {
    return memo[n];
  }
  ULL res = 0;
  if (n & 1) {
    res = maxLen(n * 3 + 1) + 1;
  } else {
    res = maxLen(n >> 1) + 1;
  }
  if (n < SZARRAY) {
    memo[n] = res;
  }
  return res;
}

int main(void) {
  try {
    memo = new ULL[SZARRAY]();

    int t;
    cin >> t;
    while (t--) {
      ULL l, r;
      cin >> l >> r;
      ULL init = r - l;
      ULL il = l;
      auto start = chrono::duration_cast<chrono::microseconds>(
          chrono::system_clock::now().time_since_epoch());
      ULL best = 0;
      ULL bn = 0;
      for (; l <= r; ++l) {
        if (l == 0) {
          continue;
        }
        ULL n = maxLen(l);
        if (n > best) {
          bn = l;
          best = n;
        }
        if (l % 10000000 == 0) {
          ::std::cout << "On iteration " << l - il << " of " << init << "; "
                      << (l - il) * 100 / init << "% done." << "\n";
        }
      }
      cout << bn << " has a length of " << best << "\n";
      auto end = chrono::duration_cast<chrono::microseconds>(
          chrono::system_clock::now().time_since_epoch());

      cout << "TIME (seconds): " << (double)((end - start).count())/1000000 << "\n";
    }
  } catch (const std::exception& e) {
    delete[] memo;
    cerr << "Exception caught: " << e.what() << endl;
    return 1;
  }

  delete[] memo;
  return 0;
}

Answer 1

You use a cache (memo) and use shifting instead of division. The code is reasonably fast enough.

You could probably seed if up by writing it in assembly, but the question is how much extra speed you need and how much trouble are you willing to go through for it.

You could do a slight optimization by removing the n == 1 check and instead adding memo[1] = 1 during the initialization. One less branching for the code to do. :)

For correctness, you should check for any overflow happening during your calculations. Have a look at this thread: https://stackoverflow.com/questions/199333/how-do-i-detect-unsigned-integer-overflow, especially to the answer where <stdckdint.h> is mentioned. I am not sure though, if that's available on OnlineGDB yet.

I do not remember the maths behind this. What is this problem called?

Is this like an unsolved problem where we do not know if there will be a loop ever or something? If not, you could just build from the other way around: start multiplying by 2 (number *= 2) until you find a number where (number - 1) % 3 == 0 and then you perform the reduction: number = (number - 1) / 3. The largest number you can find like this should have the longest string of operations, right? So you do not have to try all the numbers from A to B. :)

Never mind, that does not work as the algorithm cannot guarantee that there won't be any smaller numbers if you keep going with the calculations, so one cannot just stop as soon as one finds a number larger than a defined maximum.

Comments

This is called the Collatz Conjecture or 3x+1. The conjecture is that if all numbers eventually end up at 1 or not, and it is unsolved. https://en.wikipedia.org/wiki/Collatz_conjecture.

---

Thanks, I knew I've heard of this before. :)

---

https://en.wikipedia.org/wiki/Collatz_conjecture has a section called "Optimizations". It may be worth looking at it as well as the "shortcut" version mentioned in the same article.