Счётчик Кнута — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
м (rollbackEdits.php mass rollback)
 
(не показаны 22 промежуточные версии 9 участников)
Строка 1: Строка 1:
'''Счетчик Кнута''' (англ. ''Knuth's Counter'') - структура данных, представленная избыточной двоичной системой счисления, где добавление единицы к любому разряду выполняется за <tex>O(1)</tex>.
+
{{Определение
 +
|id=knuth_counter
 +
|definition= '''Счетчик Кнута''' (англ. ''Knuth's Counter'') {{---}} структура данных, представленная избыточной двоичной системой счисления, в которой добавление единицы к числу и вычитание единицы выполняется за <tex>O(1)</tex>.
 +
}}
  
''Избыточная двоичная система счисления'' - двоичная система счисления, где кроме 0 и 1 допустима 2 в записи числа.
+
{{Определение
== Алгоритм ==
+
|id=knuth_counter
''Примечание: этот алгоритм работает не за <tex>O(1)</tex>. Например, чтобы прибавить 1 к 0111...111, нужно <tex>O(n)</tex> действий.''
+
|definition= Неотрицательное целое число <tex>N</tex> в '''избыточной двоичной системе счисления''' записывается в виде последовательности разрядов <tex>(d_n d_{n-1} \dotsc  d_2 d_1)</tex>, где <tex>n</tex> обозначает количество разрядов в числе, <tex>d_i</tex>  {{---}} <tex>i</tex>&ndash;й разряд числа <tex>(1 \leqslant i \leqslant n)</tex>, причем <tex>d_i \in \{0,1,2\}</tex> и <tex>\sum\limits_{i=1}^n d_i \cdot 2^{i-1} = N.
 +
</tex>
 +
}}
  
Имеется число, записанное в избыточной двоичной системе счисления, необходимо добавить 1 к какому-либо разряду. Будем поддерживать следующий инвариант: в следующем за любой двойкой разряде всегда стоит 0.
+
Заметим, что в этой системе представление числа неоднозначно, например представление <tex>212</tex> эквивалентно <tex>1100</tex>.
  
Разберем случаи добавления единицы:
+
== Счетчик Кнута ==
* a) Если 1 нужно добавить к 2, то в текущем разряде установить 1, в следующем 1.
 
* б) Если 1 нужно добавить к 1 и в следующем разряде 0, то в текущем разряде установить 2.
 
* в) Если 1 нужно добавить к 1 и в следующем разряде 1, то в текущем разряде установить 0, повторить алгоритм для следующего разряда.
 
* г) Если 1 нужно добавить к 1 и в следующем разряде 2, то в следующем за двойкой разряде установить 1, в разряде с двойкой установить 1, в текущем установить 0.
 
* д) Если 1 нужно добавить к 0 и в предыдущем разряде 2, в следующем 0, то в предыдущем разряде установить 0, в текущем 2.
 
* е) Если 1 нужно добавить к 0 и в предыдущем разряде 2, в следующем 1, то в предыдущем разряде установить 0, повторить алгоритм для следующего разряда.
 
* ж) Если 1 нужно добавить к 0 и в предыдущем разряде 2, в следующем 2, то в предыдущем разряде установить 0, повторить алгоритм для следующего разряда.
 
* з) Если 1 нужно добавить к 0 и в предыдущем разряде не 2, установить в текущем разряде 1.
 
  
== Доказательство ==
+
==== Описание операции инкремента ====
Покажем, что инвариант не нарушится.
 
  
Инвариант можно нарушить в 2 случаях: когда к единице прибавляют 1, и в следующем разряде стоит не 0, и когда к нулю прибавляется 1, а в предыдущем разряде стоит 2.
+
Оригинальный метод предложен Кнутом и состоит из двух действий:
  
В первом случае, если в следующем разряде 1, алгоритм будет устанавливать в текущий разряд 0 и запускаться от следующего разряда. Если в следующем разряде 2, то, согласно инварианту, следующий за 2 разряд 0, и, если установить в следующий за двойкой и в разряд с двойкой единицы, то инвариант не нарушится.
+
# Найти младший разряд <tex>d_i</tex> равный <tex>2</tex> и, если таковой имеется, заменить последовательность <tex>(\dotsc d_{i+1}d_i \dotsc)</tex> на <tex>(\dotsc (d_{i+1}+1)0 \dotsc)</tex>
 +
