Testing for palindromes (Matev)

[Matevž Markovič]

2012/2/8 Jim White <mathimagics at yahoo.co.uk>

> > 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
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-discuss



I wrote "only to a certain point" due to the fact that I experienced a
drastic slowdown after numbers got bigger. Fortunately, those slowdowns
were not caused by gmp but were only a consequence of another software
problem (one of my test server applications decided to allocate little too
much memory from time to time).

About Torbjorn`s decission to use k=30, I thought that there was already
some research done. Thank you for your answers.

Yours,

Matevž