Mike Warren - 3 months ago 13

C++ Question

I have

`Integer`

`Integer::Integer(int x)`

: m(x), n(0)

{

}

Integer::Integer(int x, int y)

: n(y), m(x)

{

// if this->n greater than 1

if (this->n > 1)

{

// mod this->m by this->n

this->m %= this->n;

// if this->m is negative

if (this->m < 0)

{

// add this->n to it

this->m += this->n;

}

}

}

There is also

`Integer::inverse()`

`Integer::pow(int)`

`Integer Integer::inverse()`

{

// Extended Euclidean Algorithm

int t = 0,

r = this->n,

newT = 1,

newR = this->m;

while (newR != 0)

{

int quotient = r / newR,

tCopy = t,

rCopy = r,

newTCopy = newT,

newRCopy = newR;

t = newT;

newT = tCopy - quotient * newTCopy;

r = newR;

newR = rCopy - quotient * newRCopy;

}

if (r > 1)

{

throw Integer(-1);

}

if (t < 0) t = t + this->n;

return Integer(t, this->n);

}

Integer Integer::squared()

{

return Integer(this->m * this->m, this->n);

}

Integer Integer::pow(int x)

{

// if x less than 0, return this->inverse().pow(-x)

if (x < 0) return this->inverse().pow(-x);

// if x is 0, return Integer(1)

if (x == 0) return Integer(1, this->n);

// if x is 1, return *this

if (x == 1) return *this;

// if x is 2, return this->squared()

if (x == 2) return this->squared();

// if x greater than 2

if (x > 2)

{

// if x is even

if (x % 2 == 0)

{

// return this->pow(x/2).squared()

return this->pow(x/2).squared();

}

// return this->pow(x/2).squared() * (*this)

return this->pow(x/2).squared() * (*this);

}

}

Problem I'm having is when I go to implement

`Integer::isQuadraticResidue() const`

`bool Integer::isQuadraticResidue() const`

{

// if this->n is zero

if (this->n == 0)

{

// this doesn't belong to Integers mod anything. check for perfect square instead

double baseSquareRoot = std::sqrt((double)this->m);

return (baseSquareRoot == (double)((int)baseSquareRoot));

}

// this is quadratic residue iff this->pow((this->n + 1) / 2) == Integer(1, this->n)

return (this->pow((n + 1) / 2).m == 1);

}

I get following error:

`error: passing ‘const Integer’ as ‘this’ argument of ‘Integer Integer::pow(int)’ discards qualifiers`

`const`

EDIT: Class header file looks something like:

`#ifndef INTEGER_H`

#define INTEGER_H

#include <iostream>

class Integer

{

public:

Integer(int);

Integer(int, int);

// functions

Integer inverse();

Integer squared();

Integer pow(int);

bool isQuadraticResidue() const;

Integer sqrt();

private:

int m, n;

};

#endif

Answer

This is an issue with `const`

correctness, where a `const`

function is trying to call a non-`const`

function.

```
// ...
bool Integer::isQuadraticResidue() const;
Integer Integer::pow(int x);
// ....
```

In this situation, `this`

is an `Integer*`

in `pow()`

, and a `const Integer*`

in `isQuadraticResidue()`

; this means that `pow()`

can call `isQuadraticResidue()`

, because it's legal to add CV-qualifiers, but not the other way around (because `pow()`

would have to accept `this`

as a non-qualified `Integer*`

, losing the `const`

qualifier).

This is unallowed, because allowing it would mean that `isQuadraticResidue()`

breaks its guarantee that it won't modify the instance, whether directly or indirectly. While it itself doesn't change state, it assumes that `pow()`

*does* change state, because `pow()`

isn't also `const`

(and thus doesn't promise not to change state). Due to this, `isQuadraticResidue()`

is unable to call `pow()`

, because doing so would risk breaking its guarantee.

Considering that, there are two solutions for this issue.

- Remove
`const`

from`isQuadraticResidue()`

. This would naively solve the problem, but isn't recommended, because then you wouldn't be able to reap the benefits of`const`

correctness. Make all member functions that don't modify

`Integer`

's logical state`const`

, as well. This will require a bit more effort, but is overall safer. As they can then be called on a`const Integer`

just as well as they can on an`Integer`

, you will then be able to pass your instances around as`const`

whenever they don't need to be modified, giving you a greater degree of safety.`Integer Integer::inverse() const; Integer Integer::squared() const; Integer Integer::pow() const;`

This will need to be changed both in the functions' prototypes, and in their definitions.