0,0
рейтинг
6 ноября 2015 в 15:50

Разработка → Вперед, на поиски палиндромов

Не так давно на Хабре была статья про codebattle от hexlet.io. Ну и затянуло же нас с друзьями, это как наркотик! Вроде пытаешься на работу отвлечься, а руки прям сами тянутся зайти на сайт, и все мысли — об оптимизации решений.

И вот однажды попалась мне задачка, звучала она так: «The decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number». А если по-русски, то так: «десятичное число 585 в двоичном виде выглядит как 1001001001. Оно является палиндромом в обеих системах счисления. Найдите n-ый подобный палиндром». Она совсем не сложная и решена была быстро.

function is_palindrome($num) {
   return $num == strrev($num);
}
function solution($num) {
   $count = $i = 0;
   while($count<$num) {
      $i++;
      // Проверяем по порядку все числа, являются ли они палиндром в десятичном и двоичном виде
      if (is_palindrome($i) && is_palindrome(decbin($i))){
         $count++;
      }
   }
   return $i;
}

Но вот незадача. Примерно в то время на сайт напал хабраэффект, и тесты ни в какую не хотели проходить, отваливались по timeout. В местном чате началось обсуждение по оптимизации решения, но никто дельного совета так и не дал. Потом сайт отпустило, все тесты прошли, но желание оптимизировать осталось…

Генерируем десятичные палиндромы


Для начала мне стало интересно, сколько же я смогу найти палиндромов на своей машинке. Хоть в чате и не советовали искать больше 22-х, я спокойно нашел 27 всего за 5 секунд, а вот следующий пришел только через 4 с лишним минуты. Дальше я уж ждать не стал — долго что-то. Чтобы начать оптимизацию, я решил поподробнее узнать палиндромы.

Сгенерировал себе несколько штук и начал рассматривать.

Палиндромы
  1. 1
  2. 3
  3. 5
  4. 7
  5. 9
  6. 33
  7. 99
  8. 313
  9. 585
  10. 717
  11. 7447
  12. 9009
  13. 15351
  14. 32223
  15. 39993
  16. 53235
  17. 53835
  18. 73737
  19. 585585
  20. 1758571


По сути числовой палиндром — это некое число, которое взяли, отзеркалили и прикрепили в конец этого же числа. Т.е. взяли число 235, отзеркалили, получили 532 и соединили — получился прекрасный палиндром — 235532. И было принято решение: зачем перебирать все числа в поисках десятичного палиндрома, если можно их просто генерировать. Сказано — сделано!

function solution($num) {
   $count = $i = 0;
   while($count<$num) {
      $i++;
      //Берем числа по порядку и соединяем с собой же в перевернутом виде
      $palindrome = $i . strrev($i);
      // И проверяем является ли наш десятичный палиндром таким же в двоичном виде.
      if (is_palindrome(decbin($palindrome))) {
         $count++;
      }
   }
   return $palindrome;
}

Запустив, я увидел, что пропущены однознаковые палиндромы, и добавил простой цикл на первые девять чисел.

for ($i = 1; $i < 10; $i++) {
   if (is_palindrome(decbin($i))) {
      $count++;
      if ($count == $num) return $i;
   }
}

Запустив ещё раз, я увидел, что ошибка моя была гораздо сильнее. Я ведь совсем забыл про палиндромы с нечетным количеством знаков, таких как 313, 585 или 717! И вот тут мне пришлось крепко задуматься. Посмотрев на список полученных палиндромов, можно увидеть, что палиндромы с нечетным количеством знаков — это те же четные палиндромы, только с центровым знаком. Т.е. берем четный палиндром, вставляем в центр цифры 1-9 и вуаля — нечетные палиндромы готовы. Но! Если я буду вставлять их в этом цикле, я потеряю порядок чисел. Поэтому пришлось внести кардинальные изменения в код и отталкиваться от количества знаков.

