Find long palindrome multiplications in modern C++

Question

I'm a former C# programmer, updating my rusty C++98 (perhaps I should try Rust instead) to modern C++20. My main goal is to get used to C++ standard library types and algorithms.

I chose to solve a palindrome quiz, finding the largest palindrome when multiplying two N-digit numbers. Basically it's a harder version of this puzzle.

Solving this task was no problem for N <=4, but I needed to tweak performance to run in acceptable time for 5 <= N <= 7. For that I needed to

1. start at the upper limit to find large numbers quickly and count backwards
2. quit the innermost loop early (break;)
3. update the lower limit (lower_bound)

With this performance improvement, I can no longer imagine how to use a C++ algorithm instead of the plain for-loops.

Request A: can you help me use a C++ algorithm instead of the innermost "plain old" for-loops?

There's something else: when I implemented the mathematical approach for the palindrome check (is_palindrome_math()) I first had a bug. With that bug, execution time was ~120 ms only. After fixing the bug (uncomment the line which says bugfix), it takes ~1200 ms (factor 10).

Request B: can you help me apply the bugfix without getting a 10x performance loss?

Request C: just a code review ;-) I used east const, just to see how that feels. Please don't argue for west const. I know the discussion.

I'm using Visual Studio 2022, C++20. Do yourself a favor and run it in Release Build without attaching a debugger for higher N.

#include <algorithm>    // std::sort()
#include <cassert>      // assert()
#include <chrono>       // time measurements
#include <iostream>     // std::cout
#include <string>       // std::to_string()
#include <vector>       // std::vector<T>
#include <tuple>        // std::tuple<T>
#include <ranges>       // std::ranges::views
#include <map>          // std::map<T>

/**
 * \brief Checks for palindromes using string and reverse string.
 * \param n Number to check being palindrome.
 * \return True if the number is a palindrome.
 */
inline bool is_palindrome_str(unsigned long long n)
{
    auto const num = std::to_string(n);
    auto backward(num);
    std::ranges::reverse(backward);
    return num == backward;
}

/**
 * \brief Checks for palindromes using a string and a forward and reverse iterator.
 * \param n Number to check being palindrome.
 * \return True if the number is a palindrome.
 */
inline bool is_palindrome_iterator(unsigned long long  n)
{
    auto const num = std::to_string(n);
    auto left = num.begin();
    auto right = num.rbegin();
    while (std::distance(left, right.base() - 1) > 0)
    {
        if (*left != *right) return false;
        ++left;
        ++right;
    }

    return true;
}

/**
 * \brief Checks for palindromes using a string and accessing individual characters.
 * \param n Number to check being palindrome.
 * \return True if the number is a palindrome.
 */
inline bool is_palindrome_char(unsigned long long n)
{
    auto const num = std::to_string(n);
    auto const size = num.size();
    for (auto i = 0ULL; i < size / 2; i++)
    {
        if (num[i] != num[size - i - 1]) return false;
    }
    return true;
}

/**
 * \brief Checks for palindromes using a string and std::all_of for individual characters.
 * \param n Number to check being palindrome.
 * \return True if the number is a palindrome.
 */
inline bool is_palindrome_allof(unsigned long long  n)
{
    auto const num = std::to_string(n);
    auto const size = num.size();
    auto const indexes = std::ranges::views::iota(0ULL, num.size() / 2);
    return std::all_of(indexes.begin(), indexes.end(),
        [&num, &size](auto index) { return num[index] == num[size - 1 - index]; }
    );
}

/**
 * \brief Checks for palindromes using math.
 * \param n Number to check being palindrome.
 * \return True if the number is a palindrome.
 */
inline bool is_palindrome_math(unsigned long long n)
{
    // Bugfix:
    //if (n % 10 == 0) return false;
    auto m = 0ULL;
    while (n > m)
    {
        auto const last_digit = n % 10;
        n /= 10;
        if (n == m) return true; // exit for odd number of digits
        m *= 10;
        m += last_digit;
        if (n == m) return true; // exit for even number of digits
    }
    return false;
}

/**
 * \brief Calculates the start number and end number of the decade with the number of digits given.
 * \param digits Number of digits
 * \return Start and end value, e.g. 1000 and 9999 for the 4 digits decade
 */
std::tuple<unsigned int, unsigned int> get_decade_range(unsigned int const digits)
{
    unsigned int begin = 1;
    for (unsigned int i = 1; i < digits; i++) begin *= 10;
    unsigned int end = begin * 10 - 1;
    return std::make_tuple(begin, end);
}

/**
 * \brief Stopwatch for measuring wall clock time of a method.
 * Starts measuring when created, stops measuring when it goes out of scope.
 */
