C++

Forum

 
pointers factorial

adam2016 (1529)
hi guys,

I am using the GMP library to try and make a factorial that deals with very large results,

I am not finished yet,but hopefully close the problem that I identified is that I am using pointers not stack variables like the normal factorial algorithm,meaning there will be stack frames but these stack frames will be using pointers instead of local integers etc so if one stack frame changed the value of something pointed to by a pointer it will be the same in all stack frames I need to find a way around this,

anywho I get some weird output 

 5  4  3  2  1 retuning :
p one =  1
*n  1
*n  1
*n  1
*n  5


I understand that on each frame why *n equals one but I don't get why at the bottom frame *n equals 5,shouldn't it equal one? considering that it was modified in another stack frame??

thanks

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
 

#include <iostream>
#include <gmp.h>

using namespace std;

mpz_t* p_x;
mpz_t* p_one;
mpz_t x;
mpz_t y;
mpz_t* p_y;
mpz_t one;
mpz_t fact;
mpz_t* p_fact;
bool nInit = false;

// factorial small numbers

int factorial(int x){


   if( x <= 1){

      return 1;
   }
   return factorial(x-1) * x;
}

void initInts(){

  mpz_init(x);
  mpz_init(y);
  mpz_init(one);
  mpz_init(fact);

  mpz_set_str(one,"1",10);
  p_one = &one;

  mpz_set_str(x,"0",10);
  p_x = &x;

  mpz_set_str(y,"0",10);
  p_y = &y;

  mpz_set_str(fact,"0",10);
  p_fact = &fact;

}

// factorial big numbers

mpz_t* factorialBig(mpz_t* n){


    gmp_printf ("% Zd ", *n);
   if(mpz_cmp(*n,one) == 0){

      cout << "retuning :" << endl;
      cout << "p one = ";
      gmp_printf ("% Zd ", *p_one);
      cout << endl;

      return p_one;
   }

   mpz_sub(y,*n,one);

   factorialBig(p_y);

   mpz_mul(fact,*n,y);

   cout << "*n ";
   gmp_printf ("% Zd ", *n);
   cout << endl;
   return p_fact;

}

void callFactBig(char* str){

    mpz_set_str(x,str,10);
    factorialBig(p_x);
    //gmp_printf ("% Zd ", *factorialBig(x));

}


int main()
{
   initInts();
   callFactBig("5");

}
tpb (1495)
The pointer stuff is not needed. mpz_t already is a pointer, in a sense. It's an array. So if you pass it to a function you are just passing a pointer. And it's kind of pointless to write factorial recursively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#include <iostream>
#include <gmp.h>
using namespace std;

void fact(mpz_t n, mpz_t result) {
    mpz_set(result, n);
    mpz_sub_ui(n, n, 1);
    while (mpz_cmp_ui(n, 1) > 0) {
        mpz_mul(result, result, n);
        mpz_sub_ui(n, n, 1);
    }
}

int main() {
    mpz_t n, result;
    mpz_inits(n, result, NULL);
    mpz_set_ui(n, 5);

    fact(n, result);
    gmp_printf("result: %Zd\n", result);

    mpz_clears(n, result, NULL);
}

helios (17511)
It sounds to me like you're assuming some pretty bizarre semantics for local pointers in recursive functions.

Consider this code:
1
2
3
4
5
6
7
8
9
10
11
12
 
int *f(int n){
    int *m = new int(42);
    if (n == 0)
        return m;
    int *ret = f(n - 1);
    m = new int(24);
    return ret;
}

int g(){
    return *f(1);
}
Will g() return 42, or 24?

Also, why are you calculating factorials recursively?
1
2
3
4
5
6
 
int factorial(int n){
    int ret = 1;
    for (int i = 2; i <= n; i++)
        ret *= i;
    return ret;
}
Just translate that to GMP and be done with it.
Last edited on
adam2016 (1529)
thanks guys,

good point solving this problem recursively probably isn't the greatest idea but I've come this far so I'm going to try get it working lol,but yeah I will implement it using iteration after,

my code is horribly bloated so yeah the iteration method would be much cleaner and having 50 plus stack frames probably isn't very efficient but I'm determined to get this running

here is my code,the problem I am having is that now the program just prints 5 and then crashes before it can print any of my debugging outputs,

not sure why it just crashes?

Will g() return 42, or 24?


it should return 42,first m points to a new int on the heap with the value 42,next the int pointer ret is set to f(n-1) (f(0)) which returns m a pointer to 42,the stack frames then unwind m then points to a new int 24 on the heap this is done twice,and one allocation 24 is not properly deleted,

ret is still pointing to 42 so it will return a pointer to 42 on the heap,so the function g() will return 42 right?


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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
#include <iostream>
#include <sstream>
#include <gmp.h>

using namespace std;

mpz_t* p_x;
mpz_t* p_one;
mpz_t x;
mpz_t y;
mpz_t* p_y;
mpz_t one;
mpz_t fact;
mpz_t* p_fact;
stringstream ss;

// factorial small numbers

int factorial(int x){


   if( x <= 1){

      return 1;
   }
   return factorial(x-1) * x;
}

void initInts(){

  mpz_init(x);
  mpz_init(y);
  mpz_init(one);
  mpz_init(fact);

  mpz_set_str(one,"1",10);
  p_one = &one;

  mpz_set_str(x,"0",10);
  p_x = &x;

  mpz_set_str(y,"0",10);
  p_y = &y;

  mpz_set_str(fact,"0",10);
  p_fact = &fact;

}