function solution($num) {
   $count = 0;
   // Одноразрядные палиндромы.
   for ($i = 1; $i < 10; $i++) {
      if (is_palindrome(decbin($i))) {
         $count++;
         if ($count == $num) return $i;
      }
   }
   $p_size = 1;
   while (true) {
      $min = 10**($p_size-1);
      $max = (10**$p_size)-1;
      // $min и max с каждым проходом цикла будут увеличиваться на один разряд
      for ($i = $min; $i <= $max; $i++) {
         // Генерируем палиндром с четным кол-вом знаков
         $palindrome = $i . strrev($i);
         //проверяем является ли он палиндромом в двоичном виде.
         if (is_palindrome(decbin($palindrome))) {
            $count++;
            if ($count == $num) return $palindrome;
         }
      }
      for ($i = $min; $i <= $max; $i++) {
         for ($j = 0; $j < 10; $j++) {
            // Генерируем палиндром с нечетным кол-вом знаков
            $palindrome = $i . $j . strrev($i);
            //проверяем является ли он палиндромом в двоичном виде.
            if (is_palindrome(decbin($palindrome))) {
               $count++;
               if ($count == $num) return $palindrome;
            }
         }
      }
      $p_size++;
   }
}

Собственно, тут всё просто. Берем сначала одноразрядные числа 1-9. Создаем двухразрядные палиндромы. Следом трёхразрядные. Потом просто увеличиваем разряд и берем числа от 10-99. Получатся палиндромы 4-х и 5-тиразрядные. Ну и т.д.

Тестируем!


Для начала запустил посмотреть 28-ой палиндром. Оказалось что для улучшенной функции это абсолютно плёвая задача. 28-ой был получен за 0.15 секунды! А это значит, что скорость была увеличена больше чем в 1500 раз. Я был доволен. За 5 секунд я мог получить уже более 40-а палиндромов. 50-ый был получен за 2.5 минуты.

Обратив внимание на полученные палиндромы, я заметил, что все они нечетные. И ведь правда! Четные десятичные палиндромы в двоичном виде будут заканчиваться на 0, а так как они всегда начинаются с 1, то и палиндромом быть не могут. А это значит, что их даже проверять не нужно. А так как палиндромы мы генерируем, мы можем пропускать все числа с первой четной цифрой.

Простой continue по условию сразу отмёл. Нам даже не имеет смысла крутить на них цикл. Будем их пролистывать. Попробовав несколько вариантов:

if(!(substr($i,0,1))%2)) $i += $min;

if(!((floor($i/$min))%2)) $i += $min;

if (!$limit){
   $limit = $min;
   $i += $min;
}
$limit--;

Я остановился на последнем как на самом быстром и получил вот такой код.

Полный код
function solution($num) {
   $count = 0;
   // Одноразрядные палиндромы.
   for ($i = 1; $i < 10; $i++) {
      if (is_palindrome(decbin($i))) {
         $count++;
         if ($count == $num) return $i;
      }
   }
   $p_size = 1;
   while (true) {
      $min = 10**($p_size-1);
      $max = (10**$p_size)-1;
      // $min и max с каждым проходом цикла будут увеличиваться на один разряд
      $limit = $min;
      for ($i = $min; $i <= $max; $i++) {
         // Условие чтобы перескочить числа с чётной первой цифрой
         if (!$limit){
            $limit = $min;
            $i += $min;
         }
         $limit--;
         // Генерируем палиндром с четным кол-вом знаков
         $palindrome = $i . strrev($i);
         //проверяем является ли он палиндромом в двоичном виде.
         if (is_palindrome(decbin($palindrome))) {
            $count++;
            if ($count == $num) return $palindrome;
         }
      }
      $limit = $min;
      for ($i = $min; $i <= $max; $i++) {
         if (!$limit){
            $limit = $min;
            $i += $min;
         }
         $limit--;
         for ($j = 0; $j < 10; $j++) {
            // Генерируем палиндром с нечетным кол-вом знаков
            $palindrome = $i . $j . strrev($i);
            //проверяем является ли он палиндромом в двоичном виде.
            if (is_palindrome(decbin($palindrome))) {
               $count++;
               if ($count == $num) return $palindrome;
            }
         }
      }
      $p_size++;
   }
}


Этим мы получили ускорение ещё примерно в два раза. 50-ый был получен за 88 секунд и, на мой взгляд, это был отличный результат!

Генерируем двоичные палиндромы


И вот я уже был готов остановиться и порадоваться, как мне пришла в голову мысль попробовать сформировать двоичные палиндромы. А что? Используемых цифр меньше, четных не сгенирируешь. Одни плюсы кругом!