# Заменить <tex>d_1</tex> на <tex>d_1+1</tex>.
  
Во втором случае, если в следующем разряде 0, то предыдущий установится в 0, текущий в 2 и так как в следующем 0 инвариант не нарушится. Если в следующем разряде не 0, то предыдущий установится в 0 и алгоритм запустится от следующего.
+
Чтобы достичь необходимой оценки и не выполнять каждый раз поиск для первого правила, можно хранить односвязный [[Список|список]] позиций двоек в числе. Тогда, чтобы найти младший разряд равный двум, нужно просто взять первый элемент списка. Также, непосредственно перед изменением значений разрядов, необходимо выполнять следующие дополнительные действия:
  
== Пример ==
+
# Если <tex>d_{i+1}=1</tex>, то заменить первый элемент списка с <tex>i</tex> на <tex>i+1</tex>, иначе удалить его.
Рассмотрим пример для каждого варианта, добавление 1 происходит в 3 разряд.
+
# Если <tex>d_1=1</tex>, то добавить в начало списка <tex>1</tex>.
  
а) <tex>200_{2} \Rightarrow 1100_{2}</tex>
+
==== Инвариант с нулем ====
  
б) <tex>0100_{2} \Rightarrow 0200_{2}</tex>
+
Проблемой может оказаться появление двух последовательных двоек, при этом первое правило может породить
 +
тройку. То есть недопустима следующая ситуация:
  
в) <tex>1100_{2} \Rightarrow 1000_{2}</tex> повторение алгоритма для 4 разряда, по варианту б <tex>1000_{2} \Rightarrow 2000_{2}</tex>
+
<tex>(\dotsc 22\dotsc) \overset{Inc} {\longmapsto} (\dotsc 30\dotsc)</tex>.
  
г) <tex>2100_{2} \Rightarrow 11000_{2}</tex>
+
В свою очередь такая ситуация получается из этой:
  
д) <tex>10020_{2} \Rightarrow 10200_{2}</tex>
+
<tex>(\dotsc 212\dotsc) \overset{Inc} {\longmapsto} (\dotsc 220\dotsc)</tex>
  
е) <tex>1020_{2} \Rightarrow 1000_{2}</tex> повторение алгоритма для 4 разряда, по варианту б <tex>1000_{2} \Rightarrow 2000_{2}</tex>
+
Причем количество единиц между двойками может быть любое, в итоге это приведет к появлению тройки.
 +
Однако если между любой парой двоек всегда будет находиться хотя бы один
 +
<tex>0</tex>, то такой ситуации не возникнет. Покажем, что этот инвариант
 +
поддерживается после инкремента, рассмотрев возможные ситуации:
 +
: Число двоек не изменяется
 +
:: <tex>(\dotsc 2\dotsc 0\dotsc 12\dotsc 0) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 0\dotsc 20\dotsc 1)</tex>.
 +
:: <tex>(\dotsc 02\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 10\dotsc 2)</tex>.
 +
:: <tex>(\dotsc 2\dotsc 02\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 10\dotsc 2)</tex> (частный случай предыдущего).
 +
:: <tex>(\dotsc 12) \overset{Inc} {\longmapsto} (\dotsc 21)</tex>.
 +
: Пропадает одна двойка
 +
:: <tex>(\dotsc 02\dotsc 0) \overset{Inc} {\longmapsto} (\dotsc 10\dotsc 1)</tex>.
 +
:: <tex>(\dotsc 02) \overset{Inc} {\longmapsto} (\dotsc 11)</tex>.
 +
: Появление новой двойки
 +
:: <tex>(\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2)</tex> (имеется в виду появление единственной двойки).
 +
:: <tex>(\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 20\dotsc 2)</tex>.
 +
:: <tex>(\dotsc 2\dotsc 0\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 0\dotsc 20\dotsc 2)</tex> (частный случай предыдущего).
  
