How can I convert this C++ function from using long to this other type?

Question

I have this original C++ function called "s":

long s(long n) {
  long sum = 0;
  long m;

  m = (long) sqrt(n);
  for (long i = 2; i < m; i++)
    if ((n % i) == 0) sum += (i + (n/i));
  if (n>1) sum += 1;
  if ((m*m) == n) sum += m;
  return sum;
}

I've been struggling to convert this function over to using the GMP's mpz type, so that it will allow for arbitrarily long integers.

This is my attempt at it:

void s(mpz_t n, mpz_t *final)
{
    mpz_t sum;
    mpz_t m;
    mpz_t temp;

    mpz_init (sum);
    mpz_init (m);
    mpz_init (temp);

    mpz_set_str (sum, "0", 10);

    mpz_sqrt(m, n);
    for (mpz_t i, mpz_init(i), mpz_set_str(i, "2", 10); mpz_cmp(i,m)< 0; mpz_add_ui(i, i, 1))
    {
        mpz_mod(temp, n, i);
        if (mpz_cmp_si(temp, 0) == 0)
        {
            // use divexact since we know they are divisable
            mpz_divexact(temp, n, i);
            mpz_add(temp, temp, i);
            mpz_add(sum, sum, temp);
        }
    }

    if (mpz_cmp_si(n, 1) > 0) mpz_add_ui(sum, sum, 1);

    mpz_mul(temp, m, m);
    if (mpz_cmp(temp, n) == 0) mpz_add(sum, sum, m);
    final = sum;
}

The whole original program can be found here: http://pastebin.com/mf751592

What am I doing wrong? I seemed to initially have trouble because I couldn't return type mpz_t. So instead, I passed in a pointer to what I want the function to return.

I'm still struggling with it though. Can someone point me in the right direction?

This line: for (mpz_t i, mpz_init(i), mpz_set_str(i, "2", 10); mpz_cmp(i,m)< 0; mpz_add_ui(i, i, 1))
Gives this error: 23: error: cannot initialize arrays using this syntax

Answer 1

Try using templates

template <class myType>
myType s(myTypen) {
myType sum = 0;
myType m;

m = (myType) sqrt(n);
for (myType i = 2; i < m; i++)
  if ((n % i) == 0) sum += (i + (n/i));
 if (n>1) sum += 1;
if ((m*m) == n) sum += m;
return sum;
}

Answer 2

Your last line should be *final = sum; Otherwise you change the address to which your pointer points.

Or use reference instead :)

Answer 3

You were mostly on the right track. However, both function parameters should be of type mpz_t. So the header's like:

void s(mpz_t n, mpz_t final)

You don't need final = sum at the end. Instead, just use final everywhere you use sum. Also, do:

mpz_t i;
for (mpz_init_set_ui(i, 2); mpz_cmp(i,m) < 0; mpz_add_ui(i, i, 1))

for the for loop. A call is like:

mpz_t final, n;
mpz_init(final);
mpz_init_set_ui(n, 5);
s(n, final);

EDIT: As noted by Steve314, you should do a mpz_clear for every mpz_init. Since you can have the caller pass an initted final, that leaves cleaning up m, temp, and i.

Answer 4

Just declare and initialize i before the for loop instead..

mpz_t i;
mpz_init(i);
mpz_set_str(i, "2", 10);

for (; mpz_cmp(i,m)< 0; mpz_add_ui(i, i, 1)) {
   ...
}

Answer 5

gmp is a pure C library, IIRC.

Areas of concern include a lack of cleanups of the mpz_t variables (no destructors in C), and the use of the assignment operator in the last line (no overloaded operators in C - this is effectively a POD memcpy). IIRC, mpz_clear is the integer cleanup function.

Replace the assigment with either mpz_set or mpz_swap - swap being more efficient if you're about to delete the temporary as it avoids copying underlying data structures.

Still, all that would really explain is memory leakage.

My next area of suspicion would be the calls where the same variable is used both as an input and an output. I don't know about gmp, but a lot of libraries don't like this when passing pointers - the input parameter gets changed while being used (since it is also the output), causing corruption. A few extra temporaries may be needed.