class Timer
{
private:
    std::chrono::time_point<std::chrono::steady_clock> const startTime = std::chrono::steady_clock::now();
public:
    ~Timer()
    {
        auto const endTime = std::chrono::steady_clock::now();
        std::cout << "Calculation took " << std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime).count() << " ms." << std::endl;
    }
};

int main()
{
    // Some poor man's unit tests
    assert(is_palindrome_char(9234567654329));
    assert(is_palindrome_str(9234567654329));
    assert(is_palindrome_iterator(9234567654329));
    assert(is_palindrome_allof(9234567654329));
    assert(is_palindrome_math(9234567654329));

    // Different approaches for performance comparison
    std::map<std::string, bool (*)(unsigned long long)> palindrome_functions;
    palindrome_functions.emplace("math", is_palindrome_math);
    palindrome_functions.emplace("char", is_palindrome_char);
    palindrome_functions.emplace("str", is_palindrome_str);
    palindrome_functions.emplace("iterator", is_palindrome_iterator);
    palindrome_functions.emplace("allof", is_palindrome_allof);

    auto [begin, end] = get_decade_range(7); // Note to self: this is C++17 structured binding == Python tuple unpacking
    std::cout << "Looking for palindromes from " << begin << " to " << end << "\n";

    for (auto const& is_palindrome_f : palindrome_functions) // Note to self: we call this a range-based for-loop
    {
        std::cout << "\nRunning algorithm " << is_palindrome_f.first << "\n";
        const Timer _performance;

        unsigned long long lower_bound = begin;
        std::vector<std::tuple<unsigned long long, unsigned long long, unsigned long long>> palindromes;
        // Question: can I use an algorithm here?
        for (unsigned long long factor1 = end; factor1 >= lower_bound; factor1--)
        {
            // Question: or here?
            for (unsigned long long factor2 = factor1; factor2 >= lower_bound; factor2--)
            {
                auto const product = factor1 * factor2;
                if (is_palindrome_f.second(product))
                {
                    lower_bound = std::max(factor2, lower_bound);
                    palindromes.emplace_back(product, factor1, factor2);
                    break;
                }
            }
        }

        auto const highest = *std::ranges::max_element(palindromes);
        std::cout << std::get<0>(highest) << "=" << std::get<1>(highest) << "*" << std::get<2>(highest) << "\n";
    }
}

Output on my AMD Ryzen 7 2700X, 32 GB RAM (for comparison), /O2 optimization (MSVC does not have /O3 as it seems).

Looking for palindromes from 1000000 to 9999999

Running algorithm allof
99956644665999=9998017*9997647
Calculation took 5310 ms.

Running algorithm char
99956644665999=9998017*9997647
Calculation took 5332 ms.

Running algorithm iterator
99956644665999=9998017*9997647
Calculation took 5195 ms.

Running algorithm math
99956644665999=9998017*9997647
Calculation took 121 ms.       <-- bug version

Running algorithm str
99956644665999=9998017*9997647
Calculation took 8113 ms.

Answer 1

Sometimes, comments can be useful when #includeing headers. However, these are patently redundant:

#include <cassert>      // assert()
#include <vector>       // std::vector<T>
#include <tuple>        // std::tuple<T>
#include <map>          // std::map<T>

This kind of comment quickly becomes outdated as the code is changed, so I recommend them only when the dependency is distinctly non-obvious.

When the list of includes gets long, I find it helpful to sort them (or sort each group) alphabetically, so it's easy to avoid adding a duplicate. Sorting is possibly because all standard libraries are defined to be used independently.

---

is_palindrome_allof() fails to compile here, because the two iterators are of different types (the view start type and its sentinel type). That's easily fixed, by using std::ranges::all_of() in place of std::all_of() in its implementation:

auto const indexes = std::ranges::views::iota(0u, num.size() / 2);
auto compare =
    [&num, &size](auto index) { return num[index] == num[size - 1 - index]; };
return std::ranges::all_of(indexes, compare);

---

It's a good idea to use a typedef for the type of integer we're using - if we later decide we want to work with a std::uint_max_t, we would then only need to change it in one place. We could alternatively make the predicate functions into templates (e.g. template<std::unsigned_integer Integer>, using the constraint from <concepts>).

---

If we're only interested in the highest product, we don't need to maintain a vector of results - just replace the value each time we find a better one.

Of course, we need to deal with the possibility of getting no results - but that's already true of the posted code: *std::ranges::max_element(palindromes) is undefined if palindromes is empty, so we should check that first.

---

