# Find long palindrome multiplications in modern C++

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:
public:
~Timer()
{
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.

• What level of optimization are you using? Aug 23, 2022 at 18:40
• Just curious, why are you timing the conversion to string, why not just pass a converted string into functions that need a string and do the conversion just once? Aug 23, 2022 at 19:08
• @pacmaninbw: optimization /O2, added that to the question. For the string: I don't really understand the question. The string changes each time. I wanted to be able to choose the fastest algorithm. Whatever algorithm that is, if it works with a string, it will need to create that string. Aug 23, 2022 at 19:12
• That bug fix issue is strange. What if you moved the check inside the loop (after all, you are calculating last _digit anyway) ? Aug 24, 2022 at 9:38
• The bug made the program execute much more quickly, because it matches more results, quickly narrowing down the search space (you can see this if you add a print each time we update palindromes). It's pure dumb luck this didn't change the result. Remember: slow but correct is always better than fast and wrong! Aug 24, 2022 at 13:41

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).

• Thank you for the great feedback. I especially like the cleaner version of the iterator. And of course the huge performance jump. IDK why the all_of compiles here. As soon as I switch to ranges::all_of it does not compile for me. Aug 24, 2022 at 19:40
• You did change the iterator arguments to std::all_of(), and pass the range instead, I trust? I've added my working version into the answer. Aug 25, 2022 at 6:20

#### 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!!!

• I forgot you can use structured bindings in range-based for - thank you for suggesting that improvement! And I was playing with std::equal() algorithm as you were writing this; we both suggested something very similar. Aug 24, 2022 at 13:56
• Thank you for the detailed explanation. The structured binding in the for loop is really cool. Learning from such good feedback is really fun. Aug 24, 2022 at 19:44

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.

• Basically, inline doesn't actively harm your program, but it's extra clutter in the code, so best removed for readability. Aug 24, 2022 at 13:58
• I totally agree, especially with my usage in function pointers. They will never be inlined. This is a relic from earlier versions where I gave that some tries, just to find out it doesn't really matter. Aug 24, 2022 at 17:11