How to check whether a integer of type mpz_t is a palindrome
Torbjorn Granlund
tg at gmplib.org
Sun Feb 5 23:04:12 CET 2012
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
More information about the gmp-discuss
mailing list