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

[Matevž Markovič]

Ciao,

>
> Il Lun, 6 Febbraio 2012 12:26 am, Matevž Markovič ha scritto:
> > 2012/2/5 Torbjorn Granlund <tg at gmplib.org>
>
> >> Is it reasonable to assume that most numbers will be non-palindromes?
> >>
> >> If that is indeed the case, I would suggestion something like this:
> >>
> >> 1. Determine the (approximate) number of digits in your number A using
> >>   mpz_sizeinbase, call this number n.
> >>
> >> 2. Compute A / d^(n-30).  Compute A mod d^30.  Print both in base d,
> >>   compare.  If they are unequal, reject as non-palindrome.
>
> > I am wondering whether it is possible to treat mpz_t as an array and to
> > access its digits directly? (portability is not an issue, it will only be
> > used on my local computer). If not, I will try to determine whether your
> > recommendation outperforms my current method on numbers in question.
>
> It is, but the mpz_t type internally uses "digits" (usually called limbs)
> in base 2^B, with B depending on the CPU (typically B=32 or B=64).
> If you want to detect palindromic numbers in base 2 or in base some power
> of two, then you may benefit of the "direct access". But you are using
> gmp_sprintf(.,"%Zd",.), so we can guess you are interested in base 10.
>
> I may add the suggestion to order the numbers, so that you can start from
> the smaller ones and update the "d^(n-30)" factor suggested by Torbjorn
> instead of compute it from scratch for each new number.
>
> Best regards,
> Marco


I did some preliminary test and your (Marco and Torbjorn) recommendations
would speed the checking up considerably.
Numbers are luckily generated in an order (otherwise they would need to be
sorted in small chunks, as only a small fraction of them would fit even on
a 500GB hard drive).

One last question -- why have you, Torbjorn, proposed exactly 30 (in
d^(n-30) and in A mod d^30) and not some other number? I would really like
to know.

Thank you,

Matevž