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

Question

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 <math.h>

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 - 1;            
        }
        number_one = number_one - 1;
    }
}


void FindPalindrome:: Determine_if_Palindrome(){

    //used in determining length of array and storing product into array
    int array_length = 0;
    //copy of array length so that original length value is still available
    int array_length_cpy = 0;   
    //vars for checking for palindrome properties
    int head = 0;
    int tail = 0;
    int retrieve_one = 0;
    int retrieve_two = 0;

    current = number_one * number_two;
    copy = current;

    //get length of number and create array to hold number
    while (copy != 0) {
        copy /= 10;
        ++array_length;
    }

    int store[array_length];

    //restore to products value for extraction manipulations
    copy = current;

    array_length_cpy = array_length;
    //extract digits from number and poopulate array
    for (int i = array_length_cpy; i>0; --i) {
        store[i-1] = copy%10;
        copy/=10;
        --array_length_cpy;
    }

    //Compare last and first digits then move "inwards" comparing the digits
    tail = array_length -1;

    retrieve_one = store[head];
    retrieve_two = store[tail];

    if (retrieve_one == retrieve_two) {
        for (int i = (array_length/2); i > 0; --i) {
            tail = tail -1;
            head = head + 1;
            retrieve_one = store[head];
            retrieve_two = store[tail];

            if (retrieve_one != retrieve_two) {
                return;
            }
        }

        palindrome = current; //it is a palindrome

        //test for if it is the biggest one found yet
        if (current > greatest) {
            greatest = current;

        }
    }     
}

main()

#include <sys/time.h>
#include <iostream>
#include "FindPalindrome.h"

using namespace std;


int main () { 

    int digits_specified = 0;

    cout << "Please enter the number of digits: ";
    cin>>digits_specified;
    cout << "\n";

    //For testing purposes to print out all palindromes generated
    /*
    std::cout << "Operand 1" <<"\t\t";
    std::cout << "Operand 2" <<"\t\t";
    std::cout << "Product" <<"\t\t\n\n";
    */

    FindPalindrome trial1(digits_specified);

    //find palindrome and record the time it took to do this
    struct timeval start, end;
        long mtime, seconds, useconds;

        gettimeofday(&start, NULL);
        //start actual calculation for palindrome
    trial1.Product_Generator();
    gettimeofday(&end, NULL);

    seconds  = end.tv_sec  - start.tv_sec;
        useconds = end.tv_usec - start.tv_usec;
        mtime = ((seconds) * 1000 + useconds/1000.0) + 0.5;
    cout << "\n";
        printf("Elapsed time: %ld milliseconds\n", mtime);
    cout << "\n";
    cout<<endl<< "Largest palimdromic number: "<< trial1.Greatest_Palindrome_Found()<<endl; 
    cout << "\n";
        return 0;
}

Answer 1

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.

Answer 2

1) Style guide

I would like to start off with a few style tipps. Take these with a large grain of salt as it is subjective.

1) C++ functions are usually lowercase while classes are uppercase.

2) C++ class members usually have some sort of special identifiers, such as a trailing underscore or the prefix "m_".

That't it for the style guide, let's talk class design :)

2) Finding the Palindrome

You called your class FindPalindrome which is nice, but a little confusing. I like to name classes after their behaviour, e.g. PalindromeFinder. Also, you used FindPalindrome in the singular, but do you want to constrain each instance to only one palindrome? Your design suggests not.

Secondly, you aren't using the STL to your advantage. Let's think about the nature of palindromes for a bit. Excluding strings, a palindrome is any number that can be read the same way front to back, e.g.

reverse(10011001) = 10011001.

Your determine_palindrome function seems to suggest that you are breaking the array into digits and then comparing them one-by-one. Great, you're on the right track; now let the STL help you.

std::vector<int> digits  = Utility::toArray<int>(number);
std::vector<int> reverse = digits;
std::reverse(reverse.begin(), reverse.end());

Instead of an array, I have used a vector so I don't need to burden myself with array count or ugly functions that take care of that for me. It also has a copy-constructor that lets me define a second array with exactly the same digits as the first one. The third line reverses that sequence of digits.

