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

Matevž Markovič ivwcorporation.matevz at
Sun Feb 5 22:13:53 CET 2012


I have 900 x 10^6 numbers (each has at least 200,000 digits) which need to
be checked whether they are palindromes.

For example, until now, I did it in such a way:
mpz_t big_number;
int length = gmp_sprintf(array, "%Zd",big_number);
register int i = 0;    //index

    while(i <length-i-1)
            if(array[i] != array[length-i-1])
                    return false;
    return true;

The problem is, copying whole number into a external array with gmp_sprintf
is very time consuming. Can it be done internally in GMP?
I mean, instead of copying the whole number into external array I would
like to check it in-place (so that the complexity would be O(f + length)
instead of O(f + 2 * length))

I tried to write my own low-level GMP function that would do it (check
whether mpz_it number is a palindrome), but failed due to lack of
understanding of GMP:mpz_t internal structure and the source code.

Any suggestions? I suppose someone already wrote it, or perhaps with your
help I can try to write it on my own.

Thank you for your time & help.


More information about the gmp-discuss mailing list