Palindrome Number
05/10/2025
7 minutes
I few years ago I explored the palindrome problem. At the time I focused on inputs of strings. That previous post has described a few solutions from a simple implementation to vectorized solutions.
In this post I will focus on the same problem but with numbers as the input. Is a number palindrome? sounds like a simple question but requires some clarifications to before answering. In this post I use the following constraints:
Only positive integers and 0 zero are considered valid inputs (
uints).A number is palindrome if the digits of it in base 10 represent a palindrome. All other non-digit characters (
.,,,-, etc.) are omitted.
Improving the Vectorized Palindrome
As a first step, I will update the previous vectorized palindrome implementation. While that uses a Span<T> to track the current segments of the input, this implementation uses two int locals: begin and end.
public static bool IsPalindromeVectorized(ReadOnlySpan<char> input) { var data = MemoryMarshal.AsBytes(input); int begin = 0; int end = data.Length; while (end - begin > 32) { Vector256<byte> vBegin = Vector256.LoadUnsafe(in data[begin]); Vector256<byte> vEnd = Vector256.LoadUnsafe(in data[end - 32]); vEnd = Avx2.Shuffle(vEnd, shuffle); vEnd = Avx2.Permute2x128(vEnd, vEnd, 1); vEnd = Avx2.CompareEqual(vBegin, vEnd); if (!Avx2.TestC(vEnd, Vector256<byte>.AllBitsSet)) return false; begin += 32; end -= 32; } Debug.Assert((end - begin) % 2 == 0); while (begin + 1 < end) { if (data[begin + 1] != data[end - 1] || data[begin] != data[end - 2]) // byte order of the char is the same. return false; begin += 2; end -= 2; } return true; }
The above implementation leverages AVX2 instructions, that means it can only run on CPUs that have this instruction set supported. As such, a production application must make sure these instructions are supported on the target architecture.
The following table summarizes the results on different test data sizes. Vectorized_Old is the previous implementation and Vectorized is the current one using the locals to track the beginning and the end of the data to be processed.
| Method | TestData | Mean | Error | StdDev | |--------------- |--------------------- |------------:|----------:|----------:| | Simple | aabbc(...)cbbaa [32] | 6.9342 ns | 0.1553 ns | 0.1453 ns | | Vectorized | aabbc(...)cbbaa [32] | 1.8011 ns | 0.0229 ns | 0.0214 ns | | Vectorized_Old | aabbc(...)cbbaa [32] | 2.1033 ns | 0.0641 ns | 0.0535 ns | | Simple | aabb(...)bbaa [128] | 42.0108 ns | 0.8729 ns | 0.8165 ns | | Vectorized | aabb(...)bbaa [128] | 3.4347 ns | 0.0853 ns | 0.0798 ns | | Vectorized_Old | aabb(...)bbaa [128] | 9.1934 ns | 0.2127 ns | 0.2532 ns | | Simple | aabb(...)bbaa [2048] | 484.5524 ns | 7.0451 ns | 6.2453 ns | | Vectorized | aabb(...)bbaa [2048] | 50.9361 ns | 0.4600 ns | 0.4078 ns | | Vectorized_Old | aabb(...)bbaa [2048] | 137.8273 ns | 2.7587 ns | 5.0445 ns | | Simple | aba | 0.9675 ns | 0.0540 ns | 0.0774 ns | | Vectorized | aba | 3.6606 ns | 0.0709 ns | 0.0664 ns | | Vectorized_Old | aba | 3.0872 ns | 0.0454 ns | 0.0403 ns | | Simple | abcddcba | 2.3735 ns | 0.0678 ns | 0.0634 ns | | Vectorized | abcddcba | 5.0587 ns | 0.0767 ns | 0.0717 ns | | Vectorized_Old | abcddcba | 8.7217 ns | 0.2094 ns | 0.3198 ns |
The table shows that the longer the input is, the more efficient the Vectorized implementation becomes. Using the updated implementation shows some reasonable performance gains.
Palindrome of Numbers
In this post I compare three different implementations for the number palindrome problem described above. The first one is IsPalindromeSimple.
ToString
IsPalindromeSimple calls ToString(...) on the input. Then it calls the IsPalindromeSimple implementation from the previous post, to tell if the string representation of the number is a palindrome. This implementation has a disadvantage for allocating a string object on the heap.
TryFormat UTF8
The second implementation addresses the allocation problem, by leveraging TryFormat method of the ISpanFormattable interface:
public static bool IsPalindromeTryFormat(uint input) { var length = CountDigits(input); Span<byte> buffer = stackalloc byte[length]; var result = input.TryFormat(buffer, out _, provider: CultureInfo.InvariantCulture); int begin = 0; int end = length - 1; while (begin < end) { if (buffer[begin] != buffer[end]) return false; begin++; end--; } return true; }
This implementation first uses a helper method CountDigits which is inspired by the following source. CountDigits tells the number of base10 digits required to print the number into a string. However, instead of allocating a new object on the heap, it allocates a buffer on the stack. Then TryFormat method writes the UTF8 digits into this buffer. Finally, a while loop validates if the number in the buffer is a palindrome.
Notice, that input data type - uint - limits the input between 0 to 4,294,967,295. That means the largest representable number fits in 10 bytes, hence allocating on the stack is safe, likely it won't cause a stack overflow. It also means that using the vectorized solutions from the previous post would hardly have any benefits, as those only vectorize inputs larger to 32 bytes. It is possible to use smaller vector sizes Vector64 or Vector128, but I leave this exercise for later.
The TryFormat based solution still involves formatting the number into UTF8 bytes, which is reasonably expensive compared to the next and final solution in this post.
Division
The final solution uses a similar idea as used by the TryFormat method. It uses the DivRem method to get a quotient and a remainder by dividing the input number by 10. The remainder returns the last digit. Then it calculates a number that should be the first digit if the number is a palindrome. In the case of an input number 2332, the last digit is 2 and the quotient is 233. To compare the quotient's first digit, it multiplies 2 with 100, that gives 200. 100 is calculated by the number of remaining digits in the number.
Then the algorithm subtracts this number from the quotient: 233-200=33. When the digits match, the result number is smaller by one fold. When the digits don't match:
ie. input of 9332, 933-200=733, which larger to 100, meaning the first digit is still there
or input of 1332, 133-200=4294967229 in an unchecked operation, which is also larger to 100.
In the above two cases the number is not a palindrome, and the algorithm returns false. Otherwise, the remaining digits of the number are checked. When no more digits are left, the number is a palindrome.
public static bool IsPalindromeNumber(uint input) { int length = CountDigits(input); for (int i = length; i > 1; i -= 2) { (input, uint lastDigit) = uint.DivRem(input, 10); uint tenBase = TenBase(i); input -= lastDigit * tenBase; if (input >= tenBase) return false; } return true; } private static uint TenBase(int digits) { ReadOnlySpan<uint> table = new uint[] { 0, 0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, }; return table[digits]; }
Conclusion
These implementations are more like guides, I would not use them as-is in production applications. The presented solutions describe vastly different approaches to tackle the same problem. All solutions satisfy the same set of unit tests, but these tests are not exhaustive, that said for certain inputs might give different results, but it is not intentional.
An interesting aspect of these solutions is their performance. The following table uses BenchmarkDotNet to compare the mean execution time on different inputs indicated in the TestNumber column. As the size of the input number grows, a clear tendency shows that the Division based solution provides the best results. Also note, that the SimpleNumber does allocate on the heap that is not shown in the table below:
| Method | TestNumber | Mean | Error | StdDev | |---------------- |----------- |-----------:|----------:|----------:| | SimpleNumber | 3 | 2.1873 ns | 0.0769 ns | 0.0719 ns | | SimpleNumber | 121 | 2.3495 ns | 0.0341 ns | 0.0285 ns | | SimpleNumber | 123321 | 8.6489 ns | 0.1097 ns | 0.1026 ns | | SimpleNumber | 2345665432 | 11.0004 ns | 0.1755 ns | 0.1466 ns | | TryFormatNumber | 3 | 3.0024 ns | 0.0383 ns | 0.0340 ns | | TryFormatNumber | 121 | 3.4501 ns | 0.0938 ns | 0.0878 ns | | TryFormatNumber | 123321 | 4.6104 ns | 0.0612 ns | 0.0543 ns | | TryFormatNumber | 2345665432 | 7.2262 ns | 0.1408 ns | 0.1317 ns | | Division | 3 | 0.6950 ns | 0.0225 ns | 0.0188 ns | | Division | 121 | 1.3536 ns | 0.0595 ns | 0.0556 ns | | Division | 123321 | 2.6062 ns | 0.0650 ns | 0.0576 ns | | Division | 2345665432 | 4.8786 ns | 0.0756 ns | 0.0631 ns |