For the questions in the comments ("can I use an algorithm here?"), I think the answer is "no" for the first one, because we have an end-point we're continually adjusting. It's possibly "yes" for the second (std::find_if() exits the loop after the first match), but I expect that would actually harm the clarity of the code.

---

I think that lower_bound should be made exclusive, reducing its initial value by 1 and changing the comparisons to <, because we don't want to actually reach it. E.g. having found 9999*9901, we don't want to try 9998*9901. That gave me a significant speed-up when I tried it.

We can improve the termination condition for the inner loop: since we compute the product anyway, we can break out of it once we reach a value that cannot be the highest, rather than going all the way down to lower_bound. That removes a few more calls to the palindrome predicate function. And it's worth using std::sqrt() to get a better limit for factor1.

---

Improved code

#include <cmath>
using Integer = unsigned long long;

    Integer lower_bound = begin;
    Integer max_prod = 0;
    std::pair<Integer, Integer> max_factors;

    for (Integer factor1 = end;  lower_bound < factor1;  --factor1)
    {
        for (Integer factor2 = factor1 ;;  --factor2)
        {
            auto const product = factor1 * factor2;
            if (product <= max_prod) { break; }
            if (is_palindrome_f.second(product))
            {
                max_prod = product;
                max_factors = { factor2, factor1 };
                lower_bound = static_cast<Integer>(std::sqrt(product));
                break;
            }
        }
    }

    if (max_prod) {
        std::cout << max_prod << '='
                  << max_factors.first << '*' << max_factors.second
                  << '\n';
    }

---

In the individual predicate functions, we can make some improvements, too:

• In is_palindrome_str(), I expected that constructing backward from a pair of reverse iterators would be faster than copying followed by in-place reverse(), but I was wrong there - it's already as fast as I could make it.

• is_palindrome_iterator() can be simplified using a standard algorithm:

  inline bool is_palindrome_iterator(Integer n)
  {
      auto const num = std::to_string(n);
      auto half = num.size() / 2;  // rounding down is okay
                                   // as we can ignore mid char
      auto left = num.begin();
      auto right = num.rbegin();
      return std::equal(left, left + half, right);
  }
  

  This change was performance-neutral on my system.

• is_palindrome_char() really ought to use std::size_t i to fully match the type of size/2. On the other hand, we can use what we know about the number of digits in our integer types to use a smaller (and faster) type there: auto const size = static_cast<unsigned>(num.size()); for (unsigned i = 0; i < size / 2; ++i).

Answer 2

A. Using a std algorithm in the nested testing loops

I agree with all of Toby Speight's answer, so I'll comment on the rest of the code.

B. is_palindrome_math() bug fix

The problem with this function without the bug fix is that it can give wrong answers for multiples of 10. If you follow the code using an input of 1310, the variable m is unchanged after the first loop iteration. So, on the next loop iteration, the state of the function is the same as if the original input was 131, which will return true. The unfixed version is faster because it returns true for a lot more numbers. Any palindrome number multiplied by a power of 10 will return true: 131, 1310, 13100, 131000, etc. It gets an answer to the problem faster because it returns large but wrong values. Since you start with large factors and work down, you get an answer early. The fixed function takes longer because it gives correct answers which take longer to find. I don't think there's any way to get a faster correct algorithm without doing something completely different.

C. Code Review

You can use a std algorithm in the is_palindrome_iterator() function by calculating the size of the substrings you need to compare and doing arithmetic to find the end iterator.

inline bool is_palindrome_iterator(unsigned long long  n)
{
    auto const num = std::to_string(n);
    return std::equal(num.begin(), num.begin() + num.size()/2, num.rbegin());
}

You can do arithmetic on this iterator because iterators over std::string are random access. In case you want to be more general, you can use std::next:

inline bool is_palindrome_iterator(unsigned long long  n)
{
    auto const num = std::to_string(n);
    return std::equal(num.begin(), std::next(num.begin(), num.size()/2), num.rbegin());
}

Some container iterators, like std::list::iterator, do not have an operator+ since you cannot jump to random positions; you can only iterate one element at a time.

This way of using std::equal is essentially the same algorithm you're using in the _char and _allof versions.

---

Range-based for-loops can also use structured bindings, so the top level for-loop in the testing code can be written as

for (auto const& [function_name, function] : palindrome_functions)

Then, use function_name instead of is_palindrome_f.first and function instead of is_palindrome_f.second.

---

WEST const FOREVER!!!

Answer 3

The use of the inline keyword is something from your C++98 days that isn't so good anymore. The inline keyword now is only a recommendation to the compiler. The optimizing portion of the compiler will determine whether the code is inlined or not without the recommendation. I learned this here on Code Review myself.