Now all that's left to do is to check if reverse and digit are the same digit for digit:

for (int i(0); i < digits.size(); ++i)
    if (digits[i] != reverse[i])
        return false;
return true;

This is my entire bool isPalindrome(int number) function. Nothing else was needed, I just had to use the STL to my advantage. If you haven't read up on the <algorithm> header yet I strongly suggest you do :)

As for runtime performance, this function performs in O(n) (linear) time.

3) Responsibilities

This is an OOP principle. Always try to give each class and function exactly one responsibility.

Did you see the function Utility::toArray<int>(number) in my section on finding the palindrome? You had it inside your function. My question to you is: is it the responsibility of a function, that determines whether or not a number is a palindrome, to also break a number into digits?

The answer is no. The isPalindrome functions finds a palindrome, that's it. You can refactor the code that splits the number into digits into its own function like I have. Templatize it and there you go, you can reuse it for a whole bunch of other numbers (well, integral numbers...).

4) Const-correctness

This is a big one. Make everything const that can be const. Why? Safety. Why else? Other programmers might rely on guarantees given by the functions they are calling.

An easy rule for const-correctness is: if the function isn't modifying any arguments, make it const. Your function greatest_palindrome only returns the greatest palindrome and nothing else. Make it const.

As Jerry pointed out, all of your needed variables are declared in the class itself, not the functions. If you changed that, you could possibly make some other functions const as well. Always strive for this!

5) Know your functions

Look at the overloads for pow (from cplusplus.com):

double pow (      double base,      double exponent );
long double pow ( long double base, long double exponent );
float pow (       float base,       float exponent );
double pow (      double base,         int exponent );
long double pow ( long double base,         int exponent );

They all use doubles and return doubles. Doubles are slow, you are only working with integral values. Do the multiplication yourself. This also applies to the <algorithm> library. Look around! Valuable stuff.

---

I think this has gone on long enough. Along with the suggestions from Jerry, your code should work faster now. Here is my implementation (without the function for upper and lower limits. Instead it just takes numbers from the command line.).

#include <vector>
#include <algorithm>

namespace Utility
{
    // See boost::noncopyable for details.
    class Uncopyable
    {
    protected:
        Uncopyable() {}
        virtual ~Uncopyable() {}

    private:
        Uncopyable(Uncopyable const&);
        Uncopyable& operator=(Uncopyable const&);
    };

    // We can apply template specialization to handle more than just integral data types.
    template <typename T>
    std::vector<T> toArray(T num)
    {
        std::vector<T> ret;

        while (num)
        {
            ret.push_back(num % 10);
            num /= 10;
        }

        return ret;
    }
}

// Alternate to Uncopyable is boost::noncopyable.
class PalindromeFinder : public Utility::Uncopyable
{
public:
    PalindromeFinder();

    void feed(int number);

    int greatestPalindrome() const;

    void operator()(int number);

private:
    bool isPalindrome(int number) const;

private:
    int greatestPalindrome_;
};

// Make sure our members are not in an undefined state.
PalindromeFinder::PalindromeFinder()
    : greatestPalindrome_(0)
{   }

// Replace me with your upper- and lower-limit implementation :3
void PalindromeFinder::feed(int number)
{
    if (isPalindrome(number) && number > greatestPalindrome_)
        greatestPalindrome_ = number;
}

bool PalindromeFinder::isPalindrome(int number) const
{
    std::vector<int> digits  = Utility::toArray<int>(number);
    std::vector<int> reverse = digits;
    std::reverse(reverse.begin(), reverse.end());

    // We could optimize this further by only going through half the vector's elements.
    for (int i(0); i < digits.size(); ++i)
        if (digits[i] != reverse[i])
            return false;

    return true;
}

// No numbers fed? Then our palindrome is 0.
int PalindromeFinder::greatestPalindrome() const
{
    return greatestPalindrome_;
}

void PalindromeFinder::operator()(int number)
{
    feed(number);
}