Немного поразмыслив, я быстренько изменил код и получил:

function solution($num) {
   if ($num==1) return 1;
   $count = 1;
   $p_size = 1;
   while (true) {
      $min = 2**($p_size-1);
      $max = (2**$p_size)-1;
      // $min и max с каждым проходом цикла будут увеличиваться на один разряд в двоичном виде
      for ($i = $min; $i <= $max; $i++) {
         $half_palindrome = decbin($i);
         // Генерируем палиндром с четным кол-вом знаков в двоичном виде
         $bin_palindrome = ($half_palindrome) . strrev($half_palindrome);
         //проверяем является ли он палиндромом в десятичном виде.
         $dec_palindrome = bindec($bin_palindrome);
         if (is_palindrome($dec_palindrome)) {
            $count++;
            if ($count == $num) return $dec_palindrome;
         }
      }
      for ($i = $min; $i <= $max; $i++) {
         $half_palindrome = decbin($i);
         for ($j = 0; $j < 2; $j++) {
            // Генерируем палиндром с нечетным кол-вом знаков в двоичном виде
            $bin_palindrome = $half_palindrome . $j . strrev($half_palindrome);
            //проверяем является ли он палиндромом в десятичном виде.
            $dec_palindrome = bindec($bin_palindrome);
            if (is_palindrome($dec_palindrome)) {
               $count++;
               if ($count == $num) return $dec_palindrome;
            }
         }
      }
      $p_size++;
   }
}

После тестов я понял, что всё сделал правильно. 28-ой был получен за 0.05 секунды. 50-ый за 48 секунд. Когда брался за эту задачу, такого результата я совсем не ожидал.

Тут я уже решил, что хватит: я и так превзошел все свои ожидания. Хотя вру, конечно. Потом ещё пытался придумать как можно увеличить скорость ещё больше, но уже ничего в голову не пришло. Устал уже, да и ночь на дворе.

Ну и напоследок сводная таблица:

