317
правок
Изменения
Нет описания правки
Если <tex>sketch(a_i)< sketch(q)</tex>, то <tex>c_i = 0</tex>, в противном случае <tex>c_i = 1</tex>.
Теперь надо найти количество единиц в <tex>L</tex>. Умножим <tex>L</tex> на <tex>\underbrace{0\ldots 01}_{l + 1 bits}\ldots \underbrace{0\ldots 01}_{l+1 bits}</tex>, тогда все единицы сложатся в первом блоке результата, и, чтобы получить количество единиц, сдвинем его вправо на <tex>(k-1)\cdot(l + 1)</tex> бит. В таком случае мы получим некоторое <tex>2^i</tex>, где <tex>i</tex> является реальным <tex>pred(x)</tex>, а <tex>i</tex> мы можем получить с помощью цикла де Брёйна
== Индекс наиболее старшего бита с помощью цикла де Брёйна ==
'''Последовательность де Брёйна''' {{---}} последовательность <math>a_1,\;\ldots,\;a_t</math>, элементы которой принадлежат заданному конечному множеству (обычно рассматривают множество <math>\{0,\;1,\;\ldots,\;k-1\}</math>), и все подпоследовательности <math>a_{i+1},\;\ldots,\;a_{i+n}</math> заданной длины <math>n</math> различны.
=== Примеры ===
Примеры циклов де Брёйна для <math>k=2</math> с периодом 2, 4, 8, 16:
* 01 (содержит подпоследовательности 0 и 1)
* 0011 (содержит подпоследовательности 00, 01, 11, 10)
* 00010111 (000, 001, 010, 101, 011, 111, 110, 100)
* 0000100110101111
=== Получение индекса по значению степени двойки ===
Возьмем цикл де Брёйна для <tex>n</tex> <tex>(i = 0\ldots n-1)</tex> и запишем его как число <tex>b</tex> (для <tex>8</tex> цикл де Брёна равен <tex>00010111</tex>, а значение <tex>b = 23</tex>). Умножим это число на <tex>2^i</tex>, сдвинем его влево на <tex>i</tex>, а затем обратно вправо на <tex>n-k</tex> (<tex>k</tex> такое, что <tex>n=2^k</tex>). <tex>(b \ll i)\gg(n-k)</tex>), тогда получившееся число {{---}} <tex>i</tex>-ая подстрока длины <tex>k</tex> данного цикла де Брёйна. Эту перестановку опозначим за <tex>p</tex> и тогда применив ее к <tex>(2^i\cdot x) \gg (n-k))</tex> получим <tex>i</tex>: <tex>p</tex> в данном случае такое, что <tex>k</tex> подряд идущих бит равны значению, на сколько мы сдвинули, на какой позиции стоит вектор длины <tex>k</tex>.
==Вычисление sketch(x)==
}}
Первые два условия необходимы для того, чтобы сохранить все существенные биты в нужном порядке. Третье условие позволит поместить <tex>sketch</tex> узла в <tex>w</tex>-битный тип. Так как <tex>r \leqslant B-1</tex>, то <tex>sketch(node)</tex> будет занимать <tex>B(r^4 + 1) \leqslant B((B-1)^4 + 1) = B((B^2 - 2B + 1)^2 + 1)=</tex><tex>B(B^4 + 4B^2 + 1 - 4B^3 + 2B^2 -4B + 1) = B^5 - 4B^3 + 6B^2 - 4B + 2 \leqslant B^5 </tex><tex> = (w^{1/5})^5 = w </tex> бит, при всех <tex>B \geqslant 1</tex>
==См. Также==
