How to check whether a integer of type mpz_t is a palindrome
Matevž Markovič
ivwcorporation.matevz at gmail.com
Wed Feb 8 20:54:09 CET 2012
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?
>
> For example, for 4 digits, abcd - dcba is a multiple of 9 for any number
> with decimal digits a, b, c, d: 1523-3251 is -1728, multiple of 9;
> 1524-4251=-2727, multiple of 9; 1520-0251=1269, multiple of 9;
> 1424-4241=-2817, multiple of 9, and so on.
>
> So, the sieving process could maybe calculate portions of the head and
> the tail of the number, and see if their difference is a multiple of 9,
> rejecting the number otherwise. If it passes the test, then a more
> detailed analysis can be done.
>
That is a grand idea, as it does not deviate much from Torbjorn`s algorithm.
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)?
@Torbjorn False positives are not problematic, as the numbers that pass
those tests should not be just "probable palindromic". Anyway, I think that
I will settle at say 19 or 20, as there is no need for going higher than
this.
Cheers,
Matevz
More information about the gmp-discuss
mailing list