Сводная таблица
Палиндром Перебор (сек) Генерация dec палиндромов (сек) Генерация bin палиндромов (сек) кол-во бит
1 1 6.9141387939453E-6 5.0067901611328E-6 1
2 3 5.1975250244141E-5 4.887580871582E-5 4.2200088500977E-5 2
3 5 5.8889389038086E-5 5.5074691772461E-5 6.0081481933594E-5 3
4 7 6.4849853515625E-5 6.103515625E-5 6.6041946411133E-5 3
5 9 6.9856643676758E-5 6.6041946411133E-5 7.4148178100586E-5 4
6 33 8.2969665527344E-5 7.1048736572266E-5 9.0122222900391E-5 6
7 99 0.00011205673217773 8.6069107055664E-5 0.00010299682617188 7
8 313 0.00020503997802734 0.00010395050048828 0.00012612342834473 9
9 585 0.00033092498779297 0.00012397766113281 0.00014519691467285 10
10 717 0.0003969669342041 0.00013089179992676 0.0001521110534668 10
11 7447 0.0026609897613525 0.0001828670501709 0.00027918815612793 13
12 9009 0.0031960010528564 0.00020384788513184 0.00030112266540527 14
13 15351 0.0053460597991943 0.0002899169921875 0.00034999847412109 14
14 32223 0.011164903640747 0.00038385391235352 0.00047707557678223 15
15 39993 0.013840913772583 0.00048685073852539 0.00052118301391602 16
16 53235 0.018357038497925 0.00053596496582031 0.00057101249694824 16
17 53835 0.018585920333862 0.00054693222045898 0.0005891323089599 16
18 73737 0.025254964828491 0.00066089630126953 0.00065517425537109 17
19 585585 0.19646406173706 0.0011670589447021 0.0015511512756348 20
20 1758571 0.59263801574707 0.0026059150695801 0.0024890899658203 21
21 1934391 0.65274286270142 0.002892017364502 0.0026500225067139 21
22 1979791 0.66831588745117 0.0029850006103516 0.0027000904083252 21
23 3129213 1.0589859485626 0.00323486328125 0.0032520294189453 22
24 5071705 1.7217099666595 0.0046730041503906 0.0040431022644043 23
25 5259525 1.7863478660583 0.0049829483032227 0.0041420459747314 23
26 5841485 1.9860379695892 0.0059189796447754 0.0043931007385254 23
27 13500531 4.5991010665894 0.0097908973693848 0.0064051151275635 24
28 719848917 254.43427205086 0.074897050857544 0.046326160430908 30
29 910373019 0.090998888015747 0.051257133483887 30
30 939474939 0.096122026443481 0.05202817916870 30
31 1290880921 0.11239194869995 0.061146974563599 31
32 7451111547 0.16925406455994 0.15515112876892 33
33 10050905001 0.19922494888306 0.18062520027161 34
34 18462126481 0.36378288269043 0.2389931678772 35
35 32479297423 0.4427649974823 0.33302116394043 35
36 75015151057 0.88776993751526 0.48717308044434 37
37 110948849011 1.20951795578 0.60900402069092 37
38 136525525631 1.2637610435486 0.69635009765625 37
39 1234104014321 2.6941239833832 2.0280501842499 41
40 1413899983141 3.0781800746918 2.1862101554871 41
41 1474922294741 3.2089228630066 2.2403671741486 41
42 1792704072971 3.8874368667603 2.5199501514435 41
43 1794096904971 3.8904230594635 2.521210193634 41
44 1999925299991 4.3287780284882 2.7018330097198 41
45 5652622262565 7.9812479019165 4.4443550109863 43
46 7227526257227 9.285425901413 5.1428310871124 43
47 7284717174827 9.4120988845825 5.1688570976257 43
48 9484874784849 12.100240945816 5.998220205307 44
49 34141388314143 16.401521921158 11.614565134048 45
50 552212535212255 87.537031888962 49.897539138794 49
51 933138363831339 134.56801986694 62.49614405632 50
52 1793770770773971 171.45103907585 90.226871013641 51
53 3148955775598413 180.56048107147 119.85724520683 52
54 10457587478575401 293.4983189106 224.45361399651 54
55 10819671917691801 303.29767894745 227.38862919807 54
56 18279440804497281 506.18344306946 287.77621507645 55
57 34104482028440143 410.04529714584 55
58 37078796869787073 428.8955411911 56
59 37629927072992673 431.15429711342 56
60 55952637073625955 506.2887160778 56


