How to check whether a integer of type mpz_t is a palindrome

[Pedro Gimeno]

Matevž Markovič wrote:
> 2012/2/8 Pedro Gimeno <gmpdiscuss at formauri.es>
> 
>> Just to throw another idea on the table...
>>
>> The difference between a number and the base-10 reversed version of the
>> number is a multiple of 9. Couldn't that be used as a sieve?
> 
> That is a grand idea, as it does not deviate much from Torbjorn`s algorithm.

It saves the base conversion in case the number is rejected; if it is
not, you can proceed with the base conversion and test. Hopefully that
will be a quicker way to discard about 88% of the numbers. Whather it
pays off or not in the end is a different question, though.

Note that the test can be applied to other portions of the number. For
example, you can test with e.g. 10^19 and 10^(n-19), and with 10^18 and
10^(n-18); if the number is palindromic, both should pass the test, but
if not, even if one passes the other one can fail, so the rejection rate
might be in the order of 80 out of 81 (I'm not totally sure of the
accuracy of that statement, though). Whether that improves speed or not
is something you can try.

Example:
3281823 is palindromic
328-823 = -495, multiple of 9
32-23 = 9, multiple of 9.
Further tests can be applied.

3281697 is not palindromic.
328-697 = -369, multiple of 9.
But 32-97 = -65, NOT multiple of 9.
It can be rejected.

The test I suggested works because since palindromic numbers have the
same digits at the beginning and at the end, they have the same digital
root and thus are congruent modulo 9, so their difference is a multiple
of 9. So, a quicker test may be mpz_congruent_p rather than subtraction
and mpz_divisible_p. Or maybe you can test for congruence directly with
integer subtraction and modulus if you make the test against small
enough numbers (as in the case of 10^19 and 10^(n-19)). If you go that
way, remember that modulus is undefined for negative numbers, so maybe
you want to always subtract the smallest from the biggest.

> Is exporting two small numbers (under 50 digits) with gmp_sprintf into
> already allocated arrays (in base 10) quicker than
> first subtracting those two small numbers with mpz_sub and then using
> mpz_divisible_ui_p(result_of_subtraction, 9)?

I doubt it is quicker, that's why I suggested this. But as Marco says,
just try it and see.