How to check whether a integer of type mpz_t is a palindrome
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Mon Feb 6 20:36:23 CET 2012
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
--
http://bodrato.it/
More information about the gmp-discuss
mailing list