Finding the largest palindrome from the product of two n-digit numbers

The program finds the largest palindrome made from the product of two n-digit numbers, where n is specified by the user.

The code included works, however, when the user enters 5 or greater, the program runs very slowly. I believe it is \$O(n^2)\$ (feel free to correct that estimate if needed).

I'd like feedback/reviews regarding any "best practices" I should follow, along with performance and readability.

Class:

```
#include

class FindPalindrome {

private:

//multiplicand 1
int number_one;
//multiplicand 2
int number_two;
//holds current product
int current;
//copy of current product copy so as the current var values is not manipulated as its original will be needed
int copy;
//holds most recently discovered palindrome
int palindrome;
//holds greatest palindrome discovered
int greatest;
//as determined by number of digits for operand
int upper_limit;
int lower_limit;

public:

//Constructor
FindPalindrome(int digits_requiered);

//Accessors
int Greatest_Palindrome_Found();

//Mutators
void Product_Generator();
void Determine_if_Palindrome();
};

FindPalindrome::FindPalindrome(int digits_requiered){

upper_limit = pow(10, digits_requiered) - 1;
lower_limit = pow(10, digits_requiered -1);

number_two = number_one = upper_limit;

current = 0;
copy = 0;
palindrome = 0;
greatest = 0;

}

int FindPalindrome::Greatest_Palindrome_Found(){

return greatest;
}

void FindPalindrome::Product_Generator(){

while (number_one >= lower_limit) {
number_two = upper_limit;
while (number_two >= lower_limit) {
if(number_one >= number_two)
{
//test initial numbers to see if they generate palindrome
Determine_if_Palindrome();
}
number_two = number_two -

First, as a general observation, you've made created essentially all your variables as belonging to the FindPalindrome object. IMO, this is a mistake. Each variable should have the minimum scope necessary to do its job. Any variable that's only used inside a particular function, for example, should be local to that function, not the class. A variable that's used only in a specific loop should be local to that loop, etc.

After that, I'd take a look at DetermineIfPalindrome. First, I'd change it to something like:

bool is_palindrome(int number);

It should be just a pure function that tells you whether its input is palindromic or not. You then use that to decide what (if anything) to do with a particular number.

As far as how that's implemented, I'd start by observing that the length of a product is (at most) the sum of the lengths of the inputs (e.g., the product of 2 5-digit numbers will be no more than 10 digits). That means you can pre-allocate space for the converted number instead of doing most of the work for a conversion to find the size, then allocating space, then doing the conversion. This should roughly double the speed of that part of the code.

Looking at the next step up, Product_Generator uses while loops where it seems to be that for loops would make more sense. It also seems to generate (and then ignores) some numbers you apparently don't care about. It appears that it should be something like this:

int Product_Generator() { 
    int greatest = 0;
    for (int i=upper; i>=lower; --i)
        for (int j=upper; j>=i; --j) {
            int product = i * j;
            if (product > largest && is_palindromic(product))
                greatest = product;
        }
    return greatest;
}

Looking at the overall design of the class, I'd note two things: first, you've made essentially everything public, where it should all (or nearly all) be private. Second, its name signifies an action (a verb) which indicates that it should probably act like a function. Ultimately, it takes a single input (number of digits) and produces a single output (the desired palindrome).

As such, the class definition should look something like:

class FindPalindrome { 
    int lower, upper;

    bool is_palindrome(int);
public:
    FindPalindrome(int digits) : 
        lower(pow(10, digits_required -1)),
        upper(pow(10, digits_required)-1))
    {}

    int operator()() {
        // This is a renamed version of what's shown above as Product_Generator
    }
};

The other thing to consider would be whether it's worth going at this in the other direction -- start by generating palindromes, and factor each palindrome to see if we can find factors with the right number of digits. Factoring large numbers gets pretty slow, but as factoring goes, we're dealing with fairly small numbers here (for factoring, "large" generally means something like 100 digits or more). I'm not sure that would end up faster, but it might. It would also be fairly easy to generate the palindromes in strictly decreasing order, so the first one we found with factors the right size would be the final answer.

StackExchange Code Review Q#3338, answer score: 11