How to check whether a integer of type mpz_t is a palindrome
Matevž Markovič
ivwcorporation.matevz at gmail.com
Mon Feb 6 00:26:44 CET 2012
2012/2/5 Torbjorn Granlund <tg at gmplib.org>
> Matevž Markovič <ivwcorporation.matevz at gmail.com> writes:
>
> Any suggestions? I suppose someone already wrote it, or perhaps with your
> help I can try to write it on my own.
>
> 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.
>
> Computing Compute A / d^(n-30) will be fast using mpz_tdiv_q.
> Unfortunately, computing d^(n-30) is not fast. One could really do with
> a rough approximation of that, but I don't see how to use that (without
> going to mpn).
>
> --
> Torbjörn
>
If I understand these things right, this is a good idea, but only to a
certain point (some numbers have more than 20 x 10^6 digits). And yes, it
is safe to assume that 99.999% of those numbers are non-palindromic.
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.
Thank you
Matevž
More information about the gmp-discuss
mailing list