ж) <tex>2020_{2} \Rightarrow 2000_{2}</tex> повторение алгоритма для 4 разряда, по варианту а <tex>2000_{2} \Rightarrow 11000_{2}</tex>
+
Таким образом мы видим, что <tex>0</tex> всегда сохраняется.
  
з) <tex>010_{2} \Rightarrow 110_{2}</tex>
+
==== Пример ====
  
== Амортизационная оценка алгоритма ==
+
В таблице можно увидеть как будет изменяться представление при применении данных правил десять раз к нулю (представления чисел от <tex>0</tex> до <tex>9</tex>):
Воспользуемся методом предоплаты. Будем считать, что каждый раз когда мы начинаем выполнять алгоритм мы берем 2 монетки. Одна будет тратится на изменение текущего разряда и одна запасаться. Таким образом, если в разряде стоит 1, то для него запасена 1 монетка, если стоит 2, то запасено 2 монетки. Проверим все варианты.
 
  
а) Так как в текущем разряде было 2, то уже запасено 2 монеты, а так же согласно инварианту после 2 стоит 0, тогда возьмем одну из запасенных у двойки монет и потратим их на присвоение следующему разряду 1, вторую запасенную передадим этой единице. Одну монету потратим на установку в текущий разряд 1, вторую запасем для это единицы.
+
{| class="wikitable"
 +
|-
 +
! Шаг
 +
! Представление
 +
|-
 +
| 0
 +
| 0
 +
|-
 +
| 1  
 +
| 1
 +
|-
 +
| 2
 +
| 2
 +
|-
 +
| 3
 +
| 11
 +
|-
 +
| 4
 +
| 12
 +
|-
 +
| 5
 +
| 21
 +
|-
 +
| 6
 +
| 102
 +
|-
 +
| 7
 +
| 111
 +
|-
 +
| 8
 +
| 112
 +
|-
 +
| 9
 +
| 121
 +
|}
  
б) Так как в текущем разряде было 1, то прибавим наши монеты к уже запасенной от единицы. Одну монету потратим, что бы установить 2, останется 2 монеты.
+
== Обобщение на системы с произвольным основанием ==
  
в) Так как в текущем разряде было 1, то прибавив наши монеты к запасенной получим 3. Одну монету потратим, что бы установить 0, оставшиеся 2 потратим на повторение алгоритма для следующего разряда.
+
{{Определение
 +
|id=b_ary_rr
 +
|definition=В общем случае подобное представление называется '''<tex>b</tex>-ричным избыточным представлением''' ('''ИП''', англ. ''b-ary redundant representation''), которое похоже на представление в счетчике Кнута, но основание системы может быть произвольным, то есть <tex>d_i \in \{0,1,\dotsc ,b\}</tex> и <tex>\sum\limits_{i=1}^n d_i \cdot b^i = N</tex>, где <tex>b</tex>  {{---}} основание. Оно позволяет прибавить единицу к любому разряду, то есть увеличить число на <tex>b^i</tex> за <tex>O(1)</tex>
 +
}}
  
г) Так как в текущем разряде было 1, в следующем 2, то уже запасено 3 монеты и еще 2 наши. 3 монеты потратим, что бы следующему за 2 разряду установить 1, разряду с 2 установить 1, текущему установить 0. Останется 2 монеты, которые распределятся между двумя единицами.
+
{{Определение
 +
|id=regular_rr
 +
|definition= Назовем представление '''регулярным''' (англ. ''regular''), если между двумя разрядами равными <tex>b</tex> есть хотя бы один разряд отличный от <tex>b-1</tex>.
 +
}}
  
д) Так как в текущем разряде было 0, в предыдущем разряде 2, в следующем 0, то уже запасено 2 монеты. Одну монету потратим на изменение предыдущего разряда, одну на изменение текущего разряда, наши две монеты запасем для двойки в текущем разряде.
+
{{Определение
 +
|id=fixup
 +
|definition= Операция '''исправления''' (англ. ''fix'') разряда <tex>d_i=b</tex> в регулярном ИП увеличивает <tex>d_{i+1}</tex> на <tex>1</tex> и устанавливает <tex>d_i</tex> в <tex>0</tex>, образуя новое регулярное ИП, представляющее то же число, что и <tex>d</tex>.
 +
}}
  