PS. Продолжение оптимизации от ilyanik смотрите в этой статье
Золотухин Сергей @grey_wolfs
карма
8,0
рейтинг 0,0
Программист
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (15)

  • +3
    Круто! Не зря батл делали)
  • +4
    Есть ощущение, что если бы вы работали не со строками, а с цифрами напрямую, то было бы ещё быстрее.
    • 0
      Я думаю вы правы. Ниже уже подсказали как это можно сделать. Сейчас буду пробовать реализовывать.
  • 0
    Не так давно на одном из контестов codechef была такая же задачка. Только базы систем исчисления произвольные от 2 до 16, и нужно было первые 1000 палиндромов меньшие 2^60. Ограничение по времени — 8 сек (правда на входе может быть 5 тестов). Editorial там же есть.

    • 0
      Есть еще простой (но возможно более медленный) метод. Рассматриваем блоки палиндромов в двух системах счисления (я использовал блоки размера 1000 и 1024 соответственно). Рассчитываем множество разниц (a(i)-a(0)) — (b(j)-b(0)), где a(i), b(j) — числа в блоках. Множество этих разниц зависит только от количества цифр в двух системах счисления, поэтому его можно переиспользовать, пока число цифр в одной из систем счисления не изменится. Потом вычисляем разницу между началами блоков b(0)-a(0) и смотрим попадает ли она в это множество. Если попадает — проверяем ответ. Если не попадает — сдвигаем один из блоков вперед.

      У меня получились следующие результаты (на java):
      60 55952637073625955 3.100s
      61 161206152251602161 3.981s
      62 313558153351855313 4.406s
      63 7036267126217626307 11.122s
    • 0
      Спасибо! Это великолепно! Сейчас попробую в этом разобраться.
      • +2
        Еле разобрался в их решении.

        Вкратце идея такая:

        1. Для каждой возможной длины большего из оснований (BASE) генерируем 2 набора частичных палиндромов.
          1. 1-й, вида a..b0..00..0b..a, где (a != 0)
          2. 2-й, вида 0..0c..dd..c0..0, без ограничений.
          * множеством всех палиндромов данной длины, очевидно, будет множество всех попарных сумм.
        2. Переводим все палиндромы из обоих наборов во второе основание (base).
        3. Смотрим на N верних цифр палиндромов из первого набора и на N нижних из обоих. N прямо пропорционально ширине a..b
        4. Используем факт, что если пара элементов образует палиндром в основании (base), то и (N верних цифр 1-го набора).(сумма N нижних цифр обоих) ПРИМЕРНО образуют палиндром в основании (base). Это возможно потому, что прибавление даже максимально возможного палиндрома из 2-го набора ПОЧТИ не влияет на N верних цифр 1-го набора. При правильно выбранной структуре хранения элементов 2-го набора, это позволяет для каждого элемента из 1-го набора проверять относительно небольшое количество элементов из 2-го.


        Нахождение всех двойных палиндромов по основаниям 2 и 10, до 2^60, занимает ~0.1 секунды, при этом проверку на палиндром в основании (base) проходят 174984 (из более милларда!) пар.
        • +1
          Ещё немного оптимизации, и время уменьшено до ~0.03 секунды.
          • 0
            ilyanik Отличная работа! Я по этому решению хотел отдельную статью написать. Это довольно сложное и очень интересное решение. Но, если хотите, я вам уступлю. У меня сейчас немного тяжеловато со временем, а вы уже, я смотрю, во всем разобрались.
            • 0
              Нет, спасибо, «чукча не писатель» :)

              Но если нужно, причешу и прокомментирую свой код (C++) и выложу.
            • 0
              0.016 секунды.

              А если ещё в двух местах операцию модуля заменить на итеративное вычитание, то можно сделать ещё на 10-20% быстрее.
  • 0
    Извините за теоретический пост в практическом топике. :)

    По-моему, куда более эффективной будет «генерация» палиндромов прямо в переменной типа int64. Например, для десятичных палиндромов длиной 4 надо начать с 1001 и дойти до 9999, каждый раз прибавляя либо по 110 (1111, 1221, ...), либо 11 (1991->2002, 2992->3003, ...). Аналогично и постоянно сравнивая, продвигаемся по двоичным палиндромам.
    • 0
      Да. Скорее всего вы правы. Надо только придумать корректные условия для больших чисел. Например, в 6-тизначных палиндромах надо прибавлять 1100, 110 или 11. Для каждого своё условие (ну или свой цикл). А в палиндромах с нечетным кол-вом знаков надо прибавлять 10^n или 11*10^n-1. В общем сейчас попробую это реализовать и отпишусь как это сработало.
      • 0
        Не дождался вашей имплементации:

        Сделал сам
        template<typename IntT, size_t BASE>
        class palindrome_iterator
        {
        	static const size_t MAX_WIDTH = sizeof(IntT) * CHAR_BIT;
        
        	struct IncrementData
        	{
        		IncrementData()
        			: m_counter(BASE - 1)
        			, m_counterLimit(BASE - 1)
        			, m_increment(IntT(1))
        		{}
        
        		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:
        	palindrome_iterator()
        		: m_value(1)
        		, m_countersSize(1)
        		, m_basicIncrement(1)
        		, m_width(1)
        	{
        		m_powers[0] = IntT(1);
        		for (size_t i = 1; i < MAX_WIDTH / 2 + 1; ++i)
        			m_powers[i] = m_powers[i - 1] * IntT(BASE);
        	}
        
        	inline void operator ++()
        	{
        		//	always increment basic
        		m_value += m_basicIncrement;
        
        		size_t i = 0;
        		do {
        			if (--m_counters[i].m_counter)
        				return;
        
        			//	fix value on digit overflow
        			m_counters[i].m_counter = m_counters[i].m_counterLimit;
        			m_value += m_counters[i].m_increment;
        		} while (++i < m_countersSize);
        
        		//	reset increments when new digit is added
        		IncWidth();
        	}
        
        	inline const IntT & operator *() const
        	{
        		return m_value;
        	}
        
        private:
        	void IncWidth()
        	{
        		++m_width;
        		if (m_width & 1) {
        			m_counters[m_countersSize - 1].m_counter = m_counters[m_countersSize - 1].m_counterLimit = BASE;
        			++m_countersSize;
        		}
        
        		if (m_width & 1) { 
        			m_basicIncrement = m_powers[m_countersSize - 1];                                   //	100...
        
        			m_counters[0].m_increment = m_powers[m_countersSize - 2];
        		}
        		else {
        			m_basicIncrement = m_powers[m_countersSize - 1] + m_powers[m_countersSize];        //	110...
        
        			m_counters[0].m_increment = m_powers[m_countersSize - 2] - m_powers[m_countersSize];
        		}
        
        		for (size_t i = 1; i < m_countersSize - 1; ++i)
        			m_counters[i].m_increment = m_powers[m_countersSize - i - 2] - m_powers[m_countersSize - i];
        
        		m_counters[m_countersSize - 1].m_increment = m_powers[0] - m_powers[1];
        	}
        
        	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];
        	IntT           m_powers[MAX_WIDTH / 2 + 1];    //	1, B, B^2, B^3, ... sequence
        	size_t         m_width;                        //	current width = number of digits
        };
        


        Действительно несравнимо быстрее, но все равно недостаточно: просто пройтись по палиндромам до 2^60 у меня занимает 5 секунд. А значит, что найти все палиндромы по 2 основаниям займёт минимум 10 секунд. А по условиям codechef можно за 1.5
  • 0
    Не дождался вашей имплементации:

    Действительно несравнимо быстрее, но все равно недостаточно: просто пройтись по 2^60 палиндромов у меня занимает 5 секунд. А значит, что найти все палиндромы по 2 основаниям займёт минимум 10 секунд. А по условиям codechef можно за 1.5

    template<typename IntT, size_t B>
    class palindrome_iterator
    {
    	static const size_t MAX_W = sizeof(IntT) * 8;
    
    	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:
    	palindrome_iterator()
    		: m_value(1)
    		, m_countersSize(1)
    		, m_basicIncrement(1)
    		, m_width(1)
    	{
    		m_powers[0] = 1;
    		for (size_t i = 1; i < MAX_W; ++i)
    			m_powers[i] = m_powers[i - 1] * (IntT)B;
    
    		for (size_t i = 0; i < MAX_W; ++i) {
    			m_counters[i].m_counter = m_counters[i].m_counterLimit = B - 1;
    		}
    
    		m_counters[0].m_increment = 1;
    	}
    
    	inline void operator ++()
    	{
    		//	always increment basic
    		m_value += m_basicIncrement;
    
    		size_t i = 0;
    		do {
    			if (--m_counters[i].m_counter)
    				return;
    
    			//	fix value on digit overflow
    			m_counters[i].m_counter = m_counters[i].m_counterLimit;
    			m_value += m_counters[i].m_increment;
    		} while (++i < m_countersSize);
    
    		//	reset increments when new digit is added
    		IncWidth();
    	}
    
    	inline const IntT & operator *() const
    	{
    		return m_value;
    	}
    
    private:
    	void IncWidth()
    	{
    		++m_width;
    		if (m_width & 1) {
    			m_counters[m_countersSize - 1].m_counter = m_counters[m_countersSize - 1].m_counterLimit = B;
    			++m_countersSize;
    		}
    
    		if (m_width & 1) { 
    			m_basicIncrement = m_powers[m_countersSize - 1];                                                //	100...
    
    			m_counters[0].m_increment = m_powers[m_countersSize - 2];
    		}
    		else {
    			m_basicIncrement = m_powers[m_countersSize - 1] + m_powers[m_countersSize];
    
    			m_counters[0].m_increment = m_powers[m_countersSize - 2] - m_powers[m_countersSize];
    		}
    
    		for (size_t i = 1; i < m_countersSize - 1; ++i) {
    			m_counters[i].m_increment = m_powers[m_countersSize - i - 2] - m_powers[m_countersSize - i];    //	110...
    		}
    
    		m_counters[m_countersSize - 1].m_increment = m_powers[0] - m_powers[1];
    	}
    
    	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_W];
    	IntT           m_powers[MAX_W];            //	1, B, B^2, B^3, ... sequence
    	size_t         m_width;                    //	current width = number of digits
    };
    

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.