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

bodrato at bodrato at
Thu Feb 9 08:39:25 CET 2012


Il Mer, 8 Febbraio 2012 8:54 pm, Matevž Markovič ha scritto:
> 2012/2/8 Pedro Gimeno <gmpdiscuss at>

>> 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?

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

You should try, but gmp_sprintf is probably slower.

> @Torbjorn False positives are not problematic, as the numbers that pass
> those tests should not be just "probable palindromic". Anyway, I think

Having too many false positives affects general speed, because they
require a more expensive test.

> I will settle at say 19 or 20, as there is no need for going higher than

The cost of operations in GMP typically depends on the number of "limbs".
10^19 fits in 64 bits, 10^20 does not... 10^38 < 2^128 < 10^39 ...



More information about the gmp-discuss mailing list