е) Так как в текущем разряде было 0, в предыдущем разряде 2, в следующем 1, то уже запасено 3 монеты. Одну монету потратим на изменение предыдущего разряда, одну сохраним с единицей, наши две монеты потратим на повторение алгоритма на следующем разряде. Останется одна лишняя монета.
+
Чтобы добавить <tex>1</tex> к разряду <tex>d_i</tex> регулярного ИП <tex>d</tex>,
 +
нужно выполнить следующие действия:
 +
# Если <tex>d_i=b</tex>, исправить <tex>d_i</tex>.
 +
# Если <tex>d_i=b-1</tex> и самый младший значащий разряд <tex>d_j</tex>, такой, что <tex>j>i</tex> и <tex>d_j \ne b-1</tex>, равен <tex>b</tex> (т.е. <tex>d_j=b</tex>), применить операцию исправления к разряду <tex>d_j</tex>.
 +
# Добавить <tex>1</tex> к <tex>d_i</tex>.
 +
# Если <tex>d_i=b</tex>, исправить <tex>d_i</tex>.
  
ж) Так как в текущем разряде было 0, в предыдущем разряде 2, в следующем 2, то уже запасено 4 монеты. Одну монету потратим на изменение предыдущего разряда, две сохраним с двойкой, наши две монеты потратим на повторение алгоритма на следующем разряде. Останется одна лишняя монета.
+
Для реализации данной схемы мы используем односвязный список разрядов от младших
 +
к старшим. В дополнение каждый разряд <tex>d_i</tex> равный <tex>b-1</tex>
 +
будет иметь указатель на самый младший разряд <tex>d_j</tex>, такой,
 +
что <tex>j>i</tex> и <tex>d_j \ne b-1</tex>, если он равен <tex>b</tex>,
 +
иначе этот указатель будет на произвольный разряд <tex>d_j</tex> (<tex>j>i</tex>).
 +
Теперь во время увеличения разряда <tex>d_i</tex> на <tex>1</tex> будем проверять
 +
разряд по указателю вперед (п. 2).
  
з) Одну монету потратим на изменение разряда, оставшуюся запасем с единицей.
+
Такое представление позволяет увеличивать произвольный разряд на единицу за константное
 +
время. Обновление указателя вперед происходит следующим образом: когда <tex>d_{i+}</tex> становится равен <tex>b-1</tex> при исправлении разряда <tex>d_{i-1}</tex>, устанавливаем указатель вперед разряда <tex>d_{i}</tex> на <tex>d_{i+1}</tex>, если <tex>d_{i+1}=b</tex>, либо копируем указатель вперед из <tex>d_{i+1}</tex> в <tex>d_{i}</tex>, если <tex>d_{i+1}=b-1</tex>.
 +
При собственно добавлении единицы к разряду <tex>d_i</tex>, также необходимо обновлять его указатель вперед аналогичным образом,
 +
если этот разряд становится равен <tex>b-1</tex>.
  
Получается 2 монет достаточно для прибавления 1 к любому разряду, тогда наш алгоритм работает в среднем за <tex>O(1)</tex>
+
== См. также ==
 +
* [[Амортизационный анализ]]
 +
* [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код|Представление целых чисел]]
  
