Developers Club geek daily blog

1 year, 2 months ago
After seemingly quite good result received in the previous part was only "a local maximum", I for some time threw a problem. I will remind a condition:
"The decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number". Or, in Russian: "The decimal number 585 in binary numeral system looks as 1001001001. It is a palindrome in both numeration systems. Find n-y a similar palindrome".

But existence is considerable faster, with essentially other computing complexity, algorithm haunted me, and eventually I returned to its analysis.

Eventually, the algorithm was not such and difficult, but, in my opinion, very beautiful.

The original explanation and implementation use a prefix tree, but in my opinion, deeper understanding of mathematics of algorithm allows to manage simpler and fast structures. I think that it is the best of all to sort algorithm on an example.

We will look for binary palindromes among decimal palindromes 8 wide. Initial palindromes exactly 9000: from 10000001 to 99999999.

Now we will take 2 sets of numbers:

  • And [90] = { 10000001, 11000011, 12000021..., 98000089, 99000099 }
  • B[100] = { 00000000, 00011000, 00022000..., 00988900, 00999900 }

If to describe these sets formally, then the set And is a subset of decimal palindromes 8 wide which have average 4 discharges — zero, and the set of B consists from 0, sets of the decimal palindromes 2 wide increased on 103 and sets of the decimal palindromes 4 wide increased on 102.

And if it is informal, then a set And — all this possible "edges", and a set of B — all possible "cores" of decimal palindromes 8 wide. It is obvious that the set of all decimal palindromes 8 wide is a set of all paired sums of elements of sets of A and B.

for each (a in A) {
	for each (b in B) {
		palindrome = a + b;
	}
}

Further, for brevity I will use "a" instead of "A set member", and "b" instead of "B set member".

Now we will transfer elements of both sets to binary numeral system:

A
10000001 100110001001011010000001
11000011 101001111101100011001011
12000021 101101110001101100010101

98000089 101110101110101110011011001
99000099 101111001101001111100100011

B
00000000 000000
00011000 10101011111000
00022000 101010111110000

00988900 11110001011011100100
00999900 11110100000111011100

I selected 6 upper and lower discharges at all a, and 6 lower discharges at all b. Width 6 is selected not accidentally - it is the maximum degree 2 which is not exceeding width of "edges" of A = 102.

Now we will take each a, and we will look that the general at all palindromes formed from it by addition of b. And the general at them, the fact that all of them are in an interval between an and the element A following it.

For example, for a = 10000001, all decimal palindromes formed from it { 10000001, 10011001, 10022001..., 10988901, 10999901 } are in an interval [10000001, 11000011).

It means that all decimal palindromes formed from a = 10000001 can begin only with the following 6 binary figures:
100110 — the first binary figures of a = 10000001
100111
101000
101001 — the first binary figures of a = 11000011

Therefore, to be binary palindromes, all these decimal palindromes can come to an end only on the return shift of initial binary figures:
100110-> 011001
100111-> 111001
101000-> 000101
101001-> 100101

And considering what and = 10000001 comes to an end on binary figures 000001, from all possible b we are interested only those which come to an end on binary figures:
011001 — 000001 = 011000
111001 — 000001 = 111000
000101 — 000001 = 000100
100101 — 000001 = 100100

Only for such b it is necessary to check whether b a binary palindrome is 10000001 +.

Using this approach, the algorithm for finding of palindromes in the bases of BASE0, BASE1 in the range of [1, N] can be described as follows:
For each width of W from [1, quantity of discharges N in BASE0]
    To generate sets of A and B, using BASE0. Width of "edges" of A WA = O(W/4), WAWB
    To transfer the A and B elements to BASE1
    To sort elements B on baskets on the last digits in BASE1
    For each a from a set of A
        For every X of a set of possible initial digits of a + b
            For each b which is coming to an end on (X — final digits of a)
                To check whether a + is b a palindrome in BASE1

Unfortunately, I already forgot to prove strictly computing complexity of algorithms, I will give some reasons:

  1. Sets of A and B contain O(N1/4) of elements.
  2. For each an on average there is no more BASE0 of options X.
    (We initially select width of the initial digits interesting us in BASE1 so that the number which turned out from them was no more BASE0WA, and max(A) is more than min (A) in BASE0 of times.)
  3. For every X BASE1 of different b is on average checked no more, than.
    (X it is distributed evenly and almost does not correlate with final digits of an in BASE1. Each basket with b means it is selected evenly, and such baskets no more than it is BASE1 times less of everything, than b.)
  4. Check on a palindrome all the same occupies O(log(N)).

Generally, I assume that computing complexity of algorithm of O(N1/4 * log(N) * BASE0 * BASE1).

The first implementation of this algorithm was quite predictably couple orders faster, and having spent a little more time for optimization I finished computation time about a little more than 0.01 seconds, is more than 1000 times faster than predydyshchy algorithm. This result at last satisfied me, but quite naturally there was a desire to check it on numbers, big, than 260. By this time I already found the sequence interesting me in "The encyclopedia of integer sequences". In the list of double palindromes there were 122 members, the biggest of whom consisted of 131 bits. It was impressively, but also indirectly indicated that nobody thought up algorithm of logarithmic complexity yet.

The challenge was serious — it was possible not to doubt that the people who received such result put many forces in development of algorithm and besides were for certain ready to spend days and weeks of machine time for the subsequent search. Therefore, I decided to evaluate at least approximately, time which is necessary for my algorithm on repetition:

2131 / 260 = 271

271 * 1/4 218 < = 262144

Considering 0.01 seconds necessary for a limit in 260, left that my algorithm had to cope with this task approximately in 1 hour! I felt some dirty trick, but the challenge was already accepted.

Be continued.

This article is a translation of the original post at habrahabr.ru/post/272659/
If you have any questions regarding the material covered in the article above, please, contact the original author of the post.
If you have any complaints about this article or you want this article to be deleted, please, drop an email here: sysmagazine.com@gmail.com.

We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.
Shared knowledge makes the world better.
Best wishes.

comments powered by Disqus