*.exe has stopped working

Hi,

I am new to C++ coding. Wrote c++ code to calculate LCM of series of integers. Below is the code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
  #include <iostream>
#include <vector>
#include <list>

int gcd_2_ints(int a,int b){
	if (a==0||b==0){
		return 0;
	}
	else {
			if (a==b){
			return a;
		}
		else if (a>b){
			return gcd_2_ints(a-b,b);
		}
		else{
			return gcd_2_ints(a,b-a);
		}
	}

}

int lcm_2_ints(int a, int b){
	int x=a*b;
	return (x/gcd_2_ints(a,b));
}

int lcm_series_of_numbers(std::vector<int> vect){
	if(vect.size()==2){
		return lcm_2_ints(vect[0],vect[1]);
	}
	else{
		int first_elm=vect[0];
		std::vector<int> rest_of_the_vector;
		for (unsigned int i=1;i<vect.size();i++){
			rest_of_the_vector.push_back(vect[i]);
		}
		int ans=lcm_series_of_numbers(rest_of_the_vector);
		return lcm_2_ints(first_elm,ans);
	}
}



int main(){

	std::cout<<lcm_series_of_numbers({1,2,3,4,5,6,7,8,9,10,11,12,13})<<std::endl;
}




It works fine till 12 numbers but for 13 or more as above, it throws error