== Смотри также ==
+
== Источники информации ==
* [[Амортизационный анализ]]
+
* H. Kaplan и R. E. Tarjan. New heap data structures. 1998
* [[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
+
* M. J. Clancy и D. E. Knuth. A programming and problem-solving seminar. Technical Report STAN-CS-77-606, Department of Computer Sciencr, Stanford University, Palo Alto, 1977.
 +
* G. S. Brodal. Worst case priority queues. ''Proc. 7th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 96)'', страницы 52-58. ACM Press, 1996.
 +
* H. Kaplan и R. E. Tarjan. Purely functional representations of catenable sorted lists. ''Proceedings of the 28th Annual ACM Symposium of Computing'', страницы 202-211. ACM Press, 1996
 +
* [http://www.cphstl.dk/Paper/Numeral-systems/mfcs-13.pdf In-Place Binary Counter]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Амортизационный анализ]]
 
[[Категория: Амортизационный анализ]]

Текущая версия на 19:13, 4 сентября 2022

Определение:
Счетчик Кнута (англ. Knuth's Counter) — структура данных, представленная избыточной двоичной системой счисления, в которой добавление единицы к числу и вычитание единицы выполняется за [math]O(1)[/math].


Определение:
Неотрицательное целое число [math]N[/math] в избыточной двоичной системе счисления записывается в виде последовательности разрядов [math](d_n d_{n-1} \dotsc d_2 d_1)[/math], где [math]n[/math] обозначает количество разрядов в числе, [math]d_i[/math][math]i[/math]–й разряд числа [math](1 \leqslant i \leqslant n)[/math], причем [math]d_i \in \{0,1,2\}[/math] и [math]\sum\limits_{i=1}^n d_i \cdot 2^{i-1} = N. [/math]


Заметим, что в этой системе представление числа неоднозначно, например представление [math]212[/math] эквивалентно [math]1100[/math].

Счетчик Кнута

Описание операции инкремента

Оригинальный метод предложен Кнутом и состоит из двух действий:

  1. Найти младший разряд [math]d_i[/math] равный [math]2[/math] и, если таковой имеется, заменить последовательность [math](\dotsc d_{i+1}d_i \dotsc)[/math] на [math](\dotsc (d_{i+1}+1)0 \dotsc)[/math]
  2. Заменить [math]d_1[/math] на [math]d_1+1[/math].

Чтобы достичь необходимой оценки и не выполнять каждый раз поиск для первого правила, можно хранить односвязный список позиций двоек в числе. Тогда, чтобы найти младший разряд равный двум, нужно просто взять первый элемент списка. Также, непосредственно перед изменением значений разрядов, необходимо выполнять следующие дополнительные действия:

  1. Если [math]d_{i+1}=1[/math], то заменить первый элемент списка с [math]i[/math] на [math]i+1[/math], иначе удалить его.
  2. Если [math]d_1=1[/math], то добавить в начало списка [math]1[/math].

Инвариант с нулем

Проблемой может оказаться появление двух последовательных двоек, при этом первое правило может породить тройку. То есть недопустима следующая ситуация:

[math](\dotsc 22\dotsc) \overset{Inc} {\longmapsto} (\dotsc 30\dotsc)[/math].

В свою очередь такая ситуация получается из этой:

[math](\dotsc 212\dotsc) \overset{Inc} {\longmapsto} (\dotsc 220\dotsc)[/math]

Причем количество единиц между двойками может быть любое, в итоге это приведет к появлению тройки. Однако если между любой парой двоек всегда будет находиться хотя бы один [math]0[/math], то такой ситуации не возникнет. Покажем, что этот инвариант поддерживается после инкремента, рассмотрев возможные ситуации:

Число двоек не изменяется
[math](\dotsc 2\dotsc 0\dotsc 12\dotsc 0) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 0\dotsc 20\dotsc 1)[/math].
[math](\dotsc 02\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 10\dotsc 2)[/math].
[math](\dotsc 2\dotsc 02\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 10\dotsc 2)[/math] (частный случай предыдущего).
[math](\dotsc 12) \overset{Inc} {\longmapsto} (\dotsc 21)[/math].
Пропадает одна двойка
[math](\dotsc 02\dotsc 0) \overset{Inc} {\longmapsto} (\dotsc 10\dotsc 1)[/math].
[math](\dotsc 02) \overset{Inc} {\longmapsto} (\dotsc 11)[/math].
Появление новой двойки
[math](\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2)[/math] (имеется в виду появление единственной двойки).
[math](\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 20\dotsc 2)[/math].
[math](\dotsc 2\dotsc 0\dotsc 12\dotsc 1) \overset{Inc} {\longmapsto} (\dotsc 2\dotsc 0\dotsc 20\dotsc 2)[/math] (частный случай предыдущего).

Таким образом мы видим, что [math]0[/math] всегда сохраняется.

Пример

В таблице можно увидеть как будет изменяться представление при применении данных правил десять раз к нулю (представления чисел от [math]0[/math] до [math]9[/math]):

Шаг Представление
0 0
1 1
2 2
3 11
4 12
5 21
6 102
7 111
8 112
9 121

Обобщение на системы с произвольным основанием

Определение:
В общем случае подобное представление называется [math]b[/math]-ричным избыточным представлением (ИП, англ. b-ary redundant representation), которое похоже на представление в счетчике Кнута, но основание системы может быть произвольным, то есть [math]d_i \in \{0,1,\dotsc ,b\}[/math] и [math]\sum\limits_{i=1}^n d_i \cdot b^i = N[/math], где [math]b[/math] — основание. Оно позволяет прибавить единицу к любому разряду, то есть увеличить число на [math]b^i[/math] за [math]O(1)[/math]


Определение:
Назовем представление регулярным (англ. regular), если между двумя разрядами равными [math]b[/math] есть хотя бы один разряд отличный от [math]b-1[/math].


Определение:
Операция исправления (англ. fix) разряда [math]d_i=b[/math] в регулярном ИП увеличивает [math]d_{i+1}[/math] на [math]1[/math] и устанавливает [math]d_i[/math] в [math]0[/math], образуя новое регулярное ИП, представляющее то же число, что и [math]d[/math].


Чтобы добавить [math]1[/math] к разряду [math]d_i[/math] регулярного ИП [math]d[/math], нужно выполнить следующие действия:

  1. Если [math]d_i=b[/math], исправить [math]d_i[/math].
  2. Если [math]d_i=b-1[/math] и самый младший значащий разряд [math]d_j[/math], такой, что [math]j\gt i[/math] и [math]d_j \ne b-1[/math], равен [math]b[/math] (т.е. [math]d_j=b[/math]), применить операцию исправления к разряду [math]d_j[/math].
  3. Добавить [math]1[/math] к [math]d_i[/math].
  4. Если [math]d_i=b[/math], исправить [math]d_i[/math].

Для реализации данной схемы мы используем односвязный список разрядов от младших к старшим. В дополнение каждый разряд [math]d_i[/math] равный [math]b-1[/math] будет иметь указатель на самый младший разряд [math]d_j[/math], такой, что [math]j\gt i[/math] и [math]d_j \ne b-1[/math], если он равен [math]b[/math], иначе этот указатель будет на произвольный разряд [math]d_j[/math] ([math]j\gt i[/math]). Теперь во время увеличения разряда [math]d_i[/math] на [math]1[/math] будем проверять разряд по указателю вперед (п. 2).

Такое представление позволяет увеличивать произвольный разряд на единицу за константное время. Обновление указателя вперед происходит следующим образом: когда [math]d_{i+}[/math] становится равен [math]b-1[/math] при исправлении разряда [math]d_{i-1}[/math], устанавливаем указатель вперед разряда [math]d_{i}[/math] на [math]d_{i+1}[/math], если [math]d_{i+1}=b[/math], либо копируем указатель вперед из [math]d_{i+1}[/math] в [math]d_{i}[/math], если [math]d_{i+1}=b-1[/math]. При собственно добавлении единицы к разряду [math]d_i[/math], также необходимо обновлять его указатель вперед аналогичным образом, если этот разряд становится равен [math]b-1[/math].

См. также

Источники информации

  • H. Kaplan и R. E. Tarjan. New heap data structures. 1998
  • M. J. Clancy и D. E. Knuth. A programming and problem-solving seminar. Technical Report STAN-CS-77-606, Department of Computer Sciencr, Stanford University, Palo Alto, 1977.
  • G. S. Brodal. Worst case priority queues. Proc. 7th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 96), страницы 52-58. ACM Press, 1996.
  • H. Kaplan и R. E. Tarjan. Purely functional representations of catenable sorted lists. Proceedings of the 28th Annual ACM Symposium of Computing, страницы 202-211. ACM Press, 1996
  • In-Place Binary Counter