-2

I think have worked out a solution for finding the largest Collatz Sequence below a LIMIT but it takes a lot of time! My question really is where the source for this would be: code, software, hardware?

I have done some research on the Internet and have seen people doing it pretty much the same way with runtimes around 2000ms. Whereas my computer does not even come that far! I'm using Visual Studio, C++. Btw, after debugging it can be seen that the calculation suddenly (stops, struggles, hangsup?) when determining the sequence of 113383.

Here is my little code snippet:

(The parts with map and the first if are possible additions I thought could speed up the whole process but don't. If I leave them out its the same speed-wise)

#include <iostream>
#include <set>
#include <map>

using namespace std;

#define LIMIT 1234567

int main()
{
    int n = 0;
    int compare = 0;
    int longest = 0;
    int counter = 1;
    set <int> nums2excl;
    map <int, int> mappi;
    map <int, int>::const_iterator itMap = mappi.begin();

    for (int i = 13; i < LIMIT; i++)
    {
        if (nums2excl.find(i) != nums2excl.end())
        {
            continue;
        }

        n = i;

        while (n != 1)
        {
            itMap = mappi.find(n);
            if (itMap != mappi.end())
            {
                counter += ((*itMap).second - 1);
                break;
            }

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

                if (n > i)
                {
                    nums2excl.emplace(n);
                }
            }

            counter++;
        }

        mappi.emplace(i, counter);

        if (counter > compare)
        {
            compare = counter;
            longest = i;

            //Test
            cout << i << endl;
        }

        counter = 1; 
    }

    return 0;
}

Now, am I missing some mistakes in the code, mistakes regarding efficiency or is my laptop just too slow for this?

Petersson
  • 1
  • 1
  • 5
    Did you compile with optimizations enabled (in release mode)? – Algirdas Preidžius May 10 '19 at 17:20
  • 2
    `-O3` or debug code? – tadman May 10 '19 at 17:21
  • 2
    You lack a [mcve]. There are variables used that you don't have definitions for, the code is part of a larger function, and we don't know how it is being called or used. [Edit] your question to include enough code so we can determine what you're doing. (Don't forget to include the compiler and compiler options.) – 1201ProgramAlarm May 10 '19 at 17:25
  • If you tested an unoptimized debug build, all bets are off. It's going to be slow. Before drawing any conclusions, test a build where you have actually enabled the compilers optimizer - if it's still slow, tell us and then we can maybe suggest something. – Jesper Juhl May 10 '19 at 17:39
  • Thank you for your response first of all! Yes, I've tested a build with optimizations enabled and mode set to release. It does work a little faster but still does not reach the end of the program. – Petersson May 10 '19 at 17:48
  • does it work for small values? If not then it's a bug. Debug and fix it – phuclv May 11 '19 at 01:45
  • Yes it works correctly for small values. – Petersson May 11 '19 at 08:40

1 Answers1

0

n needs to be of larger data type, long long solved it.

Petersson
  • 1
  • 1
  • You may be interested in https://stackoverflow.com/questions/199333/how-do-i-detect-unsigned-integer-multiply-overflow – DaBler Aug 06 '19 at 12:44