*.exe is not working. Windows is trying to solve the problem.
Last edited on
put a print here
if (a==0||b==0){
cout << "about to divide by zero" << endl;
return 0;

and let me know if that helps? I don't see anything else yet.
> put a print here
please, no.
start using a debugger.


run throught a debugger and look at the call stack, it's huge.
that's your problem, the return gcd_2_ints(a,b-a); recursion is too slow, it takes too many steps to reach the base case.
so you may increase the stack size, change to an iterative version, or to a better recursive algorithm (like using the remainder)
The recursion depth of gcd_2_ints(a,b) is too high when a is small and b is very large.

Rewrite it as
1
2
3
4
5
int gcd_2_ints( int a, int b ) {

    if (b == 0) return a;
    else return gcd_2_ints( b, a%b );
}

and you would be able to go further.

Till int x=a*b; in lcm_2_ints results in signed integer overflow.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <limits> // *** added

int gcd_2_ints( int a, int b ) { // *** rewritten

    if (b == 0) return a;
    else return gcd_2_ints( b, a%b );
}

int lcm_2_ints(int a, int b) {

    // *** added 
    const long long check = (long long)a * b;
    if( check > std::numeric_limits<int>::max() ) {

        std::cerr << "lcm_2_ints: " << a << ' ' << b << " signed integer overflow\n" << std::flush;
        return 0;
    }

    int x = a * b;
    return (x / gcd_2_ints(a, b));
}

int lcm_series_of_numbers(std::vector<int> vect) {

    if (vect.size() == 2) {

        return lcm_2_ints(vect[0], vect[1]);
    }
    else {

        int first_elm = vect[0];
        std::vector<int> rest_of_the_vector;
        for (unsigned int i = 1; i<vect.size(); i++) {

            rest_of_the_vector.push_back(vect[i]);
        }
        int ans = lcm_series_of_numbers(rest_of_the_vector);
        return lcm_2_ints(first_elm, ans);
    }
}



int main() {

    std::cout << lcm_series_of_numbers({ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 }) << '\n' ;
}

http://coliru.stacked-crooked.com/a/7d81931ed387568c

Signed integer overflow: http://coliru.stacked-crooked.com/a/d81927036f61b04f
Amazing !!

Thanks guys for taking out time.

Now the problem makes more sense to me.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <cmath>
#include <vector>
#include <limits>
#include <algorithm>
using namespace std;

using INT = int;
// using INT = unsigned long long;

//============================

vector<INT> factorise( INT n )    // Factorise n ( > 1 ) into prime factors in ascending order
{
   vector<INT> factors;
   INT kmax = sqrt( n ) + 1;      // If it gets here without factors then n must be prime

   while ( n % 2 == 0 )           // Remove any factors of 2 (the only even prime)
   {
      factors.push_back( 2 );
      n /= 2;
   }

   INT k = 3;                     // Remaining checks are 3, 5, 7, ...
   while ( n > 1 )
   {
      if ( n % k != 0 )
      {
         k += 2;                  // If not a factor, move to next odd number
      }
      else
      {
         factors.push_back( k );
         n /= k;                  // Remove this prime factor before testing again
      }

      if ( k >= kmax && factors.size() == 0 )
      {
         factors.push_back( n );  // The case where n is prime - no further searching needed
         break;
      }
   }

   return factors;
}

//============================

void printFactors( const vector<INT> &V )
{
   INT maximum = numeric_limits<INT>::max();

   bool ok = true;
   INT product = 1;
   for ( unsigned int i = 0; i < V.size(); i++ )
   {
      cout << V[i];
      if ( i < V.size() - 1 ) cout << "x";

      if ( ok && product < (double) maximum / V[i] ) product *= V[i];
      else ok = false;
   }

   if ( ok ) cout << " = " << product << '\n';
   else      cout << " = number too big for this type\n";
}

//============================

int main()
{
   INT NMAX = 25;
   vector<INT> numbers;
   for ( INT n = 2; n <= NMAX; n++ ) numbers.push_back( n );

   vector<INT> LCM;
   for ( unsigned int n = 0; n < numbers.size(); n++ )
   {
      vector<INT> nfactors = factorise( numbers[n] );
      for ( INT i : nfactors )                                       // Remove common prime factors
      {
         auto pos = find( LCM.begin(), LCM.end(), i );
         if ( pos != LCM.end() ) LCM.erase( pos );
      }
      for ( INT i : nfactors ) LCM.push_back( i );                   // Combine with new prime factors
      sort( LCM.begin(), LCM.end() );

      cout << "LCM{";                                                // Print out
      for ( unsigned int i = 0; i < n; i++ ) cout << numbers[i] << ",";
      cout << numbers[n] << "} = ";
      printFactors( LCM );
   }
}

//============================ 

LCM{2} = 2 = 2
LCM{2,3} = 2x3 = 6
LCM{2,3,4} = 2x2x3 = 12
LCM{2,3,4,5} = 2x2x3x5 = 60
LCM{2,3,4,5,6} = 2x2x3x5 = 60
LCM{2,3,4,5,6,7} = 2x2x3x5x7 = 420
LCM{2,3,4,5,6,7,8} = 2x2x2x3x5x7 = 840
LCM{2,3,4,5,6,7,8,9} = 2x2x2x3x3x5x7 = 2520
LCM{2,3,4,5,6,7,8,9,10} = 2x2x2x3x3x5x7 = 2520
LCM{2,3,4,5,6,7,8,9,10,11} = 2x2x2x3x3x5x7x11 = 27720
LCM{2,3,4,5,6,7,8,9,10,11,12} = 2x2x2x3x3x5x7x11 = 27720
LCM{2,3,4,5,6,7,8,9,10,11,12,13} = 2x2x2x3x3x5x7x11x13 = 360360
LCM{2,3,4,5,6,7,8,9,10,11,12,13,14} = 2x2x2x3x3x5x7x11x13 = 360360
LCM{2,3,4,5,6,7,8,9,10,11,12,13,14,15} = 2x2x2x3x3x5x7x11x13 = 360360
LCM{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16} = 2x2x2x2x3x3x5x7x11x13 = 720720
LCM{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17} = 2x2x2x2x3x3x5x7x11x13x17 = 12252240
LCM{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18} = 2x2x2x2x3x3x5x7x11x13x17 = 12252240
LCM{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19} = 2x2x2x2x3x3x5x7x11x13x17x19 = 232792560
LCM{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20} = 2x2x2x2x3x3x5x7x11x13x17x19 = 232792560
LCM{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21} = 2x2x2x2x3x3x5x7x11x13x17x19 = 232792560
LCM{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22} = 2x2x2x2x3x3x5x7x11x13x17x19 = 232792560
LCM{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23} = 2x2x2x2x3x3x5x7x11x13x17x19x23 = number too big for this type
LCM{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24} = 2x2x2x2x3x3x5x7x11x13x17x19x23 = number too big for this type
LCM{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25} = 2x2x2x2x3x3x5x5x7x11x13x17x19x23 = number too big for this type

The original does crash if you put in the same value twice, like {10,10}, FYI. The re-write does not of course.
Topic archived. No new replies allowed.