Developers Club geek daily blog

1 year, 10 months ago
Not so long ago read on Habré the article "Forward, on Searches of Palindromes" about a solution and optimization of a curious competitive problem with very laconic formulation:

"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".

The author began the fascinating story with the most trivial solution with search and check of all numbers from 1 to N and computing complexity of O(N * log(N)) where N — the maximum checked number. The multiplier of log (N) is necessary since it for each checked number is made several actions depending on quantity of its discharges.

The first working optimization, namely replacement of search of all numbers by search only of decimal palindromes, cardinally improved computing complexity to O(N1/2 * log(N)) since the quantity of the checked numbers decreased to O(N1/2). And despite some losses because of complication of algorithm, on enough big N runtime predictably improved on orders.

Having made some more small optimization, the author improved runtime by 3 times, and on this quite good result decided to stop.

Without having read up up to the end yet, I thought that I at the same computing complexity of O(N1/2 * log(N)) for certain will work much quicker not with lines, and directly with numbers. That is to generate sequence of palindromes, using not operations with lines, but arithmetic actions.

And it appeared absolutely not difficult, the sequence of numbers palindromes of identical length reminds an arithmetic progression with a permanent step which it is necessary to adjust each BASE, BASE2, BASE3,… elements.

For example, for decimal palindromes 5 wide the main step will be ravn +100:

10001, 10101, 10201, 10301, 10401, 10501, 10601, 10701, 10801, 10901, 11001

The last sequence unit is not a palindrome and demands correction +10, to 11011

11011, 11111, 11211, 11311, 11411, 11511, 11611, 11711, 11811, 11911, 12011

The last element a sequence unit demands correction +10, again to 12021

So we reach that the 99th and 100th elements: 19991, 20091

Necessary correction for the 100th element +10-99 =-89, as a result, we receive 20002 also we continue until we reach to 99999.

As arithmetic generation of palindromes became very fast (on average only several commands of the assembler), I decided that generation of palindromes in one basis + check in another will work for a palindrome more slowly, than parallel generation of palindromes in both bases and comparison.

As a result, the following code on C ++ turned out:

Auxiliary structure with necessary degrees of the basis:
#undef POWER
#define POWER(exp)  m_powers[exp]

template<typename IntT>
struct BaseData
{
	static const size_t MAX_WIDTH = sizeof(IntT) * CHAR_BIT;

	BaseData(
		size_t base,
		IntT maxValue)
		: m_base(base)
	{
		POWER(0) = IntT(1);
		for (size_t i = 1; i < MAX_WIDTH; ++i) {
			POWER(i) = POWER(i - 1) * IntT(base);
			if (POWER(i) >= maxValue) {
				m_maxWidth = i - 1;
				break;
			}
		}
	}

	size_t  m_base;
	size_t  m_maxWidth;
	IntT    m_powers[MAX_WIDTH];
};

Iterator of palindromes:
template<typename IntT>
class Iterator
{
	static const size_t MAX_WIDTH = sizeof(IntT) * CHAR_BIT;

private:
	struct IncrementData
	{
		size_t  m_counter;         //	current counter value
		size_t  m_counterLimit;    //	number of iterations, usually B, but B - 1 for last increment
		IntT    m_increment;       //	increment value
	};

public:
	inline Iterator(
		const size_t base,
		const IntT * powers)
		: m_base(base)
		, m_powers(powers)
	{
		m_value = POWER(0);

		SetWidth(1);
	}

	inline void operator ++()
	{
		//	always increment by basic
		m_value += m_basicIncrement;

		size_t i = 0;
		do {
			if (--m_counters[i].m_counter)
				return;

			//	reset counter
			m_counters[i].m_counter = m_counters[i].m_counterLimit;
			//	correct value on digit overflow
			m_value += m_counters[i].m_increment;
		} while (++i < m_countersSize);

		//	prepare to next width
		SetWidth(m_width + 1);
	}

	inline const IntT &operator *() const
	{
		return m_value;
	}

private:
	void SetWidth(
		size_t width)
	{
		m_width = width;
		m_countersSize = (m_width + 1) / 2;

		m_basicIncrement = POWER(m_countersSize - 1);

		size_t i;
		for (i = 0; i < m_countersSize - 1; ++i) {
			m_counters[i].m_counter = m_counters[i].m_counterLimit = m_base;
			m_counters[i].m_increment = POWER(m_countersSize - i - 2) - POWER(m_countersSize - i - 2) * m_base * m_base;
		}
		m_counters[i].m_counter = m_counters[i].m_counterLimit = m_base - 1;
		m_counters[i].m_increment = POWER(0) - POWER(1);

		if (m_width &1)
			m_counters[0].m_increment += POWER(m_countersSize);
		else
			m_basicIncrement += POWER(m_countersSize);
	}

	IntT           m_value;                 //	current value
	IntT           m_basicIncrement;        //	basic increment (100... for odd width, 1100... for even width
	size_t         m_countersSize;          //	just greater half of width: (width + 1) / 2
	IncrementData  m_counters[MAX_WIDTH];
	size_t         m_width;                 //	current width = number of digits
	size_t         m_base;
	const IntT   * m_powers;
};

And, at last main:
int _tmain(int argc, _TCHAR* argv[])
{
	int64 limit = 18279440804497281;

	BaseData<int64> base0(2, limit);
	BaseData<int64> base1(10, limit);

	Iterator<int64> it0(base0.m_base, base0.m_powers);
	Iterator<int64> it1(base1.m_base, base1.m_powers);

	while (*it0 <= limit) {
		if (*it0 < *it1)
			++it0;
		else if (*it0 > *it1)
			++it1;
		else {
			std::cout << *it0 << std::endl;
			++it0;
			++it1;
		}
	}

	return 0;
}

The 56th palindrome equal 18279440804497281 was received in 1.85 seconds that is about 150 times faster than the previous result (assuming that the grey_wolfs computer had the computational capability similar to my Intel Core i7-3770 CPU @ 3.40GHz). Certainly, the noticeable part of my benefit was called by transition from PHP for C ++, but all the same I with satisfaction rubbed hands: the algorithm already touched nearly 300 000 000 palindromes per second, and I in a stock had two more trumps: to generate only odd decimal palindromes (-20-25%) and to use a multithreading (-70-85% at 8 flows) …

And here I saw the comment which just "killed" me:

@hellman
Not so long ago on one of contests of codechef there was the same problem. Only bases of systems of calculation any from 2 to 16, it was also necessary the first 1000 palindromes smaller 2^60. Time limit — 8 sec. (the truth on an input can be 5 tests). Editorial is in the same place.

My algorithm found all palindromes to 260 in 15 seconds, i.e. at worst would not keep within time limit even using a multithreading. And in Editorial there was also a humiliating comment "why does the time limit for this question is so high 8 sec I have not seen such high limit in any questions...?".

The satisfaction was quickly replaced by disappointment: my implementation of search * log(N)) though was close to computing complexity of O(N1/2 with the minimum theoretical limit, but it all the same there was insufficiently. I tried to understand the theoretical solution described in Editorial, even looked at their code, but from the first understood only that they managed to solve a problem with computing complexity about O(N1/4 * log(N)).

At this moment I stopped work on a problem, but it did not go at me out of the mind. And in several days I returned to it again.

Be continued.

This article is a translation of the original post at habrahabr.ru/post/272555/
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