C++ Гипотеза Коллатца Оптимизация

У вас есть несколько небольших проблем:

1. Я совершенно уверен, что вы переполняете тип данных int. Используйте uint64_t, чтобы сделать это менее вероятным.
2. Вы должны обновлять только superI и superN вне цикла while. Это не должно иметь значения, но это вредит производительности.
3. На каждой итерации вы должны изменять x только один раз. В настоящее время вы можете изменить его дважды, что может привести к тому, что вы попадете в бесконечный цикл. И ваш расчет n тоже будет неверным.
4. Используйте запоминание для повышения производительности за счет кэширования старых результатов.

Применяя это, вы могли бы придумать такой код:

#include <cstdint>
#include <iostream>
#include <map>
using namespace std;

int main()
{
    uint64_t i;
    uint64_t x;
    uint64_t n;
    uint64_t superN;
    uint64_t superI;

    std::map<uint64_t, uint64_t> memory;

    superN = 0;
    superI = 0;

    for (i = 1; i <= 1000000; i++) {
        x = i;
        n = 1;

        do {
            if (memory.find(x) != memory.end()) {
                n += memory[x];
                break;
            }

            if (x % 2 == 0) {
                x = x / 2;
            } else {
                x = 3 * x + 1;
            }

            n++;
        } while (x != 1);

        if (n > superN) {
            superN = n;
            superI = i;
        }

        memory[i] = n;
    }

    cout << "The number " << superI << " ran for " << superN << " terms.\n";
    system("pause");
    return 0;
}

Что занимает 4 секунды для вывода:

The number 837799 ran for 556 terms.

Я бы посоветовал не использовать мемоизацию, так как для меня она работает медленнее; в моем случае (до 10 000 000) код ниже работает быстрее без мемоизации. основные изменения:

1. только проверка того, является ли текущий номер даже один раз (не требуется else-if).
2. используя побитовую операцию вместо операции по модулю (немного быстрее)

Кроме того, я не знаю, почему ваш код такой длинный (мой меньше 200 миллисекунд), может быть, вы компилируете как отладку?

bool isEven(uint64_t value)
{
    return (!(value & 1));
}

uint64_t solveCollatz(uint64_t start)
{
    uint64_t counter = 0;
    while (start != 1)
    {
        if(isEven(start))
        { 
            start /= 2;
        }
        else
        {
            start = (3 * start) + 1;
        }
        counter++;
    }

    return counter;
}

Если вы можете использовать встроенные функции компилятора, особенно с подсчетом и удалением завершающих нулей, вы поймете, что вам не нужно ветвление в основном цикле, вы всегда будете чередовать нечетные и четные числа. Методы запоминания, которые были представлены ранее, редко будут замыкать накоротко вокруг математики, которую вы делаете, поскольку мы имеем дело с числами градины — кроме того, у большинства чисел есть только одна точка входа, поэтому, если вы видите их один раз, вы больше никогда их не увижу.

В GCC это будет выглядеть примерно так:

#include <cstdint>
#include <iostream>
#include <unordered_map>
#include <map>
using namespace std;

using n_iPair = std::pair<uint32_t, uint64_t>;

auto custComp = [](n_iPair a, n_iPair b){
  return a.first < b.first;
};

int main()
{
    uint64_t x;
    uint64_t n;
    n_iPair Super = {0,0};

    for (auto i = 1; i <= 1000000; i++){
        x = i;
        n = 0;

        if (x % 2 == 0) {
          n += __builtin_ctz(x); // account for all evens
          x >>= __builtin_ctz(x); // always returns an odd
        }

         do{ //when we enter we're always working on an odd number

          x = 3 * x + 1; // always increases an odd to an even
          n += __builtin_ctz(x)+1; // account for both odd and even transfer
          x >>= __builtin_ctz(x); // always returns odd

        }while (x != 1);

        Super = max(Super, {n,i}, custComp);

    }

    cout << "The number " << Super.second << " ran for " << Super.first << " terms.\n";
    return 0;
}

Если производительность критична, а память — нет, вы можете использовать кэширование для повышения скорости.

#include <iostream>
#include <chrono>
#include <vector>
#include <sstream>

std::pair<uint32_t, uint32_t> longestCollatz(std::vector<uint64_t> &cache)
{
    uint64_t length = 0;
    uint64_t number = 0;

    for (uint64_t current = 2; current < cache.size(); current++)
    {
        uint64_t collatz = current;
        uint64_t steps = 0;
        while (collatz != 1 && collatz >= current)
        {
            if (collatz % 2)
            {
                // if a number is odd, then ((collatz * 3) + 1) would result in
                // even number, but even number can have even or odd result,  so
                // we can combine two steps for even number, and increment twice.
                collatz = ((collatz * 3) + 1) / 2;
                steps += 2;
            }
            else
            {
                collatz = collatz / 2;
                steps++;
            }
        }

        cache[current] = steps + cache[collatz];

        if (cache[current] > length)
        {
            length = cache[current];
            number = current;
        }
    }
    return std::make_pair(number, length);
}

int main()
{
    auto start = std::chrono::high_resolution_clock::now();;

    uint64_t input = 1000000;
    std::vector<uint64_t> cache(input + 1);
    auto longest = longestCollatz(cache);

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "Longest Collatz (index : value) --> " << longest.first << " : " << longest.second;
    std::cout << "\nExecution time: " << duration << " milliseconds\n";

    return EXIT_SUCCESS;
}