Testing for palindromes (Matev)
Jim White
mathimagics at yahoo.co.uk
Wed Feb 8 03:22:16 CET 2012
> 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.
Not sure what you mean by "only to a certain point". Given that you are
testing for base 10 palindromes, the method suggested by TG seems to me
to be the only way to attack this problem.
To recap, for each target integer A, with known size N digits (or N-1), we look at the
leading and trailing digits, K digits at a time. TG suggests K = 30, it might be worth
testing a sample of your A's to see what value of K is optimal for you.
Forming the required divisors 10 ^ (N - K) might best be done with the traditional binary
mask approach, ie using a table of precomputed values 10, 10^2, 10^4 etc (ie. 10^2^x).
Jim White
More information about the gmp-discuss
mailing list