Charactar array size overflow

joshky (87)
I have been working through some of the problems on project Euhler. My problem is not about the math, but character arrays. The problem is to find the largest sum of digitsd for a value of a to the b power. Here is my 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
51
52
53
54
55
56
57
58
59
 
#include<gmp.h>
#include<gmpxx.h>
#include<iostream>
#include<cstring>
#include<vector>

using namespace std;
int main(){
    mpz_t a;
    mpz_init(a);
    string str;
    char * c;
    int size;
    vector<int> vec;
    unsigned long b;
    mpz_t eachans;
    mpz_init(eachans);
    mpz_t anssum;
    mpz_init(anssum);
    mpz_t temp;
    mpz_t anstemp;
    mpz_init(anstemp);
    mpz_set_ui(anstemp,0);
    mpz_init(temp);
    for(mpz_set_ui(a,1);mpz_cmp_ui(a,100)<0;mpz_add_ui(a,a,1)){
                       for(b=1;b<100;++b){
                                          cout<<"\nb: "<<b<<"   a:  ";
                                          mpz_out_str(NULL,10,a);
                                          mpz_pow_ui(eachans,a,b);
                                          cout<<endl;
                                          size=mpz_out_str(NULL,10,eachans);
                                          c=new char[size];
                                          mpz_get_str(c,10,eachans);
                                          mpz_set_ui(anssum,0);
                                          for(int i=0;i<size;++i){
                                                   str=c[i];
                                                   mpz_set_str(temp,str.c_str(),10);
                                                   mpz_add(anssum,anssum,temp);                         
                                                   }
                                          if(mpz_cmp(anssum,anstemp)>0){
                                                                        mpz_set(anstemp,anssum);
                                                                        }
                                                                        }
                                                                        }
                                          cout<<endl<<"your answer: "<<endl;
                                          mpz_out_str(NULL,10,anstemp);
                                                                        
                                                                                        
                                          
                                          
    
    
    
    
    
                                                 system("pause");
                                                 return 0;

}


My problem is on line 32, where the character array is declared with size of the number I need to import to string format. When the program reaches a certain point I get an overflow I am assuming due to the fact that there are too many digits in the number to be stored in the character array. Suggestions?
PanGalactic (1658)
You continue to allocate with new, assigning it to c, but I see no corresponding delete. This is a memory leak. If the numbers are large enough, this will cause a failure. Granted, the code formatting makes it a bit hard to follow so I may be missing it.
helios (17607)
100^100 contains 201 decimal digits, so no, that can't be the problem.

Check that size>0, although my guess is that you're messing up with some GMP call.

Oh, and two more things: you're never deleting c, and you don't need arbitrary precision to calculate the sum of 200 numbers below 10.
PanGalactic (1658)
The short answer: size=mpz_out_str(NULL,10,eachans); is broken. It does not account for the NUL terminator. Use mpz_sizeinbase(x, 10) + 2; as the gmp docs suggest.


helios (17607)
Ah-ha! I knew it!
joshky (87)
TY pangalactic, I was using the wrong function. Answer is still wrong, but the program runs, am debugging now. TY again.
joshky (87)
OK, now the program gi9ves a different reslt ranging each time it is run from 1013 to 1025, usually 1019 (which is not the answer)????? Is this due to how GMP deals with the big numbers? Here is the edited 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
#include<gmp.h>
#include<gmpxx.h>
#include<iostream>
#include<cstring>
#include<vector>

using namespace std;
int main(){
    mpz_t a;
    mpz_init(a);
    string str;
    char * c;
    int size;
    vector<int> vec;
    unsigned long b;
    mpz_t eachans;
    mpz_init(eachans);
    mpz_t anssum;
    mpz_init(anssum);
    mpz_t temp;
    mpz_t anstemp;
    mpz_init(anstemp);
    mpz_set_ui(anstemp,0);
    mpz_init(temp);
    for(mpz_set_ui(a,1);mpz_cmp_ui(a,100)<0;mpz_add_ui(a,a,1)){
                       for(b=1;b<100;++b){
                                         // cout<<"\nb: "<<b<<"   a:  ";
                                         // mpz_out_str(NULL,10,a);
                                          mpz_pow_ui(eachans,a,b);
                                          //cout<<endl;
                                          size=mpz_sizeinbase(eachans, 10) + 2;
                                          c=new char[size];
                                          mpz_get_str(c,10,eachans);
                                          delete c;
                                          mpz_set_ui(anssum,0);
                                          
                                         // delete c;
                                          for(int i=0;i<size;++i){
                                                   str=c[i];
                                                   mpz_set_str(temp,str.c_str(),10);
                                                   mpz_add(anssum,anssum,temp); 
                                                                          
                                                   }
                                                   
                                          if(mpz_cmp(anssum,anstemp)>0){
                                                                        mpz_set(anstemp,anssum);
                                                                         cout<<"\nresult of "<<b<<"  and ";
                                                   mpz_out_str(NULL,10,a);
                                                                        }
                                                                        }
                                                                        }
                                          cout<<endl<<"your answer: "<<endl;
                                          mpz_out_str(NULL,10,anstemp);
                                                                        
                                                                                        
                                          
                                          
    
    
    
    
    
                                                 system("pause");
                                                 return 0;

}
Last edited on
PanGalactic (1658)
Might I suggest using the STL to prevent some of your issues? This is basically your algorithm, cleaned up, commented, and using the STL.

In your code, you delete c before you are done using it. My guess is that something is reallocating that memory for other purposes and clobbering your number.

A vector of characters is much easier to deal with and not prone to these sorts of problems.

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
 
// Public domain.

#include <gmp.h>
#include <gmpxx.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>

/// Convert a character to its integer value. e.g. '9' -> 9.
struct lexical_value : public std::unary_function<unsigned char, int>
{
    int operator()(unsigned char c)
    {
        c -= '0';
        return c < 10 ? c : 0;
    }
};

int main()
{
    mpz_t x;
    mpz_init(x);
   
    int final = 0;

    for(size_t a = 1; a < 100; ++a)
    {
        for(size_t b = 1; b < 100; ++b)
        {
            // Write out the equation.
            std::cout << a << " ^ " << b << " = ";

            // Compute.
            mpz_ui_pow_ui(x, a, b);

            // Get the string length (plus optional sign and
            // NUL terminator).
            size_t size = mpz_sizeinbase(x, 10) + 2;

            // Allocate buffer and get the results.
            std::vector<char> output(size);
            mpz_get_str(&(output[0]), 10, x);
            
            // Write the equation results.
            std::cout << &(output[0]) << std::endl;

            // Allocate the vector.
            std::vector<int> temp(size);

            // Assign lexical values from vector<char> to vector<int>.
            std::transform(output.begin(), output.end(), temp.begin(),
                lexical_value());

            // Sum the digits.
            int result = std::accumulate(temp.begin(), temp.end(), 0);

            // Pick the biggest sum so far.
            final = std::max(result, final);
        }
    }

    std::cout << "Result: " << final << std::endl;
    
    return 0;
}
joshky (87)
thank you very much, i can see how setting the array, then performing more calculations could change part of the array. Your way worked great. thanks.
Topic archived. No new replies allowed.