// factorial big numbers


mpz_t* factorialBig(mpz_t* n,int strNum){


   gmp_printf ("% Zd ", *n);
   if(mpz_cmp(*n,one) == 0){

      cout << "retuning :" << endl;
      cout << "p one = ";
      gmp_printf ("% Zd ", *p_one);
      cout << endl;

      return p_one;
   }

   char* strTemp;

   ss << strNum;
   ss >> strTemp;

   mpz_t temp;
   mpz_init(temp);
   mpz_set_str(temp,strTemp,10);

   mpz_t tempTwo;
   mpz_init(tempTwo);
   mpz_set_str(tempTwo,strTemp,10);
   mpz_sub(tempTwo,temp,one);

   mpz_swap(*n,tempTwo);

    ss.str("");
    ss.clear();

   factorialBig(n,strNum);

   mpz_mul(fact,temp,tempTwo);

   cout << "*n ";
   gmp_printf ("% Zd ", fact);
   cout << endl;
   return p_fact;

}

void callFactBig(char* str,int num){

    mpz_set_str(x,str,10);
    factorialBig(p_x,num);
    //gmp_printf ("% Zd ", *factorialBig(x));

}



int main()
{
   initInts();
   callFactBig("5",5);
}
Last edited on
doug4 (1535)
and one allocation 24 is not properly deleted,


Actually, none of the allocations (42 or 24) are properly deleted. There are 4 3 ints allocated on the heap that are leaked when g() returns.
Last edited on
adam2016 (1529)
ok so I got a working big number factorial function(using iteration) I guess I am happy to get it working after spending more time than I would like to admit on it,although the code works it is still quite sloppy looking and probably too bloated.also I never really like using booleans in this way and using continue is probably not great practice either.


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
 

#include <iostream>
#include <sstream>
#include <gmp.h>

using namespace std;


stringstream ss;

// factorial small numbers

int factorial(int x){


   if( x <= 1){

      return 1;
   }
   return factorial(x-1) * x;
}


// factorial big numbers


void factorialBigIt(int n){

    int temp = n;

    char str[] = "";
    ss << temp;
    ss >> str;

    mpz_t a;
    mpz_init(a);
    mpz_set_str(a,str,10);

    mpz_t b;
    mpz_init(b);

    mpz_t resultTemp;
    mpz_init(resultTemp);

    ss.str("");
    ss.clear();

    bool firstTime = true;

    for(int i = n-1; i >= 1; i--){

       char strTemp[] = "";
       ss << i;
       ss >> strTemp;

       mpz_set_str(b,strTemp,10);


       if(firstTime){

       mpz_mul(resultTemp,a,b);
       firstTime = false;
       ss.str("");
       ss.clear();
       continue;

       }

       mpz_mul(resultTemp,b,resultTemp);

       ss.str("");
       ss.clear();
    }

   gmp_printf("% Zd ", resultTemp);

}

int main()
{

  // callFactBig("5",5);
   factorialBigIt(20);
}
Last edited on
adam2016 (1529)
*updated with memory management 

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
 

char* factorialBigIt(int n){

    int temp = n;

    char str[] = "";
    ss << temp;
    ss >> str;

    mpz_t a;
    mpz_init(a);
    mpz_set_str(a,str,10);

    mpz_t b;
    mpz_init(b);

    mpz_t resultTemp;
    mpz_init(resultTemp);

    ss.str("");
    ss.clear();

    bool firstTime = true;

    for(int i = n-1; i >= 1; i--){

       char strTemp[] = "";
       ss << i;
       ss >> strTemp;

       mpz_set_str(b,strTemp,10);


       if(firstTime){

       mpz_mul(resultTemp,a,b);
       firstTime = false;
       ss.str("");
       ss.clear();
       continue;

       }

       mpz_mul(resultTemp,b,resultTemp);

       ss.str("");
       ss.clear();
    }

   char *resultStr = new char[100000];
   mpz_get_str(resultStr,10,resultTemp);

   delete [] str;
   mpz_clear(a);
   mpz_clear(b);
   mpz_clear(resultTemp);

   return resultStr;
}


I'm sure there has to be a much more elegant way of writing that function
helios (17511)
Why are you using mpz_set_str() instead of mpz_set_ui()?
What if the string from mpz_get_str() needs more than 100,000 characters?
adam2016 (1529)
Why are you using mpz_set_str() instead of mpz_set_ui()?
What if the string from mpz_get_str() needs more than 100,000 characters?


whats the difference? what does ui stand for,I thought setting using the str version would allow for larger numbers
tpb (1495)
The following makes a char array of size 1 initialized with the value 0.
 
 
    char str[] = "";

And you certainly can't delete it:
 
 
    delete [] str;

There's so many little things that don't make sense. What is temp for? Why not just use n? Why would you convert i to a string and then load b from the string when you could just load it from i (mpz_set_si or mpz_set_ui).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#include <iostream>
#include <gmp.h>

char* fact(int n){
    mpz_t result;
    mpz_init_set_si(result, n);
    while (--n > 1)
        mpz_mul_si(result, result, n);
    char *resultStr = mpz_get_str(NULL, 10, result);
    mpz_clear(result);
    return resultStr;
}

int main() {
    char *s = fact(100);
    printf("%s\n", s);
    free(s);
    return 0;
}

Last edited on
Topic archived. No new replies allowed.